基础算法| 常用排序算法小结
日常吹水
说到这个算法，
可能瞬间大家就觉得那些灰机昏膏素什么的比这个生动活泼多了。
那么，正走在算法之路上的你，
是否还在苦苦寻求修仙之路？
是否被各种排序算法欺负得苦不堪言？
那还等什么，快进来看看
带你全程装逼加一路向西！
刺不刺激？高不高能？
＊
内容提要：
＊排序常用术语介绍
＊冒泡排序
＊选择排序
＊插入排序
＊希尔排序
＊归并排序
＊快速 排序
排序基础知识
⚫排序的定义
将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。说得再通俗点，比如将一个班的人（数据元素）按照身高（关键字）站位，高的站前面，矮的站后面咯。
⚫ 排序的分类
排序可分为内排序和外排序。
所谓内排序就是所有的数据和操作都在内存中完成。
而外排序就是说需要排序的数据太大，无法全部塞进内存，需要在内存和外存之间多次数据交换才能完成的排序。
⚫算法优劣的术语说明
⚫稳定：如果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）