基础算法| 常用排序算法小结

日常吹水

说到这个算法，

可能瞬间大家就觉得那些灰机昏膏素什么的比这个生动活泼多了。

那么，正走在算法之路上的你，

是否还在苦苦寻求修仙之路？

是否被各种排序算法欺负得苦不堪言？

那还等什么，快进来看看

带你全程装逼加一路向西！

刺不刺激？高不高能？

＊

内容提要：

＊排序常用术语介绍

＊冒泡排序

＊选择排序

＊插入排序

＊希尔排序

＊归并排序

＊快速 排序

排序基础知识

⚫排序的定义

将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。说得再通俗点，比如将一个班的人（数据元素）按照身高（关键字）站位，高的站前面，矮的站后面咯。

⚫ 排序的分类

排序可分为内排序和外排序。

所谓内排序就是所有的数据和操作都在内存中完成。

而外排序就是说需要排序的数据太大，无法全部塞进内存，需要在内存和外存之间多次数据交换才能完成的排序。

⚫算法优劣的术语说明

⚫稳定：如果Ai=Aj，开始Ai在Aj前面，排完序之后Ai依然在Aj前面。

⚫不稳定：

如果Ai=Aj，开始Ai在Aj前面，而排完序以后Ai有可能跑到Aj后面去了。

⚫时间复杂度：一个算法执行完所消耗的时间。

⚫空间复杂度：执行一个算法需要消耗的内存空间大小。

⚫常见算法的复杂度及稳定性

好了看完上面一堆头(dan)疼的术语介绍，

接下来将为大家介绍几种常用的内部排序算法，

开始我们的表演。

1

冒泡排序(Bubble Sort)

⚫常规冒泡排序

冒泡排序算是比较好理解的了。想小编当年入门的时候，就是仰仗着冒泡大法，从此踏入红尘，一去不返……呃这个扯远了，为什么叫冒泡呢？这个后面再解释。为了更好的说明问题，还是用一个数组A[n]，以升序（降序方法一样）为例，来给大家一一讲解。

⚫基本原理：

1）从序列的最左边开始，将两两相邻的两个元素（例如A[0]和A[1], A[1]和A[2], A[2]和A[3]等等）进行比较。将小的放左边，将大的放右边。例如A[i] > A[i+1]，那么就交换A[i]和A[i+1]的位置。那么经过一轮比较交换以后，A[n]里的值必然是A[0]~A[n]中的最大值。

2） 对剩下的元素A[0]~A[n-1]也进行上述操作。完成后A[n-1]里面存的就是A[0]~A[n-1]中的最大值。

3） 不断对剩下的元素进行上述操作，直到剩下元素只有A[0]时，排序完成。

看不懂嘛？那来试试图片吧：

好了，讲完了基本原理，来看看具体代码是如何实现的吧。

可以看到，在冒泡后，相等元素的位置并不会改变。因此，冒泡算法是稳定的。

⚫ 冒泡排序改进版

此方法可称为定向冒泡排序，它和冒泡排序的不同之处在于，定向冒泡从左到右把最大数搬到最后面的时候，再反向从右往左把最小值搬到最左边。这种方法稍微比传统冒泡好上那么一丢丢。具体实施看代码。

不理解嘛？没关系，小编还为大家准备了动态图。

定向冒泡的优势，比如对序列{4, 5, 6, 7, 8, 2}排序，传统冒泡要访问5次序列，而定向冒泡排序只需要访问一次就OK了。

2

选择排序(Selection Sort)

说到选择排序，这个也是灰常易于理解的。相信大家看一眼基本原理就懂了。还是以数组A[n]与升序排列为例说明问题。

基本原理：

1）先从A[0]~A[n]中找最小的元素A[i]，交换A[0]和A[i]的位置。

2）再从剩下的元素A[1]~A[n]中找最小的元素A[j]，交换A[1]和A[j]的位置。

3）不断在剩下的元素中找最小的元素丢到开头，直到剩下最后一个元素。

还不懂？再来看看个图片：

代码哪能少？

选择排序每次将最小值丢到开头的时候，有可能会打乱相等元素的位置。因此，它是不稳定的。也注意区分其和冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

3

插入排序(Insertion Sort)

大家打过扑克牌嘛？我们在对手上的扑克牌进行排序的时候，是不是将右手上的牌插到左手上已经排序好的牌之间？这跟我们的插入排序是有点类似的。

还是以A[n]为例说明问题。

基本原理：

1）从A[0]开始，则A[0]可认为是已排序列。

2）取出下一个元素(比如A[1])，在已排序列中从右往左扫描，如果已排序列中的元素大于取出的元素，那么就将该元素（已排序列中的）往后挪一个位置。

3）直到在已排序列中找到一个小于等于取出元素的元素。将取出元素插入该元素（已排序列中的）后一个位置。

4）不断重复步骤2-3.直到所有元素都插入到已排序列。

还不明白？看看图片

请问代码在哪里？？？

亲，这么详细的注释，

别跟我说你看不懂

可以看出，关于相等元素，排序前后并不会改变他们的位置。因此，插入排序又是稳定的。

4

希尔排序(Shell Sort)

希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。其中希尔排序是基于以下几点做出改进的：

1）直接插入排序对于几乎排好的数据有着极高的效率。基本可以达到线性排序时的效率。

2）但是对于一般的乱序数据来说，直接插入排序由于每次只能将数据往后搬一位，从这点上来说它效率又是及其低下的。

基本原理：

1）将无序数据分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，对各个子序列进行直接插入排序；

2）然后再选择一个更小的增量，再将数据分割为多个子序列进行直接插入排序......

3）不断重复步骤2，直到最后增量变为1，即对所有数据使用直接插入排序（此时所有数据几乎都排好了，直接插入效率较高），最终排序完成。

唉，小编就不指望你们能看懂，还是来看看图片吧。

关于不同增量的选取对于希尔排序性能的影响，有不同的观点。这里就不过多赘述。

代码！代码！代码在哪里！！！？？？

值得一提的是，由于数据划分为多个区域，在每个区域中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱。因此希尔排序是不稳定的排序。

5

归并排序(Merge Sort)

小伙子，你造归并吗？

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。效率为O(nlogn)，1945年由冯·诺伊曼首次提出。归并排序的实现分为递归实现与非递归(迭代)实现。这里我们讨论递归实现。归并排序依赖于归并操作。归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

基本原理：

1）申请内存空间A，大小为两个已排序列之和。

2）设定两个指针，分别指向两个已排序列的首元素。

3）比较两个指针指向的元素大小，将小的那个元素丢进内存空间A。同时指向该元素的指针向前移动一位。

4）不断重复步骤3），直到任何一个序列的元素全被丢进空间A。那么就把另外一个序列剩下的所有元素丢进空间A。

Understand？别说了，看图吧。

兄弟，来，干了这段代码。

归并排序是稳定的算法。

6

快速排序(Quick Sort)

1

1

终于说到这个大boss了。为什么叫快速排序呢？额，这个倒不是因为它很快。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：开始选取一个基准数，通过一趟排序将基准数移到序列的合适位置，使得，左边的这部分都小于等于基准数，右边的部分都大于等于基准数，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

那么，对于一个序列，怎样才能使基准数移动到正确位置，以便能使左边的数都小于等于它，右边的数都大于等于它呢？还是以数组A[N]为例，为大家慢慢道来：

1）设置两个变量i、j，排序开始的时候：i=0，j=N；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；

5）重复第3、4步，直到i=j；

6）3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束。

还是来看看图吧：

聪明的同学已经发现了，当序列中的每个元素都归位的时候，整个序列也就都变得有序了。

看完了图解是不是感觉贼得劲儿了呢？？

看代码：

快速排序是不稳定的排序算法。

OK自此，常用的排序算法已经介绍完毕，今天的表演到此结束，谢谢大家。

最后再多说两句

这次内容量有点大啊

小伙伴们要耐下心来多看几遍

不懂就再多看几遍

最近天气变冷了，大家修仙学习的时候也多注意身体。

不要像小编一样……

最后谢谢大家的支持，共勉共进。

祝大家早日练就大佬的姿态

1

END

编辑：邓发珩（华中科技大学管理学院本科一年级，2638512393@qq.com，个人公众号:程序猿声）

代码: 邓发珩

指导老师：秦时明岳（professor.qin@qq.com）