浅谈排序算法（中）

事实上，人类需要不断面对计算机科学所研究的一些高难度问题，在不确定性及时间有限、信息不全、情况瞬息万变等不利因素的干扰下做出决定。针对一些问题，即使最前沿的计算机科学也没能开发出永远不会犯错误的有效算法，有的情形似乎是任何算法都无法解决的。

——《算法之美》

浅谈排序算法（上）中介绍了冒泡、选择和插入三种排序方法，本文主要介绍希尔、快速和归并三种排序。

希尔排序

核心思想：

希尔排序是插入排序的改进版本，弥补了插入排序在某些情况下的缺点。

希尔排序定义了一个步长的概念，从大到小对步长进行切割，从而依次进行插入排序，最后完成整个排序操作。所以希尔排序也叫做缩小增量排序，它通过先设置一个增量n，大小为数组长度的一半，将间隔为n的元素视作一个组，然后对每个组内部的元素进行从小到大进行插入排序；然后再将增量n缩小一半，再次进行分组插入排序，直到增量n为1，因为增量为1的时候，所有的元素都为同一个组了。

希尔排序的核心在于先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

希尔排序动画演示

Java实现希尔排序

public static void shellSort(int[] arr){
    long start = new Date().getTime();
    // 定义步长
    for (int gap = arr.length / 2; gap > 0 ; gap /= 2) {
        for (int i = gap; i < arr.length; i++) {
            int insertIndex = i;
            int insertVal = arr[i];
            while (insertIndex -gap >= 0 && insertVal < arr[insertIndex - gap]){
                arr[insertIndex] = arr[insertIndex - gap];
                insertIndex -= gap;
            }
            arr[insertIndex] = insertVal;
        }
    }
    long end = new Date().getTime();
    System.out.println("消耗时间:" + (end-start) + "ms");
    for (int a: arr){
        System.out.println(a);
    }
}

优点:快，数据移动少。

缺点：不稳定，步长gep的取值是多少，应取多少个不同的值，都无法确切知道。

快速排序

基本思想:

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下

1. 选择一个基准元素,通常选择第一个元素或者最后一个元素,
2. 通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比 基准元素值小。另一部分记录的 元素值比基准值大。
3. 此时基准元素在其排好序后的正确位置
4. 然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

快速排序图示

Java实现快速排序

public static void fastSort(int[] arr, int left, int right){
    if (left >= right){
        return;
    }
    int l = left;
    int r = right;
    while (l < r){
        while (l < r && arr[r] >= arr[left]) r--;
        while (l < r && arr[l] <= arr[left]) l++;
        if (r==l){
            int temp = arr[r];
            arr[r] = arr[left];
            arr[left] = temp;
        }else {
            int temp = arr[r];
            arr[r] = arr[l];
            arr[l] = temp;
        }
    }
    fastSort(arr,left,r-1);
    fastSort(arr,l+1,right);
}

优点:极快，数据移动少.

缺点：不稳定

归并排序

核心思想：

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序算法稳定，数组需要O(n)的额外空间，链表需要O(log(n))的额外空间，时间复杂度为O(nlog(n))，算法不是自适应的，不需要对数据的随机读取。

工作原理：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

归并排序图示

Java实现归并排序

public static int[] mergeSort(int[] a,int low,int high){
    int mid = (low+high)/2;
    if(low<high){
        // 先拆分
        mergeSort(a, low,mid);
        mergeSort(a,mid+1,high);
        //左右归并
        merge(a,low,mid,high);
    }
    return a;
}
public static void merge(int[] a, int low, int mid, int high) {
    int[] temp = new int[high-low+1];
    int i= low;
    int j = mid+1;
    int k=0;
    // 把较小的数先移到新数组中
    while(i<=mid && j<=high){
        if(a[i]<a[j]){
            temp[k++] = a[i++];
        }else{
            temp[k++] = a[j++];
        }
    }
    // 把左边剩余的数移入数组
    while(i<=mid){
        temp[k++] = a[i++];
    }
    // 把右边边剩余的数移入数组
    while(j<=high){
        temp[k++] = a[j++];
    }
    // 把新数组中的数覆盖nums数组
    for(int x=0;x<temp.length;x++){
        a[x+low] = temp[x];
    }
}

优点：复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)，稳定。

缺点：需要与待排序序列一样多的辅助空间；对数据的有序性不敏感，若数据节点数据量大，那将不适合。