是否存在"二进制排序"算法？

Question

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

Answer 1

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

两种算法都进行了O(n log n)多次比较,但实际上你还需要移动元素,这会使整个算法成为二次方.

Answer 2

对于JDK其Arrays.sort()方法中大小小于32的数组，会使用“二进制排序” 。这实际上是一个，insertion sort但是binary search用于查找下一项而不是线性搜索。

这是来自的代码 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;
    }
}