smile.sort.QuickSort类的使用及代码示例

x33g5p2x  于2022-01-28 转载在 其他  
字(7.2k)|赞(0)|评价(0)|浏览(151)

本文整理了Java中smile.sort.QuickSort类的一些代码示例,展示了QuickSort类的具体用法。这些代码示例主要来源于Github/Stackoverflow/Maven等平台,是从一些精选项目中提取出来的代码,具有较强的参考意义,能在一定程度帮忙到你。QuickSort类的具体详情如下:
包路径:smile.sort.QuickSort
类名称:QuickSort

QuickSort介绍

[英]Quicksort is a well-known sorting algorithm that, on average, makes O(n log n) comparisons to sort n items. For large n (say > 1000), Quicksort is faster, on most machines, by a factor of 1.5 or 2 than other O(n log n) algorithms. However, in the worst case, it makes O(n2) comparisons. Quicksort requires a bit of extra memory.

Quicksort is a comparison sort. A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator obey the three defining properties of a total order:

  • if a ≤ b and b ≤ a then a = b (antisymmetry)
  • if a ≤ b and b ≤ c then a ≤ c (transitivity)
  • a ≤ b or b ≤ a (totalness or trichotomy)

Quicksort, however, is not a stable sort in efficient implementations. Stable sorting algorithms maintain the relative order of records with equal keys. If all keys are different then this distinction is not necessary. But if there are equal keys, then a sorting algorithm is stable if whenever there are two records(let's say R and S) with the same key, and R appears before S in the original list, then R will always appear before S in the sorted list.

For speed of execution, we implement it without recursion. Instead, we requires an auxiliary array (stack) of storage, of length 2 log2 n. When a subarray has gotten down to size 7, we sort it by straight insertion.
[中]快速排序是一种众所周知的排序算法,它平均对n个项目进行O(n logn)比较。对于大n(比如>1000),在大多数机器上,快速排序比其他O(n logn)算法快1.5或2倍。然而,在最坏的情况下,它会进行O(n2)比较。快速排序需要一些额外的内存。
快速排序是一种比较排序。比较排序是一种排序算法,它只通过单个抽象比较操作(通常是“小于或等于”运算符)读取列表元素,该操作确定两个元素中的哪一个应该首先出现在最终排序的列表中。唯一的要求是,运算符必须遵守总序的三个定义属性:
*如果≤ b和b≤ a然后a=b(反对称)
*如果≤ b和b≤ c然后a≤ c(及物性)
*a≤ b还是b≤ a(整体或三分法)
然而,在高效的实现中,快速排序并不是一种稳定的排序。稳定的排序算法保持具有相等键的记录的相对顺序。如果所有键都不同,则无需进行这种区分。但是如果有相等的键,那么排序算法是稳定的,如果每当有两个记录(比如R和s)具有相同的键,并且R在原始列表中出现在s之前,那么R在排序列表中总是出现在s之前。
为了提高执行速度,我们实现它时不需要递归。相反,我们需要一个长度为2 log2 n的辅助存储阵列(堆栈)。当子阵列的大小降至7时,我们通过直接插入对其进行排序。

代码示例

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * Sorts the specified array into ascending numerical order.
 * @return the original index of elements after sorting in range [0, n).
 */
public static int[] sort(int[] arr) {
  int[] order = new int[arr.length];
  for (int i = 0; i < order.length; i++) {
    order[i] = i;
  }
  sort(arr, order);
  return order;
}

代码示例来源:origin: stackoverflow.com

Execute ex=new Execute();
ex.takeInput();
QuickSort q=new QuickSort();
q.sort(ex.getA(),0,ex.getLen()-1);
System.out.println("Printing the the Sorted Object");
System.out.println(ex);

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * Sorts the specified array into ascending order.
 * @return the original index of elements after sorting in range [0, n).
 */
public static <T extends Comparable<? super T>>  int[] sort(T[] arr) {
  int[] order = new int[arr.length];
  for (int i = 0; i < order.length; i++) {
    order[i] = i;
  }
  sort(arr, order);
  return order;
}

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * Sorts the specified array into ascending numerical order.
 * @return the original index of elements after sorting in range [0, n).
 */
public static int[] sort(double[] arr) {
  int[] order = new int[arr.length];
  for (int i = 0; i < order.length; i++) {
    order[i] = i;
  }
  sort(arr, order);
  return order;
}

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * Besides sorting the array arr, the array brr will be also
 * rearranged as the same order of arr.
 */
public static <T extends Comparable<? super T>>  void sort(T[] arr, int[] brr) {
  sort(arr, brr, arr.length);
}

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * Sorts the specified array into ascending numerical order.
 * @return the original index of elements after sorting in range [0, n).
 */
public static int[] sort(float[] arr) {
  int[] order = new int[arr.length];
  for (int i = 0; i < order.length; i++) {
    order[i] = i;
  }
  sort(arr, order);
  return order;
}

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * Besides sorting the array arr, the array brr will be also
 * rearranged as the same order of arr.
 */
public static void sort(double[] arr, Object[] brr) {
  sort(arr, brr, arr.length);
}

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * Besides sorting the array arr, the array brr will be also
 * rearranged as the same order of arr.
 */
public static <T extends Comparable<? super T>>  void sort(T[] arr, Object[] brr) {
  sort(arr, brr, arr.length);
}

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * Besides sorting the array arr, the array brr will be also
 * rearranged as the same order of arr.
 */
public static void sort(int[] arr, Object[] brr) {
  sort(arr, brr, arr.length);
}

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * Besides sorting the array arr, the array brr will be also
 * rearranged as the same order of arr.
 */
public static void sort(float[] arr, Object[] brr) {
  sort(arr, brr, arr.length);
}

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * This is an effecient implementation Quick Sort algorithm without
 * recursive. Besides sorting the array arr, the array brr will be also
 * rearranged as the same order of arr.
 */
public static void sort(double[] arr, double[] brr) {
  sort(arr, brr, arr.length);
}

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * Besides sorting the array arr, the array brr will be also
 * rearranged as the same order of arr.
 */
public static void sort(int[] arr, int[] brr) {
  sort(arr, brr, arr.length);
}

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * Besides sorting the array arr, the array brr will be also
 * rearranged as the same order of arr.
 */
public static void sort(float[] arr, int[] brr) {
  sort(arr, brr, arr.length);
}

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * Besides sorting the array arr, the array brr will be also
 * rearranged as the same order of arr.
 */
public static void sort(float[] arr, float[] brr) {
  sort(arr, brr, arr.length);
}

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * Besides sorting the array arr, the array brr will be also
 * rearranged as the same order of arr.
 */
public static void sort(double[] arr, int[] brr) {
  sort(arr, brr, arr.length);
}

代码示例来源:origin: com.github.haifengl/smile-math

/**
 * Sorts each variable and returns the index of values in ascending order.
 * Note that the order of original array is NOT altered.
 * 
 * @param x a set of variables to be sorted. Each row is an instance. Each
 * column is a variable.
 * @return the index of values in ascending order
 */
public static int[][] sort(double[][] x) {
  int n = x.length;
  int p = x[0].length;
  
  double[] a = new double[n];
  int[][] index = new int[p][];
  
  for (int j = 0; j < p; j++) {
    for (int i = 0; i < n; i++) {
      a[i] = x[i][j];
    }
    index[j] = QuickSort.sort(a);
  }
  
  return index;
}

代码示例来源:origin: io.github.myui/hivemall-core

@Nonnull
public static int[][] sort(@Nonnull final Attribute[] attributes, @Nonnull final double[][] x) {
  final int n = x.length;
  final int p = x[0].length;
  final double[] a = new double[n];
  final int[][] index = new int[p][];
  for (int j = 0; j < p; j++) {
    if (attributes[j].type == AttributeType.NUMERIC) {
      for (int i = 0; i < n; i++) {
        a[i] = x[i][j];
      }
      index[j] = QuickSort.sort(a);
    }
  }
  return index;
}

代码示例来源:origin: com.github.haifengl/smile-core

/**
 * Sorts each variable and returns the index of values in ascending order.
 * Only numeric attributes will be sorted. Note that the order of original
 * array is NOT altered.
 * 
 * @param x a set of variables to be sorted. Each row is an instance. Each
 * column is a variable.
 * @return the index of values in ascending order
 */
public static int[][] sort(Attribute[] attributes, double[][] x) {
  int n = x.length;
  int p = x[0].length;
  
  double[] a = new double[n];
  int[][] index = new int[p][];
  
  for (int j = 0; j < p; j++) {
    if (attributes[j].getType() == Attribute.Type.NUMERIC) {
      for (int i = 0; i < n; i++) {
        a[i] = x[i][j];
      }
      index[j] = QuickSort.sort(a);
    }
  }
  
  return index;        
}

代码示例来源:origin: com.github.haifengl/smile-core

QuickSort.sort(o, itemset, t);

代码示例来源:origin: com.github.haifengl/smile-core

double[] prediction = probability.clone();
QuickSort.sort(prediction, label);

相关文章

QuickSort类方法