排序算法最强总结及代码实现（代号XQ手游）

在这里插入图片描述

前言

本文总结了常用的全部排序算法，内容包括：

排序算法的定义和思路
排序算法的代码实现：Python和Java，包括实现中需要注意的细节
排序算法性能分析：时间空间复杂度分析，稳定排序算法背诵口诀等
不同排序算法最佳使用场景

此文干货颇多，烦请收藏后慢慢研读。

面试知识点复习手册

此文属于知识点复习手册专栏内容，你还可以通过以下两种途径查看全复习手册文章导航：

关注我的公众号：Rude3Knife 点击公众号下方：技术推文——面试冲刺
全复习手册文章导航(CSDN)

-----正文开始-----算法性能分析

图中纠正：归并排序空间复杂度应该是O(n)，快排是O(logn)-O(n)

这里写图片描述

稳定性定义：

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

例如，对于如下冒泡排序算法，原本是稳定的排序算法，如果将记录交换的条件改成r[j]>=r[j 1]，则两个相等的记录就会交换位置，从而变成不稳定的算法。

再如，快速排序原本是不稳定的排序方法，但若待排序记录中只有一组具有相同关键码的记录，而选择的轴值恰好是这组相同关键码中的一个，此时的快速排序就是稳定的。

只需记住一句话（快些选一堆美女一起玩儿）是不稳定的，其他都是稳定的。

补充性能图：

这里写图片描述

不同情况下的合适排序方法

初始数据越无序，快速排序越好。

已经基本有序时，用直接插入排序最快。

在随机情况下，快速排序是最佳选择。

既要节省空间，又要有较快的排序速度，堆排序是最佳选择，其不足之处是建堆时需要消耗较多时间。

若希望排序是稳定的，且有较快的排序速度，则可选用2路归并排序，其缺点需要较大的辅助空间分配。

算法实现

基于比较的排序算法

冒泡排序

思路：

冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

步骤：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

Python:

Java:

选择排序

思路：

选择排序无疑是最简单直观的排序。它的工作原理如下。

步骤：

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。

Python:

Java：

插入排序

思路：

从左边第二个数开始，往前遍历，将大于他的数都往后一个个移位，一旦发现小于等于他的数，就放在那个位置（之前的数已经被移到后面一位了）

插入排序的工作原理是，对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

步骤：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果被扫描的元素（已排序）大于新元素，将该元素后移一位
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复步骤2~5

image

Python：

Java：

希尔排序（递减增量排序算法，实质是分组插入排序）

思路：

希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。

例如，假设有这样一组数，

如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

然后我们对每列进行排序：

将上述四行数字，依序接在一起时我们得到：

。这时10已经移至正确位置了，然后再以3为步长进行排序：

排序之后变为：

最后以1步长进行排序（此时就是简单的插入排序了）。

具体实现：外面套一个gap，while内做插入排序，并且将gap不断除2，直到小于0出循环

Python：

Java：

归并排序(递归合并)

思路：拆拆拆到单个数字，合并合并合并

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。

先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

再考虑递归分解，基本思路是将数组分解成left和right，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可。

image

Python：

Java：

快速排序

快速排序通常明显比同为Ο(n log n)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。可见掌握快排的重要性。

快排特点：

每经过一趟快排，轴点元素都必然就位，也就是说，一趟下来至少有关键字key节点在其最终位置，所以考察各个选项，看有几个元素就位即可。
逆序的数列，选择首位为key，则会退化到O（n^2），可以随机选择一个元素作为基准元素。

两种交换方法：

指针交换法：youtube视频：https://www.youtube.com/watch?v=gl_XQHTJ5hY （下图代码实现的方法，并且是两两交换，最后将key与left交换）

image

挖坑填数法：http://blog.csdn.net/morewindows/article/details/6684558 （key一开始就被挖坑填写了别的数，我认为第二种是做牛客网选择题时需要掌握的，应为选择题答案的排序结果通常是按照这种算法得到的排序结果）

快排优化方法：

https://blog.csdn.net/cpcpcp123/article/details/52739285

选择基准的方式：三数取中（median-of-three）

举例：待排序序列为：8 1 4 9 6 3 5 2 7 0

左边为：8，右边为0，中间为6.

我们这里取三个数排序后，中间那个数作为枢轴，则枢轴为6

下图分别对应第一种和第二种排序的中间结果：

这里写图片描述

Python(指针交换)：

Java(指针交换)：

Java(挖坑法)

非递归形式实现（栈）：和刚才的递归实现相比，代码的变动仅仅在quickSort方法当中。该方法中引入了一个存储Map类型元素的栈，用于存储每一次交换时的起始下标和结束下标。

每一次循环，都会让栈顶元素出栈，进行排序，并且按照基准元素的位置分成左右两部分，左右两部分再分别入栈。当栈为空时，说明排序已经完毕，退出循环。

该方法实现代码请参考程序员小灰：

https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653195042&idx=1&sn=2b0915cd2298be9f2163cc90a3d464da&chksm=8c99f9f8bbee70eef627d0f5e5b80a604221abb3a1b5617b397fa178582dcb063c9fb6f904b3&mpshare=1&scene=1&srcid=0813k35KHoSO42jGGrMx5oUA#rd

堆排序

参考：

http://blog.csdn.net/minxihou/article/details/51850001

https://www.2cto.com/kf/201609/549335.html

例题：相当帮助理解

https://www.nowcoder.com/test/question/done?tid=14276624&qid=56294#summary

image

思路：

父节点i的左子节点在位置(2*i 1)

父节点i的右子节点在位置(2*i 2)

子节点i的父节点在位置floor((i-1)/2)

堆排序构建堆的时间复杂度是N,而重调堆的时间复杂度是logN

堆可以分为大根堆和小根堆，这里用最大堆的情况来定义操作:

(1)最大堆调整(MAX_Heapify):

将堆的末端子节点作调整，使得子节点永远小于父节点。这是核心步骤，在建堆和堆排序都会用到。比较i的根节点和与其所对应i的孩子节点的值。当i根节点的值比左孩子节点的值要小的时候，就把i根节点和左孩子节点所对应的值交换，当i根节点的值比右孩子的节点所对应的值要小的时候，就把i根节点和右孩子节点所对应的值交换。然后再调用堆调整这个过程，可见这是一个递归的过程。

(2)建立最大堆(Build_Max_Heap):

将堆所有数据重新排序。建堆的过程其实就是不断做最大堆调整的过程，从len/2出开始调整，一直比到第一个节点。

(3)堆排序(HeapSort):

移除位在第一个数据的根节点，并做最大堆调整的递归运算。堆排序是利用建堆和堆调整来进行的。首先先建堆，然后将堆的根节点选出与最后一个节点进行交换，然后将前面len-1个节点继续做堆调整的过程。直到将所有的节点取出，对于n个数我们只需要做n-1次操作。堆是用顺序表存储的的代码可以先看：http://blog.51cto.com/ahalei/1427156 就能理解代码中的操作

注意：

从小到大排序的时候不建立最小堆而建立最大堆。最大堆建立好后，最大的元素在h[ 1]。因为我们的需求是从小到大排序，希望最大的放在最后。因此我们将h[ 1]和h[ n]交换，此时h[ n]就是数组中的最大的元素。

请注意，交换后还需将h[1]向下调整以保持堆的特性。OK现在最大的元素已经归位，需要将堆的大小减1即n--，然后再将h[1]和h[ n]交换，并将h[1]向下调整。如此反复，直到堆的大小变成1为止。此时数组h中的数就已经是排序好的了。

代码如下：

Python:

Java：

有空补

非基于比较的排序算法

基于比较的排序算法是不能突破O(NlogN)的。简单证明如下：

N个数有N!个可能的排列情况，也就是说基于比较的排序算法的判定树有N!个叶子结点，比较次数至少为log(N!)=O(NlogN)(斯特林公式)。

计数排序

计数排序在输入n个0到k之间的整数时(可以从a到b，不用非要从0开始，代码可以实现)，

时间复杂度最好情况下为O(n k),最坏情况下为O(n k),平均情况为O(n k),空间复杂度为O(n k)

算法的步骤如下：

1.找出待排序的数组中最大和最小的元素

2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项

3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）

4.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

当k不是很大时，这是一个很有效的线性排序算法。更重要的是，它是一种稳定排序算法，即排序后的相同值的元素原有的相对位置不会发生改变(表现在Order上)，这是计数排序很重要的一个性质，就是根据这个性质，我们才能把它应用到基数排序。

桶排序

假如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。这些数据全部在1—100之间。因此我们定制10个桶，然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中，并在每个非空的桶中进行快速排序。

因此，我们需要尽量做到下面两点：

(1) 映射函数f(k)能够将N个数据平均的分配到M个桶中，这样每个桶就有[N/M]个数据量。

(2) 尽量的增大桶的数量。极限情况下每个桶只能得到一个数据，这样就完全避开了桶内数据的“比较”排序操作。当然，做到这一点很不容易，数据量巨大的情况下，f(k)函数会使得桶集合的数量巨大，空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。

对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：
O(N) O(M(N/M)log(N/M))=O(N N(logN-logM))=O(N NlogN-N*logM)
当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

桶排序是稳定的。

基数排序

基数排序的思想就是将待排数据中的每组关键字依次进行桶分配。比如下面的待排序列：

278、109、063、930、589、184、505、269、008、083

我们将每个数值的个位，十位，百位分成三个关键字： 278 -> k1(个位)=8 ，k2(十位)=7 ，k3=(百位)=2。

然后从最低位个位开始(从最次关键字开始)，对所有数据的k1关键字进行桶分配(因为，每个数字都是 0-9的，因此桶大小为10)，再依次输出桶中的数据得到下面的序列。

930、063、083、184、505、278、008、109、589、269

再对上面的序列接着进行针对k2的桶分配，输出序列为：

505、008、109、930、063、269、278、083、184、589

最后针对k3的桶分配，输出序列为：

008、063、083、109、184、269、278、505、589、930

很明显，基数排序的性能比桶排序要略差。每一次关键字的桶分配都需要O(N)的时间复杂度，而且分配之后得到新的关键字序列又需要O(N)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2N) ，当然d要远远小于N，因此基本上还是线性级别的。基数排序的空间复杂度为O(N M)，其中M为桶的数量。一般来说N>>M，因此额外空间需要大概N个左右。

但是，对比桶排序，基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作，而桶排序在桶相对较少的情况下，桶内多个数据必须进行基于比较操作的排序。因此，在实际应用中，基数排序的应用范围更加广泛。

# 参考

稳定性解释：
https://baike.baidu.com/item/排序算法稳定性/9763250?fr=aladdin

性能分析与适应场景：
http://blog.csdn.net/p10010/article/details/49557763

动画：
http://blog.csdn.net/tobeandnottobe/article/details/7192953
http://www.webhek.com/post/comparison-sort.html

Python排序总结：
http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/

Java排序总结：
https://www.cnblogs.com/10158wsj/p/6782124.html?utm_source=tuicool&utm_medium=referral

-----正文结束-----

更多精彩文章，请查阅我的博客或关注我的公众号：Rude3Knife

全复习手册文章导航：通过以下两种途径查看