㈠ O（n2）排序算法的总结
最近在慕课网上学习了O（n2）时间复杂度的相关算法，总算是对这些算法的优缺点有了详细的特点。其实对于任何的算法，没有优点和缺点，而是有相应的特点。所以我们应该结合不同的排序环境来选择不同的排序算法，从而达到在实现时间和执行效率上的平衡。这是因为，越是简单的排序算法，实现起来肯定是越容易，而且出现BUG的概率也不会太大。相反，复杂算法可能效率更高，但是出现问题的可能性也会更大。下面，我就结合O（n2）时间复杂度的四个经典排序算法，为您详细讲解这四个算法的特点。
定义：选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
图示说明：
源码实现：
分析：通过选择排序的图示和源码我们可以看出来，选择排序要进行两次循环，而且最关键的是内层循环在每一次执行时都是全部执行完的。那我们有没有办法让内层循环不用每次都执行完呢？方法肯定是有的，这就是冒泡排序。
定义：冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，一次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
图示说明：
源码实现：
分析：从图示和源码可以看出来，从执行次数上来说，冒泡排序是比选择排序的循环次数更少的。那是不是就可以说，如果待排序的数组中元素比较合适，冒泡排序在时间复杂度上是不是会比选择排序更好呢？真的是这样的吗？
其实不是的，经过多次测试验证，冒泡排序基本上是比选择排序的时间复杂度要差的，这是为什么呢？从源码中我们可以很明显的看出来，虽然冒泡排序是比选择排序执行次数少了，但是交换的次数明显增多了，而如果你对计算机程序指令的实现原理只要有一个基本的认识，就应该知道交换动作比赋值动作是需要更多指令操作的。所以说，最终冒泡排序大部分情况下，比选择排序的时间复杂度都要高。
既然交换动作这么消耗资源，那有没有一种方法，即能够减少内层循环的执行次数，又可以减少甚至是无需交换操作呢？这就要请出插入排序了。
定义：插入排序（Insertion Sort）的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，即每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
图示说明：
源码实现：
分析：从图示和源码可以看出来，插入排序（优化后的）是没有交换操作的，而且对于内层循环来说，如果待排序的元素是比较大的值，那内层循环执行的次数会非常的少。因此，如果原始数据基本上是有序的，那使用插入排序的效率会非常的高。在O（n2）级别的排序算法还可以再优化吗？如果可以从哪里优化呢？下面我们来介绍希尔排序，正是这个排序算法的提出，使得排序算法打破了O（n2）时间复杂度的禁锢。
定义：希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。该算法的基本思想是：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，排序算法便终止。
对于希尔排序来说，最关键的就是增量该如何选取。这个增量该怎么确定，这还真是个数学难题，至今没有解答。但是通过大量的实验，还是有个经验值的。我们的例子给出的增量选取公式是：h = 3 * h + 1，下面请看图示说明。
图示说明：
源码实现：
分析：从插入排序中我们知道，插入排在待排序数组基本有序时，插入排序的算法效率会非常高，所以我们可以这样认为，希尔排序的最终思想就是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，在对全体进行一次直接插入排序。
而希尔排序的效率之所以很高，就是因为这个基本思想确实很有用：即当h值大的时候，数据项每一趟排序需要移动元素的个数很少，但数据项移动的距离很长。这是非常有效率的。而当h减小时，每一趟排序需要移动的元素的个数增多，但是此时数据项已经接近于它们排序后最终的位置，这对于插入排序可以更有效率。正是这两种情况的结合才使希尔排序效率那么高。
对于增量的选取，可以称得上是一种魔法。在希尔的原稿中，他建议初始的间距为N/2，简单地把每一趟排序分成了两半。但是，这被证明并不是最好的数列。尽管对于大多数的数据来说这个方法还是比插入排序效果好，但是这种方法有时会使运行时间降到O(N2)，这并不比插入排序的效率更高。间隔序列中的数字互质通常被认为很重要：也就是说，除了1之外它们没有公约数。这个约束条件使每一趟排序更有可能保持前一趟排序已排好的效果。希尔最初以N/2为间隔的低效性就是归咎于它没有遵守这个准则。
总结：上面就是四种经典O（n2）级别排序算法的相关说明。其实在各种场合下选择排序和冒泡排序基本上是不会使用的，因为使用场景基本没有。而对于插入排序和希尔排序来说，在待排序数据基本有序的情况下，使用场景还是有的，比如一些日志文件中存储的日志，可能大部分的日志记录都是基于时间排序，只是在某些极端情况下导致一些日志晚存储了导致时间不一致。
我是徐建航， 这是我写的第31篇文章，欢迎你加入007社群，七天写一篇，一起写七年，七年之后一起去南极。
㈡ 面试必会八大排序算法（Python）
一、插入排序
介绍
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。
算法适用于少量数据的排序，时间复杂度为O(n^2)。
插入排算法是稳定的排序方法。
步骤
①从第一个元素开始，该元素可以认为已经被排序
②取出下一个元素，在已经排序的元素序列中从后向前扫描
③如果该元素（已排序）大于新元素，将该元素移到下一位置
④重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⑤将新元素插入到该位置中
⑥重复步骤2
排序演示
算法实现
二、冒泡排序
介绍
冒泡排序（Bubble Sort）是一种简单的排序算法，时间复杂度为O(n^2)。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
原理
循环遍历列表，每次循环找出循环最大的元素排在后面；
需要使用嵌套循环实现：外层循环控制总循环次数，内层循环负责每轮的循环比较。
步骤
①比较相邻的元素。如果第一个比第二个大，就交换他们两个。
②对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
③针对所有的元素重复以上的步骤，除了最后一个。
④持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
算法实现：
三、快速排序
介绍
快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。
基本思想
快速排序的基本思想是：挖坑填数 + 分治法。
首先选出一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
实现步骤
①从数列中挑出一个元素，称为 “基准”（pivot）；
②重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）；
③对所有两个小数列重复第二步，直至各区间只有一个数。
排序演示
算法实现
四、希尔排序
介绍
希尔排序（Shell Sort）是插入排序的一种，也是缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法，时间复杂度为：O(1.3n)。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
·插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率；
·但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位。
基本思想
①希尔排序是把记录按下标的一定量分组，对每组使用直接插入算法排序；
②随着增量逐渐减少，每组包1含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法被终止。
排序演示
算法实现
五、选择排序
介绍
选择排序(Selection sort)是一种简单直观的排序算法，时间复杂度为Ο(n2)。
基本思想
选择排序的基本思想：比较 + 交换。
第一趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；
第二趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；
以此类推，第 i 趟，在待排序记录ri ~ r[n]中选出最小的记录，将它与r[i]交换,使有序序列不断增长直到全部排序完毕。
排序演示
选择排序的示例动画。红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置。
算法实现
六、堆排序
介绍
堆排序（Heapsort）是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。
利用数组的特点快速指定索引的元素。
基本思想
堆分为大根堆和小根堆，是完全二叉树。
大根堆的要求是每个节点的值不大于其父节点的值，即A[PARENT[i]] >=A[i]。
在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
排序演示
算法实现
七、归并排序
介绍
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
基本思想
归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
算法思想
自上而下递归法（假如序列共有n个元素）
① 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
② 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
③ 重复步骤②，直到所有元素排序完毕。
自下而上迭代法
① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
② 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
④ 重复步骤③直到某一指针达到序列尾；
⑤ 将另一序列剩下的所有元素直接复制到合并序列尾。
排序演示
算法实现
八、基数排序
介绍
基数排序（Radix Sort）属于“分配式排序”，又称为“桶子法”。
基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m) ，其中 r 为采取的基数，而m为堆数。
在某些时候，基数排序法的效率高于其他的稳定性排序法。
基本思想
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序按照优先从高位或低位来排序有两种实现方案：
MSD（Most significant digital） 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等,再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来,便得到一个有序序列。MSD方式适用于位数多的序列。
LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。
排序效果
算法实现
九、总结
各种排序的稳定性、时间复杂度、空间复杂度的总结：
平方阶O(n²)排序：各类简单排序：直接插入、直接选择和冒泡排序；
从时间复杂度来说：
线性对数阶O(nlog₂n)排序：快速排序、堆排序和归并排序；
O(n1+§))排序，§是介于0和1之间的常数：希尔排序 ；
线性阶O(n)排序：基数排序，此外还有桶、箱排序。