极客算法训练笔记(六)，十大经典排序之希尔排序，快速排序

抛砖引玉

十大经典排序算法江山图

排序算法的衡量指标我这里不再重复，上一篇我已经列举分析的很清楚了，但是非常重要，没看到我上一篇的小伙伴墙裂推荐，这里给一个直通车票极客算法训练笔记(五)，十大经典排序之冒泡，选择，插入排序。

冒泡，选择和插入排序，它们的时间复杂度都是O(n2)，比较高，适合小规模数据的排序，当有大规模的数据需要排序的时候这三种排序算法就有点吃不消了，所以需要进行优化，先来看看优化的思路：

首先，冒泡，选择和插入排序的第一步都是全部遍历，要想再有突破，将平均时间复杂度降低到O(n log n)，那肯定不能从头遍历了，考虑一下部分遍历。
其次，排除弟中弟的选择排序，分析江山图得知冒泡排序和插入排序的时间复杂度，在最好情况和最坏情况下差了一个指数级别，这个地方有很大的优化空间让大神们发挥。

实际上，欲抱琵琶半遮面的希尔排序和大概是个程序员都听说过但大部分人都不清楚的快速排序，分别就是插入排序和冒泡排序的变种，而且这两个排序分别前后脚，一个在1959年另一个于1960年问世。

希尔排序

鉴于网上很多文章上来就讲希尔排序是什么样的，但是都没有说明为什么会有这个版本排序，怎么演变过去的，所以这里我来分析一下，有不同的意见欢迎分享。

十大排序将军都有正经的名字，就这个希尔排序是个洋名字，想必大家猜也猜得到，是用这个算法的提出人希尔（Donald Shell）名字命名的。学算法都辣么难，打破固有的思维模式，创造一个算法那就更加了不起了，希尔一个小小的改动就把插入排序的时间复杂度从指数级别降下来了，把牛皮打在公屏上（插入排序去看我的上一篇，上面可坐直通车）。

算法描述

·优化依据：插入排序在最好情况下，数据都是有序时，遍历一次数据即可时间复杂度为O(n)；最坏情况下刚好数据倒序时为(n^2-n)/2即时间复杂度O(n^2)，可知插入排序算法时间复杂度到底是 n 还是 n^2 和原始数据是否有序息息相关，原始数据有序的话，插入时比较次数越少，挪动的位置也越少（例子：如果倒序，最后一个数据要一个一个和前面的比较大小，挪动N-1次，才可以到最前面）。

希尔优化思路：所以，希尔就是从这个点着手优化的，先将整个数组进行宏观调控，使用分组的方式，分组策略使用一个递减序列，每组依然使用插入排序算法进行组内排序，最后将分组都组合起来，这样局部宏观调控之后每组都有序即局部有序，局部调控的效果是可喜的（看看下图一个完全倒序数组第一遍宏观调控的效果）；一直分组下去，直到分组为1，组内就是全部元素了，分组越少，组内成员就越多，局部有序元素就越多，当分组为1的时候，全部元素都是一组，而且这组已经被宏观调控的大致有序，最后这组仍然使用插入排序算法进行微调，即全部有序，全排序。

10长度完全倒序数组，按照从小到大排序，分10/2=5组：

宏观调控效果

每组都有序了，大的元素几乎都被调到后面去了。再往后细分组5/2=2，2/2=1组，最后全排序了。
算法思想

将数组分为 h 组，初始 h 一般定为 n 的1/2或者1/3，交换间隔为 h 的元素进行局部排序，数据顺序不对可以直接跳过 h 个位置一步“交换”到前面去，每次使得任意间隔为 h 的元素都是有序的，nice哇。然后每次遍历 h/2, 直到 h=1, 组越分越小，当 h=1 的时候，整个数组已经被调整到非常有序了，再使用我们的插入排序算法进行微调，bingo，全排序！

抛出概念帮助理解和总结，希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（h就是增量，一直变小），上面提到的数组称为 h 有序数组，一个 h 有序数组就是 h 个互相独立的有序数组编织在一起组成的一个完整数组。
动图演示

希尔排序
- 颜色相同的代表同一组
- 前两遍都是宏观调控局部排序，只有数据交换没有挪位操作
- 最后一遍是插入排序，微调（具体的看上一篇朋友）
图解动图：
1. 第一遍
  
  第一遍
  
  首先第一组84默认有序，50和84比较，插入到84前面；接着第二组，83默认有序，70和83比较，70插入到83前面.....
2. 第二遍
  
  第二遍
  1. 第三遍
    
    分组 h=2/1，即分组为1，只有一组，也就是本数组全部进行插入排序
    
    第三组
    
    这个自不用说，直接就是此数组的插入排序，画图解可真的费劲。
  2. 为什么第一遍，第二遍不需要挪位？
    
    第一遍每组只有2个元素，是在本组使用插入排序，直接插入到前面就可了，不用挪位，但是还是插入排序算法。
    
    第二遍是因为我这组数据，在第二遍每组都是有序的，也不需要挪位插入，但是动画可看出是比较了的。
    
    第三遍可以很直观的看出来是插入排序算法了。

代码实现

理解了上面的，代码还不是褒义信手拈来，这里采用自顶向下的写法，来撸算法。

先把上篇插入排序的算法拿过来对比一下，就可以看到不是是我上面说的那样，插入排序代码：

public class InsertSort {
    public static int[] insertSort(int[] arr) {
        if(arr == null || arr.length < 2)
            return arr;

        int n = arr.length;
        // 下标为0的数默认是有序的，从下标为1的数开始遍历，将其放入他该去的地方
        for (int i = 1; i < n; i++) {
            // 申请一个变量记录要插入的数据，也就是动图中红色的元素
            int tmp = arr[i];

            // 从已经排序的序列最右边的开始比较，找到比其小的数，即动图中绿色的元素序号
            int j = i;
            // 红色元素下标大于0，要插入元素与遍历到的元素满足大小关系，遍历到的元素往后挪位腾位置        // 继续遍历，直到不满足大小关系停止，这个地方就是它的位置
            // 即红色元素小于绿色元素时，绿色元素挪位
            while (j > 0 && tmp < arr[j - 1]) {
              // 绿色元素往后挪一位
                arr[j] = arr[j - 1];
                j--;
            }

            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
        return arr;
    }
}

希尔排序代码如下：

public class ShellSort {
    public static int[] shellSort(int arr[]) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        int n = arr.length;
        // 对每组间隔为 h 的元素进行排序，刚开始 h = n / 2;
        for (int h = n / 2; h > 0; h /= 2) {
            // i代表第几组，对各个局部分组轮流进行插入排序
            for (int i = h; i < n; i++) {
                // 轮流对每个分组进行插入排序
                insertSort(arr, h, i);
            }
        }
        return arr;
    }

    /**
     * 局部插入排序
     * @param arr 原数组
     * @param h 分组内元素个数，分组数，间隔数，递增数; 例如栗子中第一次分组 f=5 是 {arr[0],arr[5]]} ，{arr[1],arr[6]]}， {arr[2],arr[7]]} ......
     * @param f 每个分组的第二个元素，默认第一个元素有序，从第二个元素开始排
     */
    private static void insertSort(int[] arr, int h, int f) {
        int n = arr.length;
        // 下标为0的数默认是有序的，从下标为1的数开始遍历，将其放入他该去的地方
        for (int i = f; i < n; i++) {
            // 申请一个变量记录要插入的数据，也就是动图中取出来的元素
            int tmp = arr[i];

            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            // 原本插入排序间隔 1 改为间隔 h，上一篇插入排序是 j>0，其实和 j>=1 等价，这里是 j>=h 不难理解
            while (j >= h && tmp < arr[j - h]) {
                // 在局部数组中后挪一位
                arr[j] = arr[j-h];
                j -= h;
            }

            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
    }
}

看代码可知，插入排序几乎是一样的，只不过改成了分组插入排序的逻辑，1变成了h而已。

稳定性分析

不稳定。

首先我们知道插入排序是稳定的，因为插入排序每次插入一个数据都能保证他的顺序是相对有序，不必被相同大小元素打乱了顺序，他保证了排好序的那边分区的有序性。

但是希尔排序只能保证分组内的元素有序，相同大小元素，排在很后面的可能在一次分组排序中直接被调到了前面，因此排序就会乱。例如数组arr为 3 1 1 2，按照希尔排序，第一次分组 [arr[0], arr[2]]，[arr[1],arr[3]] 即[3，1]，[1，2]，第三个 1 直接去了前面。
时间复杂度分析

最好和最坏情况下都一样，具体值看看江山图，由于推算方法过于复杂这里不做具体推算，感兴趣的可以去看相关的论文。

快速排序

百度百科说快排是冒泡排序的变种，我找了全网也没找到为什么。我很讨厌别人跟我说，xxx，这是结论，但是又不告诉我为什么，不是我天生反骨不服管教，一个东西总不可能凭空出现，哪怕说一说背景来历也比尬看代码好，花了半条命看懂了还记不住，我喜欢探寻物于物之间的联系，这对于拓展和帮助记忆都是非常有趣的（同意的评论区扣1）。

快排利用了分治的思想，分而治之，分治算法的基本思想是将一个规模为N的问题,分解成K个规模较小的子问题,这些子问题相互独立且问题性质相同。求解出子问题的解,合并得到原问题的解。拆分问题总不可能手脚并用一个个拆分，因此分治算法大多采用递归实现。

算法描述

对A[p....r]进行快速排序的分治过程：

分解：选择一个枢轴(pivot)元素划分数组。将数组 A[p..r] 划分为两个子数组(可能为空) A[p..q-1] 和 A[q+1..r]，使得 A[q] 大于等于A[p..q-1] 中的每个元素，小于 A[q+1..r] 中的每个元素。计算下标 q 的值也是划分过程的一部分； 求解：通过递归调用快速排序，对子数组 A[p..q-1] 和 A[q+1..r] 分别排序； 合并：子数组在原地排序，故无需合并操作，数组 A[p...r] 已经有序。
算法思想

每次选一个pivot（分区值），其他数依次和 pivot 比较，大的放右边小的放左边，然后再对左边和右边的两组数，分别选出pivot，重复比较，大的放左边，小的放右边；重复步骤，直到最后都变成单个元素，整个数组就成了有序的序列。

为什么说快排是冒泡排序的变种？

首先，每次重复，pivot 一定会有序，这点和冒泡排序很像，冒泡排序也是每次遍历冒泡，都会有一个元素排序正确；再者，快排也是两两比较，交换位置，和冒泡排序也是相似的，快排的核心交换代码和冒泡神似，这些点可说快速排序是冒泡排序的变种。

动图演示

明黄色代表此次遍历选定的 pivot，每次选数组第一个数作为 pivot，本数组 pivot 分别为3，38，19，4，26，27，46，47，50；
暗黄色代表已经排好序的元素；
绿色代表比基准值 pivot 小的数据，紫色代表比基准值 pivot 大的数据，绿色子数组和紫色子数组有会进行切割数组排序，直到子数组只有一个元素为止；
每次遍历过后，至少有一个元素会是有序的， pivot 元素一定有序。

图解分析：

图解还是用上面数组里的数据做分析，动图里面元素太多了。

快速排序

明黄色代表此分组选定的 pivot, 暗黄色代表已经排好序的，当分组内只有一个元素不需要再排序。

可知，每次遍历之后，pivot 是一定有序的，其他元素如果组内只剩下一个元素也有序。

代码实现

每次取数组第一个元素作为基准值 pivot，设定数组基准值 pivot 右边第一个数为mark用来存储比 pivot 小的元素，遍历数组；
元素大于 pivot，正常，继续遍历；
遍历元素小于 pivot，将此元素放入mark位置，即此元素与mark所指元素互换，选择mark后面一个元素位置继续存储小于pivot值的元素；
一趟遍历下来，mark存储了所有比第一个元素pivot小的元素，将pivot与mark最后一个元素交换，使得pivot去中间，pivot左边的都比它小，右边的都比它大

public class QuickSort {
    public static int[] quickSort(int[] arr) {
        return sort(arr, 0, arr.length-1);
    }

    public static int[] sort(int[] arr, int left, int right) {
        // 递归终止条件，子数组长度为1
        if (left >= right) {
            return arr;
        }
        //获取中轴元素所处的位置，即 pivot 的值
        int pivot = partition(arr, left, right);
        //切割,递归先排左边数组
        arr = sort(arr, left, pivot - 1);
        //切割,递归排好右边数组
        arr = sort(arr, pivot + 1, right);
        return arr;
    }

    private static int partition(int[] arr, int left, int right) {
        // pivot 选取数组第一个元素
        int pivot = arr[left];
        // mark 初始选取 pivot 右边第一个元素，存储小于 pivot 的元素， mark 最后指的元素就是小于 pivot 的数组最后一个值
        int mark = left + 1;
        for (int i = mark; i <= right; i++) {
            // 如果遍历的元素小于 pivot 元素，和 mark 元素交换
            if (arr[i] < pivot) {
                int temp = arr[i];
                arr[i] = arr[mark];
                arr[mark] = temp;
                // mark 元素向右挪一位
                mark ++;
            }
        }
        // 交换到最后 mark 多加了1，需减去;
        mark -= 1;
        // 如果left==mark，表示没有交换过，没有比pivot小的值，这个pivot即为一组，直接返回 mark
        if (left < mark) {
            // pivot 所指第一个元素和 mark元素交换，即pivot元素和小于pivot的最后一个元素互换，使得 pivot 左边元素全部小于pivot
            arr[left] = arr[mark];
            arr[mark] = pivot;
        }
        return mark;
    }

}

这段代码是我完全根据动图来写的，便于大家看着动图理解的代码实现方式，实际上快排实现方式还可以用双指针法，有兴趣的可以自己实现一下。

稳定性分析

不稳定。

还是3 1 1 2数组分析，第一次分区 [2，1，1]， [3]，第二次分区[1，1，2]，[3]，这里两个 1 就调换了位置

时间复杂度分析

最好的情况下，如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，用递归树来表示如下图：

快排
```
第1层是n次，

第2层有2次递归，每次n/2次，共n次操作，

第3层有4次递归，每次n/4次，共n次操作，

……

（最后一层）第k层有k次递归，每次n/2^(k-1)次，共n次操作

由于递归结束的条件是只有一个元素，所以这里的**n/2^(k-1)=1**  =>  **k=logn+1** 

即递归树的**深度为logn**

时间复杂度=每层的操作次数*树的深度=nlogn 即：O(nlogn)；
```
最坏情况下，如果数组中的数据原来已经是有序的了，比如1，3，5，6，8。如果我们每次选择最后一个元素作为pivot，那每次分区得到的两个区间都是不均等的。我们需要进行大约n次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约n/2个元素，这种情况下，快排的时间复杂度就从O(nlogn)退化成了O(n2)。

原本是想这篇写四个算法的，但是没想到这两个算法写了这么多内容，因此这篇暂且写这两篇，归并排序和堆排序下一篇再写，如果有错误欢迎批评指正，另外欢迎大家关注我的公众号《阿甘的码路》，我是小魔女阿甘，交个朋友最好啦！