排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的内部排序算法有十种：冒泡排序、选择排序、插入排序、希尔排序、堆排序、快速排序、归并排序、基数排序、计数排序、桶排序。前面三种是简单排序，之后四种是在前面基础上进行优化，最后三种不是基于比较的排序，因此时间复杂度突破了nlogn的限制，但是算法本身对数据有一定的要求。

1 十大排序算法

1.1 冒泡排序

主要思想：依次对两个数比较大小，较大的数冒起来，较小的数压下来。

形象理解：一队新兵N个人整齐站成一列，教官想让他们按照身高排好队，看起来更协调，于是从前走到后走一趟，每次遇到相邻的两个人身高不协调时，就让两人互换位置。当走完一趟时，个子最高的人就被排到了最后。教官回到前排后发现队伍仍然不协调，于是又按照原样走了一趟。这样循环走了N-1趟之后，教官终于满意了。（注意：每次走一趟时，之前排到后面的高个子就不参与这次排序了；有时候可能还没走完N-1趟，教官就发现队伍已经协调了，于是排序结束。）

特点：简单易懂，排序稳定（优点）；速度慢（缺点）。

1.2 选择排序

主要思想：针对冒泡排序，有一个地方可以优化，即在跑一趟的过程中，没必要两两交换，可以先记下最小值，跑完一趟后直接将最小值换到前面。

特点：比冒泡更快一些，但代价是跳跃性交换，排序不稳定。

1.3 插入排序

主要思想：过程跟拿牌一样，依次拿N张牌，每次拿到到牌后，从后往前看，遇到合适位置就插进去。最终手上的牌从小到大。

特点：稳定，当数据规模较小或者数据基本有序时，效率较高（优点）。比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是数据量庞大的时候（缺点）

1.4 希尔排序

主要思想：设增量序列个数为k，则进行k轮排序。每一轮中，按照某个增量将数据分割成较小的若干组，每一组内部进行插入排序；各组排序完毕后，减小增量，进行下一轮的内部排序。
特点：针对插入排序的改进，当数据规模较大或无序时也比较高效。精妙之处在于，可以同时构造出两个特殊的有利条件（数据量小，基本有序），一个有利条件弱时，另外一个有利条件就强。（刚开始时虽然每组有序度低，但其数据量小；随着每轮的增量逐渐压缩，虽然各组数据量逐渐变大，但其有序度逐渐增加。）

先将整个待排序元素序列分割成若干子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（因为直接插入排序在元素基本有序的情况下，效率很高）；

特点：比较在希尔排序中是最主要的操作，而不是交换。用已知最好的步长序列的希尔排序比直接插入排序要快，甚至在小数组中比快速排序和堆排序还快，但在涉及大量数据时希尔排序还是不如快排；

1.5 堆排序

主要思想：将待排数组构建成一个最大堆，将堆顶最大元素换到后面，然后堆容量减1；类似进行N-1次操作即可。

4.1、二叉堆定义：

二叉堆是完全二叉树或近似完全二叉树。二叉堆满足两个特性:

（1）父结点的键值总是大于或者等于（小于或者等于）任何一个子节点的键值；

（2）每个结点的左子树和右子树都是一个二叉堆；

当父结点的键值总是大于或者等于任何一个子节点的键值时为大根堆。当父结点的键值总是小于或等于任何一个子节点的键值时为小根堆；

4.2、堆的存储：

一般都用数组来表示堆，i结点的父结点下标就为（i-1）/2.它的左右子节点的下标分别为2*i+1和2*i+2.

4.3、堆的插入：

每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列，然后将这个新数据插入到这个有序数据中

（1）用大根堆排序的基本思想

先将初始数组建成一个大根堆，此对为初始的无序区；

再将最大的元素和无序区的最后一个记录交换，由此得到新的无序区和有序区，且满足<=的值；

由于交换后新的根可能违反堆性质，故将当前无序区调整为堆。然后再次将其中最大的元素和该区间的最后一个记录交换，由此得到新的无序区和有序区，且仍满足关系的值<=的值，同样要将其调整为堆；

..........

直到无序区只有一个元素为止；

4.4：应用

寻找M个数中的前K个最小的数并保持有序；

时间复杂度：O(K)[创建K个元素最大堆的时间复杂度] +（M-K）*log(K)[对剩余M-K个数据进行比较并每次对最大堆进行从新最大堆化]

1.6 快速排序

主要思想：分治思想。选一基准元素，依次将剩余元素中小于该基准元素的值放置其左侧，大于等于该基准元素的值放置其右侧；然后，取基准元素的前半部分和后半部分分别进行同样的处理；以此类推，直至各子序列剩余一个元素时，即排序完成。

注意：对于小规模数据（n<100），快排由于用了递归，其效率可能还不如插排。因此通常可以定义一个阈值，当递归的数据量很小时停止递归，直接调用插排。

（1）算法思想

选择一个基准元素，将比基准元素小的元素放在其前面，比基准元素大的元素放在其后面，然后在将小于基准值元素的子数列和大于基准元素的子数列按原来的方法排序，直到整个序列有序;

（2）优缺点

优点：极快数据移动少；

缺点：不稳定；

（3）效率分析

此排序算法的效率在序列越乱的时候，效率越高。在数据有序时，会退化成冒泡排序；

（4）对于基准的选择

a.三数取中

具体思想：对待排序序列中low、mid、high三个位置上数据进行排序，取他们中间的那个数据作为枢轴，并用0下标元素存储枢轴；

b.随机选取基准

引入原因：在待排序列是部分有序时，固定选取枢轴使快排效率低下；

具体思想：取在待排序列中任意一个元素作为基准；

（5）优化方法

a.当待排序序列的长度分割到一定大小后，使用插入排序；

原因：对于很小和部分有序的数组，快排不如插排好。当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排；

b.在一次分割结束后，可以把与key相等的元素聚集在一起，继续下次分割时，不必再对于key相等元素分割；

（6）应用场景

 a.求数组中第k小的数

将数组中某一个元素m作为划分依据,即m=arr[0]。若m前面的元素个数大于k，则第k小的数一定在m前面的元素中，这时我们只需要继续在m前面的元素中找第k小的数；若m前面的元素小于k，则第k小的数一定在m后面的元素中，这时我们只需要在m后面的元素中找第k小的数；

1.7 归并排序

归并排序，顾名思义就是合并两个有序数组。常见的归并排序有两种，递归法（自上而下的合并）和非递归法（自底向上的合并），都需要新开一个大小为n的数组来中转。递归法比较简单，就是中间切一刀，左右分别递归排序，最后合并两个有序数组。非递归法就是先分别对相邻的两个元素合并排序，第二趟时候分别对相邻的四个元素合并排序（此时前两个元素和后两个元素已有序），第三趟时候对相邻的八个元素合并排序，依次类推直至有序数组长度超过数组总长度。两者相较，递归的归并排序代码更简洁，代价是时间和空间复杂度上都会更大（因为有递归的logn）。下面的代码是非递归方法，后续对比也按照这个版本。

主要思想：类似两个有序链表的合并，每次两两合并相邻的两个有序序列，直至整个序列有序。

（1）基本思想

首先将初始序列的n个记录看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2的有序子序列，在此基础上，再对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列，以此类推，直到得到一个长度为n的有序序列为止；

（2）适用场景

若n较大，并且要求排序稳定，则可以选择归并排序；

1.8 基排序

主要思想：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

基排序的主要适用场景是待排元素是非负整数，且位数相差不大。此外，整数也可以用字符串等表达，所以也可以用于字符串的排序。

折叠

1.9 计数排序

针对剑指offer中P81提到的场景，假如需要对公司内部几万个员工的年龄进行排序，要求时间复杂度为O(n)，空间复杂度为O(1)。

主要思想：计数排序和前面的基排序类似，都是基于分桶思想。由于这里要求时间复杂度为O(n)，低于基于比较的时间复杂度O(nlogn)，所以前面7中排序算法均失效。又因为该场景中年龄属于一个比较小的范围，有大量的重复值，故可以考虑计数排序。实际做法是，新开一个长度为100的数组（假设年龄为0~99），数组下标表示年龄，数组存储该下标对应的年龄出现的个数，最后再根据数组的计数来排序。

计数排序主要适用场景是元素值比较集中，特别是集中在一个小区间里面。

1.10 桶排序

桶排序两大步骤：第一步是将值域划分成几个区间，然后将待排数组中各元素映射到这几个区间上（从区间这个大视角来看，这几个区间是有序的）；第二步是针对各个区间内部元素，选择一个喜欢的算法进行排序。经过两步之后，整个数组就有序了。

桶排序是对计数排序的改进，计数排序申请的额外空间跨度从最小元素值到最大元素值，若待排序集合中元素不是依次递增的，则必然有空间浪费情况。桶排序则是弱化了这种浪费情况，将最小值到最大值之间的每一个位置申请空间，更新为最小值到最大值之间每一个固定区域申请空间，尽量减少了元素值大小不连续情况下的空间浪费情况。另外，从分桶的思想来看，快排也是一种分桶方法，即用一个pivot将值域切割成两个桶，左右分别递归。只不过快排是用一个pivot来切割值域，而桶排序则是直接将值域划分成几个区间。

桶排序的主要适用场景是，各元素值分布比较均匀，这样分桶时候就可以比较均匀，尽量避免把大部分元素都分到少数几个桶中。

2 十大排序算法比较

复杂度与稳定性的比较（来自维基百科）

以下是基于浙大数据结构课练习题测试（09-排序1 排序 (25 分)），由于后3种算法这里不适用，故只对比了前7种算法。