常用排序算法（二）

之前的文章讲解了三种时间复杂度为O(n^2)的简单排序算法，本篇介绍另外两种经典排序算法希尔排序和归并排序。这两种算法中，希尔排序理解起来不太容易，归并排序比较容易理解但代码量偏多。在面试的过程中被问到的几率比较小。

希尔排序

希尔排序是插入排序的一种，是对前一篇所讲直接插入排序的优化方法，又称缩小增量排序。
基本思想：将无序数组分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，对各个子序列进行插入排序；然后再选择一个更小的增量，再将数组分割为多个子序列进行排序直到选择增量为1，即使用直接插入排序，使最终数组成为有序。
增量的选择：在每趟的排序过程都有一个增量，至少满足一个规则 增量关系 d[1] > d[2] > d[3] >..> d[n] = 1 (n趟排序)。
增量的大小对排序算法性能也有影响，一般而言，增量的初始值设为(数组长度 / 2)之后的每趟排序中，数组长度变为之前的1/2，直到 增量为1时结束排序。
希尔排序过程比较复杂，这里有个短视频，可以帮助理解：http://v.youku.com/v_show/id_XMjU4NTcwMDIw.html
还是直接上代码吧：

public void shellSort(int[] nums){
    int increment = nums.length;
    int temp;
    while(true){
        increment = (int)Math.ceil(increment / 2);
        for(int i = 0; i < increment; i += increment){
            for(int j =i + increment; j < nums.length; j++){
                int k = j - increment;
                temp = nums[j];
                for(; k >= 0 && nums[k] > temp; k -= increment){
                    nums[k + increment] = nums[k];
                }
                nums[k + increment] = temp;
            }
        }
        if(increment == 1){
            break;
        }
    }
}

归并排序

归并排序运用了基础算法中的分治思想，将数先对半拆分为两个数组，在对分开的数组做拆分，以此类推直到拆分出的数组的长度为1时停止拆分开始归并。
归并的方式也很简单，就是创建一个大小为两个数组长度之和的新数组，然后两个数组都从头开始遍历，按顺序加入新数组，新产生的数组必定是排好序的，再将其与其他数组进行归并，直至整个数组排序完成。
思路很简单，但是代码量还是挺大的，虽然比不上堆排序，但毕竟堆排序相较于归并而言显得更加高级，相同的时间复杂度但空间复杂度堆排序优于归并排序。

归并过程

为了方便理解，减少代码量，本文给出归并排序的递归实现方式：

//归并的主方法
public int[] mergeSort(int[] nums, int low, int high){
    int mid = (low + high) / 2;
    if(low < high){
        mergeSort(nums, low, mid);
        mergeSort(nums, mid + 1, high);
        merge(nums, low, mid, high);
    }
    return nums;
}
//数组合并
public void merge(int[] nums, int low, int mid, int high){
    int[] temp = new int[high - low + 1];
    int i = low;
    int j = mid + 1;
    int cnt = 0;
    while(i <= mid && j <= high){
        if(nums[i] < nums[j]){
            temp[cnt++] = nums[i++];
        }else{
            temp[cnt++] = nums[j++];
        }
    }
    while(i <= mid){
        temp[cnt++] = nums[i++];
    }
    while(j <= high){
        temp[cnt++] = nums[j++];
    }
    for(i = 0; i < temp.length; i++){
        nums[i + low] = temp[i];
    }
}

本篇介绍的两种排序算法在面试中不常被问到，可能还没有在笔试中考到的频率高，但也希望理解其思想，不会写也得会说吧。