algorithm - 是否存在"二进制排序"算法?

  显示原文与译文双语对照的内容
134 0

是否有一个名为"二进制排序"的排序算法? 合并排序。选择排序或者其他排序类型一样,是否存在二进制排序?

时间: 原作者:

89 2

这里有 ,还有二进制插入排序。 两者非常相似。 它们都是二次( O(n^2) ) 时间算法。

两种算法都做 O(n log n) 比较,但实际上,你还需要移动元素,这将使整个算法二次化。

原作者:
93 2

JDK 在它的Arrays.sort() 方法中使用"二进制排序"的数组 <大小 32. 下面是 JDK7的代码


private static void binarySort(Object[] a, int lo, int hi, int start) {


 assert lo <= start && start <= hi;


 if (start == lo)


 start++;


 for ( ; start <hi; start++) {


 @SuppressWarnings("unchecked")


 Comparable<Object> pivot = (Comparable) a[start];



//Set left (and right) to the index where a[start] (pivot) belongs


 int left = lo;


 int right = start;


 assert left <= right;


/*


 * Invariants:


 * pivot> = all in [lo, left).


 * pivot <all in [right, start).


 */


 while (left <right) {


 int mid = (left + right)>> > 1;


 if (pivot.compareTo(a[mid]) <0)


 right = mid;


 else


 left = mid + 1;


 }


 assert left == right;



/*


 * The invariants still hold: pivot> = all in [lo, left) and


 * pivot <all in [left, start), so pivot belongs at left. Note


 * that if there are elements equal to pivot, left points to the


 * first slot after them -- that's why this sort is stable.


 * Slide elements over to make room for pivot.


 */


 int n = start - left;//The number of elements to move


//Switch is just an optimization for arraycopy in default case


 switch (n) {


 case 2: a[left + 2] = a[left + 1];


 case 1: a[left + 1] = a[left];


 break;


 default: System.arraycopy(a, left, a, left + 1, n);


 }


 a[left] = pivot;


 }


}



原作者:
139 5

二进制排序是一种非常快速的算法,它涉及位测试。 它对可以排序项中的每个位都有一次传递。 对于每个通道,如果设置了位,则可以排序的项将堆叠在缓冲区的一端。 如果未设置位,则该项将堆叠在缓冲区的另一端。 在最小的位中启动排序,以及处理下一个位的处理将导致排序列表。 我在苏格兰教育部门的早期 8086中写了其中的一个。 Pitts

...