一道排序面试题【20200103】

Java程序如下：

public class SortTest {
    public static void main(String[] args) {
        int[] a = {10, 20, 3, 21, 11, 10, 9, 3, 6 ,- 2};
        int i, j;
        int low, high, mid;
        int temp;
        for (i = 1; i < 10; i++) {
            temp = a[i];
            low = 0;
            high = i - 1;
            while (low <= high) {
                mid = (low + high) / 2;
                if (a[mid] > temp)
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            for (j = i - 1; j > high; j--)
                a[j + 1] = a[j];
            a[high + 1] = temp;
        }
        //输出排序后结果
        for (i = 0; i < 10; i++) {
            System.out.print(a[i]+" ");
        }
    }
}

上面这段代码属于哪一种排序？

A，归并排序

B，快速排序

C，希尔排序

D，二分法排序

解析：

从二分字面上理解的话，快速排序和归并排序都与二分相关；快速排序按照标值二分，小的在前，大的在后；而归并排序是按照下标二分，再分别对两个部分归并排序，先分后和，在和的过程中排序。

此外，还有一种二叉树排序，它的原理是：构造二叉树，小的在左，大的在右，将待排序的数一次插入，然后前序遍历即可，这种方法利用二叉树的特殊构造把每个数插入到恰当的位置，跟二分的概念略有关系。

目前比较公认的二分法排序是指折半插入排序。当直接插入排序进行到某一趟时候，对r[i].key来讲，前边i-1个记录极影按关键字有序，此时不用直接吃哈如排序的方法，而改为二分法折半查找，找出r[i].key应插的位置，然后插入。这种方法就是折半插入排序（二分法排序）。在二分法排序中，关键字的比较次数由于采用折半查找而减少，数量级为O（n log n），但是元素移动次数仍然为O（n二次方）。所以者半插入排序时间复杂度还是O（n二次方）。

答案：D