排序算法(2)

排序算法1中，对于选择排序和插入排序进行了介绍，通过代码，可以看出，假设有一个给定的乱序数组，插入排序因为都只能通过交换相邻的元素，于是得到的时间复杂度是相对来说比较高的。从这也可以看出，在插入排序中，元素只能缓慢的从一端到另一端。从这就可以观察得到，这应该还有优化的空间，于是，基于插入排序的改进算法进一步提出。

希尔排序

既然插入排序对于乱序对象的处理能力比较差，也就是某个对象需要从一端到另外一端。基于这个思想，能不能不让对象只一个一个相邻交换。因此，希尔排序通过扩大每个对象的间隔交换值h，从而保证任意间隔值h都都是有序的；这样通过较大的将间隔值，从而保证对象不是一个一个相邻移动，从而提高效率。看代码，此代码还是基于排序算法1中的模板，以下只展示sort部分，其余部分可参见排序算法1：

   //目标：实现a[]按照升序排列
    public static void sort(Comparable[] a){
        int N = a.length;
        //数据间隔h时为有序。
        int h = 1;
        //找到最大的间隔h,除以几可以根据需要进行调节
        while(h < N/3){
            h = 3*h + 1;
        }
        while(h >= 1){
            for (int i = h; i < N ; i++) {
                for (int j = i; j >= h && less(a[j],a[j-h]); j-=h) {
                    exch(a,j,j-h);
                }
            }
            show(a);
            h = h/3;
        }
​
    }

在此，可能体会不到希尔排序起到了什么作用，通过一个简单的小实验，体会下

希尔排序结果

原始数组：20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
第一次：7 6 5 4 3 2 1 13 12 11 10 9 8 20 19 18 17 16 15 14 
第二次：3 2 1 4 7 6 5 9 8 11 10 13 12 16 15 14 17 20 19 18 
第三次：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

通过观察可以得到，希尔排序很快就可以把乱序偏后的元素移动到另外一边，这就是希尔排序的强大之处。所以说，在此也会有很多疑问，如何进行选择间隔递增的h值呢。这个在很多论文都进行了研究，但是是一个比较难的问题，实际中，可以通过调节h值进行测试。也可以看出，希尔排序解决了插入排序在乱序情况下移动困难的问题。并且实践也证明，希尔排序对于中等大小的数组的运行时间是 可以接受的，并且也不需要额外的内存空间。

归并排序

通过希尔排序，可以知道，其思想是通过控制全部对象中间隔长度为h的保持有序。但基于此是否还可以想到，能否通过一直保证部分有序，最终实现全局有序呢。归并排序通过这样的思想。首先给的的对象数组，一分为二，然后有两个子数组对象，通过保证两个子数组对象有序，然后将结果进行归并，从而达到全局有序。也就是说，归并排序通过分治的思想，最后达到全部对象有序。

其实想法是比较简单的，但实现起来却要考虑很多问题。比如说，对于一个很长的大数组来说，如果每次归并都要创建一个新数组来进行存储归并结果，这导致很大的空间浪费，因此，在这可以考虑原地归并的思路，也就是创建一个和原数组大小一样的数组，进行每次的归并存储。归并排序的代码如下

 private static Comparable[] aux;
    //将两个已排序数组对象进行归并
    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        for (int k = 0; k <= hi; k++) {
            aux[k] = a[k];
        }
        for (int k = 0; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }
    //排序
    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        //整个进行排序
        sort(a, 0, a.length - 1);
    }
​
    private static void sort(Comparable[] a, int lo, int hi) {
        if(hi <= lo) return;//递归出口
        //二分
        int mid = lo + (hi-lo)/2;
        sort(a, lo, mid);//保证左边有序
        sort(a, mid+1, hi);//保证右边有序
        merge(a, lo, mid, hi);//进行归并
    }

上述是一个自顶向下的归并排序，也就是从整个数组为开端，一步一步的分治，从而达到全部排序的目的。当然，也可以通过自下往上的方式达到目的，在此不再重复赘述。对于归并排序的算法复杂度，可以看见，归并排序似乎有点二分的感觉，是的，每一个都把数据进行二分，因此时间复杂度相对于插入或者选择肯定是降低了的，具体的时间复杂度不在详细讨论，后面会对各种算法的时间空间复杂度进行一个详细的论述。

总结

通过希尔和归并排序，其实要充分理解两种算法还是有一定的难度的，但最重要的是，理解两种算法所带来的核心思想。希尔排序通过保持间隔值h为有序，从而修复了插入排序在乱序临近元素的冗余性。归并排序通过分治的思想，把大问题化解为小问题，通过一分为二的思想，从而解决了全局性问题。对于算法的认识，要充分认识算法在哪里有冗余性，这才是需要改进的空间。