从头学算法（四、排序）

数据结构及算法

说到排序，首先想到的就是冒泡排序了，可能是因为太初级太简单，而且一般面试也经常会问到。其实除此之外插入排序、选择排序、希尔排序也是比较基础常见的排序，稍微复杂一点的还有快速排序，也是最常用的排序方法。
这几天我单独抽出时间来研究了一下这些排序算法，下面我将按我的理解向大家展示这几个算法的区别，并配上我的实现代码。

1.冒泡排序

所谓冒泡排序，是通过循环两两对比，小数前移实现的。
首先我们给定一个数组{ 1, 9, 38, 29, 16, 101, 265, 4, 78}
如何通过冒泡排序进行排序呢？
我们从末位开始两两对比，如果后一位比前一位小，则交换位置，否则不做处理，也就是个冒泡的过程。
由于在markdown上难以动态展示这个过程，我在纸上画一下排序过程：

通过这个图大家大概已经知道冒泡排序的过程了，那具体如何通过代码实现呢，以下是我的代码实现：

static int[] data = { 1, 9, 38, 29, 16, 101, 265, 4, 78};
private static void bubbleSort(){
    int i,j,temp;
    for(i=0;i<data.length-1;i++ ){
        for(j=data.length-1;j>i;j--){
            if(data[j]<data[j-1]){
                temp = data[j-1];
                data[j-1] = data[j];
                data[j] = temp;
            }
        }
    }
}

而在上一节，我在LeetCode Two Sum问题中提到的，正序冒泡倒序冒泡的问题，其实就是第二层循环条件写法的区别，实际上第一层循环也可以逆序，如果你对冒泡排序很熟悉了，反向冒泡也是可以的，要学以致用，学习算法切忌生搬硬套要懂得变通。
接下来我说下如果第二层循环改成正序的排序情况，
也就是改成下面的代码：

     for(i=0;i<data.length-1;i++ ){
        for(j=0;j<data.length-1-i;j++){
            if(data[j+1]<data[j]){
                temp = data[j];
                data[j] = data[j+1];
                data[j+1] = temp;
            }
        }
     }

初始时：1, 9, 38, 29, 16, 101, 265, 4, 78
第一次循环结束：1,9,29,16,38,101,4,78,265
第二次循环结束：1,9,16,29,38,4,78,101,265
第三次循环结束：1,9,16,29,4,38,78,101,265
第四次循环结束：1,9,16,4,29,38,78,101,265
第五次循环结束：1,9,4,16,29,38,78,101,265
第六次循环结束：1,4,9,16,29,38,78,101,265

从这种情况看的话，倒序只需三次循环，而正序则用了六次循环，这主要是因为有一个很小的数在数组的末端，对于这个例子来说就是“4”，如果倒序的话，4在一层循环中无限前推，直到落位。而正序的话，4就比较尴尬了，在其余位置都已排序完成之后，一次循环只能前移一个身位。

此时你有没有深入想一下为什么呢，因为冒泡排序是小数前移，如果第二层循环正向向前的话，移完一次，然后就跟当前这次循环没什么关系了。而第二层循环逆序就不一样了，你交换一次，当前的循环可以一直前推你的交换项，直到条件不满足，结束。

OK，关于冒泡排序大概就说这么多，最基础的排序方法，一定要熟练掌握。

2.插入排序

插入排序与冒泡排序有点类似，以至于很多人写着写着就把两个给写混了，因为它们都有两两对比交换位置的过程。
其实插入排序的思路与冒泡排序是不一样的，插入排序的核心是找到“插入点”，冒泡排序是通过一直遍历整个数组逐步排序的过程。这时候就需要对两种排序进行深入理解了，我在最开始分析这两个排序的时候也花了一些功夫。下面我会尽我所能详细讲解一下插入排序，并比较一下与冒泡排序的异同。
我们依然采用之前的数组{ 1, 9, 38, 29, 16, 101, 265, 4, 78}来了解插入排序的过程：
初始顺序：1,9,38,29,16,101,265,4,78
第一次插入：1,9,29,38,16,101,265,4,78
第二次插入：1,9,16,29,38,101,265,4,78
第三次插入：1,4,9,16,29,38,101,265,78
第四次插入：1,4,9,16,29,38,78,101,265
排序完成。
现在附上实现代码：

    static int[] data = { 1, 9, 38, 29, 16, 101, 265, 4, 78};
    private static void insertSort(){
        int i,j,temp;
        for(i=0;i<data.length;i++){     //  1 外层循环
            temp = data[i];
            j = i-1;
            while(j>=0&&temp<data[j]){      //  2 依次交换位置，获取最前面的交换项j 
                data[j+1] = data[j];
                j--;
            }
            data[j+1] = temp;       // 3  交换当前循环项与插入点位置
        }
    }

我记得在大学的时候看过直插排序的代码，只是当时没有看懂。现在看来，插入排序的设计还是非常巧妙的，如果我没有见过插入排序，让我自己实现一个插排，估计我是写不成这样的。
那我们就研究一下这个经典的插排算法，它的核心就是：除去第一项无需比较，其余项都要通过循环与前面所有项进行对比，如果前面有比它大的数则交换位置，看起来像是一次就位的，其实是相邻元素循环两两交换的结果。
这样说感觉还是太抽象，我举个比较容易的例子：
比如一个基本有序的数组{1,3,4,5,6,7,2}进行插入排序，因为前面六项均为有序项，所以在i=6的时候才会进行排序，接下来会进入while循环，也就是代码注释中2的位置，while循环里面进行持续交换，2-->7 ， 2-->6 ， 2-->5 ， 2-->4 ， 2-->3，每替换一次，j--，也就是前移一位，通过循环结束时j的值获取到最后一次替换的元素位置，最后执行代码中注释3，在插入点插入元素2。整体来看，看上去是直接把2插入1和3之间一样。
这时候你有没有想到，这种情况和冒泡排序基本上是一模一样的，同样的数组，我们采用冒泡排序走一遍：
外层循环i=0的时候，逆序冒泡，2-->7 ， 2-->6 ， 2-->5 ， 2-->4 ， 2-->3，这大概是最舒服的冒泡了，从尾直接冒到头，一次循环搞定。
然而这并不是你把这两个排序搞混的理由，你要深入理解这两个排序。
我们再换一个数组作为例子：{12,43,150,78,32,210,123}
这个用冒泡排序的话，第一次循环排序结果：12,32,43,150,78,123,210
实际上，冒泡排序关注面比较宽泛，只是大体上进行整体修正，存在两两相邻元素前<后，则互换位置，而以上123与210交换位置后，实际上前面还有150。对于冒泡排序来说，本次循环关注不到这种跳跃的不相邻的元素排序，需要通过之后的循环进行处理。
而对于插入排序而言，如果已经在找123的插入点了，那说明123之前的所有元素已经有序了。如果你不理解我这句话，从头看一下示例中插排过程。也就是说，插入排序是从前到后逐步有序的过程。它的初始关注面并不像冒泡排序那么广，但是它能保证已经排过的元素是有序的。而冒泡排序虽然初始关注面广，但并不保证有序。

3.选择排序

相对来说，选择排序就好理解了，就是遍历整个数组中是否存在比当前元素小的元素，若存在则交换位置。
选择排序过程如下：
初始顺序：1,9,38,29,16,101,265,4,78
第一次替换结果：1,4,9,38,29,16,101,265,78
第二次替换结果：1,4,9,16,29,38,101,265,78
第三次替换结果：1,4,9,16,29,38,78,265,101
第四次替换结果：1,4,9,16,29,38,78,101,265
排序完成。

代码如下：

    static int[] data = { 1, 9, 38, 29, 16, 101, 265, 4, 78};
    private static void selectSort(){
        int i,j,k,temp ;
        for(i=0;i<data.length;i++){
            k = i;
            for(j=i+1;j<data.length;j++){
                if(data[j]<data[k]){
                    k = j;
                }
            }
            if(k!=i){
                temp = data[i];
                data[i] = data[k];
                data[k] = temp;
            }
        }
    }

以上代码中k接收最小值的下标，如果存在更小值，则将最小元素下标重新赋值给k，直到没有更小值，之后进行元素替换，达到排序目的。

4.希尔排序

希尔排序听起来没有其它几个排序那么熟悉，其实它是插入排序的升级版。
我们在上面介绍插入排序的时候，你有没有意识到这点：在处理靠后的元素时，其实前面的元素已经有序了，但是后面的元素还是要不停的与前面交换元素来达到最终落到插入点。这是非常低效的。
我开始看希尔排序的时候出现了误解，想象成了归并排序，以为希尔排序根据增量将数组分为若干组之后将若干组分别进行插入排序，最后归并。实际上，希尔排序根据增量分组的含义并非如此，下面我向大家展示希尔排序的过程：
初始：1,9,38,29,16,101,265,4,78

设置增量为d=4；，记得d < n，第一次分组如下：
1,9,38,29,16,101,265,4,78
1---------16
  9----------101
    38-----------265
       29------------4
结果：1,9,38,4,16,101,265,29,78
再设置增量d=2,第二次分组如下：
1,9,38,4,16,101,265,29,78
1---38---16-----265----78
  9----4----101-----29
结果：1,4,16,9,38,29,78,101,265
再设置增量d=1，第三次结果如下：
1,4,9,16,29,38,78,101,265

OK,我们刚刚完成了希尔排序的整个过程，也是清楚了希尔排序的思路：首先要取一个增量，增量的选取是整个排序的关键，实际上增量的最优选取是一门非常复杂的数学难题，我们姑且采取d=n/2作为增量，然后再取一个较小的增量进行排序，直到d=1最终排序完成。当d=1时，其实就是插入排序了，任何数组都可以直接排序完成，前面的排序过程只是为了最后d=1时进行排序时，整个数组已经基本有序。因此除了用shell的名字命名之外，也就不难理解希尔排序又称为缩小增量排序了。
现在我们清楚了，希尔排序根据增量分组并非是简单将原数组进行切分成若干子数组，而是数组中所有距离为d的倍数的记录分为一组，增量d其实也就是分组的数量。
我们知道，插入排序是稳定的。但是由于希尔排序这种多次分组的特性，导致相同元素可能会在不同的插入排序中各自移动，这样相同元素的相对位置就会发生变化，所以希尔排序是一个不稳定的排序。
由于希尔排序代码简短，容易实现，且执行效率相对较高，没有比较严苛的效率要求时基本都可以采用。
下面我们就来用代码写一下希尔排序：

private static void shellSort(){
        int a = data.length;
        int i,j,k,temp;
        while(true){
            a = a / 2;
            for(i = 0;i < a;i ++){
                for(j = i + a ;j < data.length;j += a){
                    temp = data[j];
                    k = j - a;
                    while(k >= 0 && temp < data[k]){
                        data[k + a] = data[k];
                        k -= a ;
                    }
                    data[k + a] = temp ;
                }
            }
            if(a == 1){
                break;
            }
        }
    }

如果你还没理解透彻插入排序，看到这几层代码可能有点懵逼，不过咱们已经把插入排序给讲解完了。在此基础上再来看希尔排序，其实不过就是在插入排序之外加了一个增量分组的循环而已。

5.快速排序

快速排序如其名，突出一个快。快速排序时间复杂度可以达到O(nlogn),也是实际应用中用的最多的算法。相对其他的基础排序，快速排序就显得稍微复杂一些，手写快速排序还是有一些难度的。也正是因为这样，快排成为很多公司面试的考察点，而少有冒泡之类的考察，毕竟写个冒泡插排什么的也体现不了真实水平。
快速排序的思路如下：
1.先取一个数作为基准，一般我们默认选择第一个数。
2.进行分区，将大于这个数的全部放到它的右边，小于等于这个数的放到它的左边。
3.递归过程，左右区间重复步骤2，直到各区间只有一个数止。
这个过程体现了“分治”的思想，所以快排也称为分治法。
接下来我们看一下快速排序的过程：
初始值我们就不采用我们一直在用的数组了，因为第一个数字是1，囧。

我们换一个数组{6 8 7 9 0 1 3 2 4 5}
将6作为基准数，倒序寻找小于6的数字，交换位置：
5<6 交换位置：5 8 7 9 0 1 3 2 4 6
正序找比6大的数，8>6 交换位置：5 6 7 9 0 1 3 2 4 8
之后4<6: 5 4 7 9 0 1 3 2 6 8
7>6: 5 4 6 9 0 1 3 2 7 8
2<6: 5 4 2 9 0 1 3 6 7 8
9>6: 5 4 2 6 0 1 3 9 7 8
3<6: 5 4 2 3 0 1 6 9 7 8
第一轮排序结束。6之前都比6小，6之后都比6大
再分别对 5 4 2 3 0 1 和 9 7 8 分别重复上述步骤进行排序。
最终有序。

下面我们用代码实现快速排序：

private static void quickSort(int data[], int low, int high){
    int i, j, temp;
    temp = data[low];
    if(low < high){
        i = low;
        j = high;
        while(i < j){
            while(i < j && data[j] >= temp)     //倒序找小数
                j --;
            data[i] = data[j];
            while(i < j && data[i] <= temp)     //正序找大数
                i ++;
            data[j] = data[i]; 
        }
        data[i] = temp;
        quickSort(data, low, i - 1);
        quickSort(data, i + 1, high);
    }
}

其实快排理解了之后再写起来就没有那么复杂了，核心就是i、j正序倒序双向与基准位进行逐步替换，基准位左右区间递归的过程。

6.归并排序

有了上面快速排序分治的思路，我们再来看一下归并排序。
归并排序在速度上仅次于快速排序，时间复杂度为O(nlogn)，是一种稳定的的排序。适用于整体无序， 子序列相对有序的数组。
在归并排序之前，如何归并两个有序数组呢？
我翻出了我之前在没有任何参照的情况下写出的代码demo：

package com.lxy.testij;
/**
 * Created by coldxiangyu on 2016/9/12.
 */
public class MergeSort {
    static int[] a = {1, 4, 5, 8, 20, 22, 33, 44};
    static int[] b = {2, 3, 6, 9};
    private static void merge(){
        int[] k = new int[a.length + b.length];
        int n = 0;
        int i = 0, j = 0;
        while(i < a.length && j < b.length) {
            if (a[i] < b[j]) {
                k[n] = a[i];
                i++;
                n++;
            }else{
                k[n] = b[j];
                j++;
                n++;
            }
        }
        if(a.length > b.length){
            for(int p = i;p < a.length;p++){
                k[n++] = a[p];
            }
        }else{
            for(int a = j;a < b.length;a++){
                k[n++] = b[a];
            }
        }
        for(int m = 0;m < k.length; m++) {
            System.out.print(k[m] + " ");
        }
    }
    public static void main(String[] args){
        merge();
    }
}

虽然以上代码可以实现两个有序数组的合并，但是足足写了40行，现在看到简直是太臃肿了。尤其是后边通过比较两个数组的长度进行对数组k的赋值，也是没谁了。
不过思路上面的还是很清晰的，这也是我把它贴出来的原因：比较两个数组第一个元素，小值赋给新数组，而后将此值从对应的数组中拿掉，直到其中一个数组为空时，将另一数组剩余值赋给k即可。
merge方法优化如下：

private static void merge2(){
    int[] k = new int[a.length + b.length];
    int n = 0, i = 0, j = 0;
    while(i < a.length && j < b.length) {
        if (a[i] < b[j]) {
            k[n++] = a[i++];   //写法优化
        }else{
            k[n++] = b[j++];    //写法优化
        }
    }
    while (i < a.length)                    //此
        k[n++] = a[i++];                    //处
    while (j < b.length)                    //优
        k[n++] = b[j++];                    //化
    for(int m = 0;m < k.length; m++) {
        System.out.print(k[m] + " ");
    }
}

优化之后，代码简短了很多，用两个while循环进行剩余代码的依次赋值。
到了这里，归并排序的基础也就打好了。
归并排序的思路就是将数组进行循环分组，直至分组数据只有一个元素，那么这个分组已经有序，相邻分组直接合并即可。
归并排序的过程我在网上借鉴了一张图，很直观的展示了归并排序拆分、合并的过程。
图片地址：http://images.cnblogs.com/cnblogs_com/flyingbread/MergeSort.jpg

下面附上实现代码：

private static void Merge(int[] array, int low, int mid, int high) {
        int i = low; // i是第一段序列的下标
        int j = mid + 1; // j是第二段序列的下标
        int k = 0; // k是临时存放合并序列的下标
        int[] array2 = new int[high - low + 1]; // array2是临时合并序列
        // 扫描第一段和第二段序列，直到有一个扫描结束
        while (i <= mid && j <= high) {
            // 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
            if (array[i] <= array[j]) {
                array2[k++] = array[i++];
            } else {
                array2[k++] = array[j++];
            }
        }
        // 若第一段序列还没扫描完，将其全部复制到合并序列
        while (i <= mid) {
            array2[k++] = array[i++];
        }
        // 若第二段序列还没扫描完，将其全部复制到合并序列
        while (j <= high) {
            array2[k++] = array[j++];
        }
        // 将合并序列复制到原始序列中
        for (k = 0, i = low; i <= high; i++, k++) {
            array[i] = array2[k];
        }
    }
    private static void MergePass(int[] array, int gap, int length) {
        int i = 0;
        // 归并gap长度的两个相邻子表
        for (i = 0; i + 2 * gap - 1 < length; i = i + 2 * gap) {
            Merge(array, i, i + gap - 1, i + 2 * gap - 1);
        }
        // 余下两个子表，后者长度小于gap
        if (i + gap - 1 < length) {
            Merge(array, i, i + gap - 1, length - 1);
        }
    }
    private static int[] sort(int[] list) {
        for (int gap = 1; gap < list.length; gap = 2 * gap) {
            MergePass(list, gap, list.length);
        }
        return list;
    }
    public static void main(String[] args){
        int[] array = {9, 1, 5, 3, 4, 2, 6, 8, 7};
        sort(array);
    }

复杂一点的排序还有桶排序、堆排序、多路并排等等，我们稍后研究。