排序算法

排序问题：###

输入：n个数的一个序列<a1，a2,...,an>
输出：输入序列的一个排列<a1',a2',...an'>，满足a1'<=a2'<=,...<=an'
下面先上总结，然后再逐一说明各个算法。

排序方法	平均时间	最差时间	额外空间	是否稳定
插入排序	O(n*n)	O(n*n)	O(1)	是
归并排序	O(nlgn)	O(nlgn)	O(n)	是
堆排序	O(nlgn)	O(nlgn)	O(1)	否
选择排序	O(n*n)	O(n*n)	O(1)	否
快速排序	O(nlgn)	O(n*n)	O(lgn)->O(n)	否
计数排序	O(n+k)	O(n+k)	O(n+k)	是
基数排序	O(d(n+k))	O(d(n+k))	O(n+k)	是
桶排序	O(n)	O(n*n)	O(n)	是
鸽巢排序	O(n)	O(n)	O(range)	否
梳排序	O(n*n)	O(n*n)	O(1)	否
希尔排序	O(n*n)	O(n*n)	O(1)	否
冒泡排序	O(n*n)	O(n*n)	O(1)	是
煎饼排序	O(n*n)	O(n*n)	O(1)	否

1.插入排序
（1）原理说明
每次将一个新的数放到已经排好序的数组中
初始只有一个数，这是排好序的
以后每次加一个新的数，都选好位置让它插入，使得插入后的数组还是有序的
这就像打扑克时摸牌整理一样

摸牌排序.gif
（2）算法简单实现如下:Github插入排序
（3）算法性能分析：
插入排序对已排序或近似排序的序列会有较好性能，因为此时内循环～O(1)，所以整体时间－>O(n)，而对恰好反序排列的序列要耗时O（n＊n），平均情况耗时O（n＊n）
由于只有常数个额外空间使用，所以空间为O(1)
此内循环的终止条件（<而不是<=）决定了此排序算法是稳定的
2.归并排序
（1）原理说明：
归并排序基于这样一种基本算法：我有两个已经排好序的数组，怎样把它们合并成一个有序的数组
这个基本算法实现很简单，每次比较两个数组当前的最小元素的大小，把其中小的放进结果数组中，重复这一过程直到其中一个数组元素耗尽，之后把没有耗尽的数组剩下的数全部放到结果数组中去即可。其实为了减少这种元素个数是否耗尽的情况判断，我们可以在两个数组的最后添加一个哨兵元素（值为MAX以致两个数组中出现的元素都不可能比它大），这样当一个数组原本的元素耗尽则只剩下设置的哨兵元素，另一个数组元素永远比这个哨兵元素小就会一直把此数组中的剩余元素放进结果数组中，达到了减少判断元素耗尽的判断。
归并排序是分治思想（详见算法思想——分治法）的一种应用。
归并排序将一个数组不断地二分，直到子数组元素个数为1个；这时1个元素显然为已经排好序的，然后将这些数组两两合并，得到元素个数更多的排好序的子数组，这样不断重复这一过程最重会得到原始数组排好序的结果。一个例子如下图所示： 归并排序.gif

（2）算法简单实现如下：Github归并排序
（3）算法性能分析：
为了解决一个数组排序(T(n))，我们需要解决这个数组的两个子数组(T(n/2))的排序并将其合并(O(n))，所以：
T(n)＝T(n/2)＋O(n)
所以耗时为O（nlgn）
由于进行了数组的拷贝，所以额外空间消耗为O（n）
3.堆排序
（1）原理说明：
这是利用堆（详见基本数据结构（栈、队列、链表、树、堆））这种数据结构来进行排序的算法。具体我们使用的是最大堆。
具体堆排序算法如下：
首先我们构建最大堆
然后每次将堆头（heap[0]也即剩余堆中的最大值）与堆尾交换，这样当前最大的值就被放在了最后面
这时我们将堆大小减一，再对堆头维护最大堆性质（交换破坏了最大堆特性），维护后的堆重复进行上述交换，直到最后堆只剩下一个元素，即为最小值在第一个位置，完成排序。示例如下图所示：

堆排序.gif

（2）算法简单实现如下：Github堆排序
（3）算法性能分析：
建堆耗时O(n)
维护堆耗时O(h)＝O(lgn)
维护堆在循环中所以整体堆排序耗时O(nlgn)
因为没有占用额外空间（原址排序），所以空间为O（1）
由此可见此算法结合了插入排序（空间复杂度低）和归并排序（时间复杂度低）的优点。
这种堆排序是不稳定的。
4.选择排序
（1）原理说明：
每次选择剩余元素中最小的，和已排序的数组的后面一个元素交换。初始剩余元素为全部，已排序个数为0，即应该把第一次选出来的元素和位置为0的元素交换。例子如下图所示：

选择排序.gif

（2）算法简单实现如下：Github选择排序
（3）算法性能分析：
两层循环耗时O（n*n）
没有额外为数据分配空间，所以空间消耗为O（1）
由于涉及到swap，所以是不稳定的，考虑（1，2，2，1）
不过如果额外分配O（n）空间，可以使其变稳定

5.快速排序
（1）原理说明：
快速排序也是基于分治细想的一种算法，只是其与归并排序采取的具体分治策略不一样。
快排每次选择待排序列中的一个数，把小于这个数的数放在此数左边，大于这个数的数放在此数右边，然后再递归地对此数的左半部分和右半部分重复之行上述策略，直到最后每个部分只剩下一个数，这时原数组就被排好序了。
由此可见快排的关键在于如何选择“主元”，并把数据按“主元”将数据分为左右两部分，然而answer is“主元”的选取可以随机，也可以每次选固定位置的数。😊而数据的划分可以引进一个坐标记录k，记录当前小于“主元”的最后一个数所在位置。例子如下所示：

快速排序.gif

（2）算法简单实现如下：Github快速排序
（3）算法性能分析：
平均情况下时间O(nlgn)
最坏情况下O(n*n)，这发生在每次划分都不均匀的情况下(9，8，7，6，5，4，3，2，1)，所以随机选择主元可以有效避免最坏情况发生
空间消耗O(lgn)
快排是不稳定的，但存在稳定版本

6.计数排序
（1）原理说明：
这是一种专门针对整数的算法（准确讲应该是非负整数，不过如果是负数我们可以添加offset使其变为正整数）。如果我们知道待排序非负整数都小于一个值max，则我们可以定义长度为max数组，记录序列中每个元素有多少个元素比它小，则这个记录的位置就为其在最后排序结果中应该在的位置。注意如果存在重复的元素，则确定完其中一个的位置后我们应当对记录数组进行修改，以确保两次放置不会放到同一个位置上。例子如下图所示：

计数排序.gif

（2）算法简单实现如下：Github计数排序
（3）算法性能分析：
因为都是单层for循环，所以时间为O(n+k)
空间消耗为O(n+k)
注意上面算法实现中要从后往前逐一放置元素，这保证了算法的稳定性。
7.基数排序
（1）原理说明：
基数排序也是针对整数的排序（其实非整数可以乘以一个大的10^k使所有待排序数都变为整数，负数可以单独拿出来变为正数排序后进行合并），如果我们知道待排数据中最大数据的位数，则可以对从低到高对每一位进行排序（使用基数排序，注意计数排序的稳定性保证了基数排序的正确性），则当排好最高位后即得到排好序的结果。一个例子如下所示：

基数排序.jpg

（2）算法简单实现如下：Github基数排序
（3）算法性能分析：
有d位进行计数排序，所以时间消耗O(n+k)
额外空间与计数排序一样
其也是稳定的
8.桶排序
（1）原理说明：
这是针对[0,1)之间的小数进行排序的一种算法(其实可以将序列同除以一个大的10^k使它们都落在[0,1)之间)，假设有n个数的序列，则我们将[0,1)划分为n个子区间(形象地称为“桶”)然后我们将这n个数放进这n个桶里，假设这些数服从随机分布，则不太可能集中分布在一个桶里，我们针对每个桶里的数进行插入排序，然后再把每个排过序的桶按序合并起来，即得到最终的排序结果。例子如下图所示：

桶排序.jpg

（2）算法简单实现如下：Github桶排序
（3）算法性能分析：
平均时间为O(n)
但如果不幸落在同一桶里，就是个插入排序了，所以最差O(n*n)，不过如果采用高效的比较算法比如快排、合并排序、堆排序等等则会最差O(nlgn)
因为要准备“桶”，所以消耗额外O(n)空间
加入我们采用插入排序，则此时桶排序时稳定的。

9.鸽巢排序
（1）原理说明：这个也是针对整数排序的算法，如果我们知道待排序列最小和最大的数，则我们可以首先减去最小值，使序列offset到以0为起点的数据，然后定义一个数组，大小为序列的range(max-min)，然后遍历序列将每个数据存储在相应位置上，这样最后我们就得到一个各个元素出现次数统计的数组，没有出现过的记录为0，这样我们从小到大遍历这个数组，将个数不为0的元素加上最小值(恢复偏置)输出，即得到最后的输出结果。例子如下图所示：

鸽巢排序.png

（2）算法简单实现如下：Github鸽巢排序
（3）算法性能分析：
鸽巢排序耗时为O(n)
但是建造鸽巢要耗费O(range)空间，如果范围很大，则这很浪费空间
讲道理这个和计数排序好像的，但鸽巢排序是不稳定的，放在同一个鸽巢里的数据如果没有额外映射关系，则不能确定原来的顺序。而计数排序是按原数组从后往前的位置查找其应该放的位置，所以是稳定的。

10.梳排序
（1）原理说明：
我们从头到尾遍历比较位置为i和i+gap的两个数，如果后者小于前者，则进行交换。上述为一次循环。gap初值设为length/1.3(准确为1.247，这个设的太小收敛过慢，设的太大会返回错误排序结果)，每进行一次循环gap/=1.3，直到gap变为最小值1，进行最后一次遍历得到最终结果。一个例子如下图所示：

梳排序.png

（2）算法简单实现如下：Github梳排序
（3）算法性能分析：
时间消耗为O(n*n)
空间消耗为O(1)
它是不稳定排序

11.希尔排序
（1）原理说明：
我们从头开始选择增量为n的length/n个数对他们分别进行插入排序(这会有n组结果)，这是一次循环。增量从length/2开始一直除以2直到增量变为1，循环结束则得到最终排序结果。例子如下图所示：

希尔排序.jpg
（2）算法简单实现如下：Github希尔排序
（3）算法性能分析：
时间消耗为O(n*n)
空间消耗为O(1)
这是不稳定的排序算法，考虑(1，2，2，1)

12.冒泡排序
（1）原理说明：
这种排序大部分情况下只用在教学，是个toy algorithm。每次从首位开始逐一向后比较当前数和后一个数的大小关系，如果后者大于前者则进行次序交换，这样当第一轮遍历到最后时最大的数就“浮”到最上面了。进行n-1次这样的遍历，则每次遍历都会“浮出”剩余序列中最大的数组，所有n-1次遍历完成后，就得到最终排好序的数列。例子如下图所示：

冒泡排序.gif

（2）算法简单实现如下：Github冒泡排序
（3）算法性能分析：
时间消耗O(n*n)
空间消耗O(1)
是稳定的

13.煎饼排序
（1）原理说明：
煎饼排序如其名，和煎饼的时候翻面很相似。我们选择当前剩余最大的数，一铲子铲下去从上到下翻一个个儿，则此时最大的值到了最上面，然后选择下面已排好顺序的数的上面(初始情况就是最下面)再一铲子铲下去，则此时最上面的剩余最大的数就翻转到了其应该在的位置，重复这样的步骤，就可以得到排好序的序列。翻转煎饼的例子如下图所示：

煎饼1.jpg
煎饼2.jpg
煎饼3.jpg

（2）算法简单实现如下：Github煎饼排序
（3）算法性能分析：
时间消耗O(n*n)
因为借用了栈，所以空间消耗O(n)，其实可以不用栈进行操作的
是不稳定的

其实还有很多排序算法，这里不再进行说明。（PS：不是说它们不重要，只是我们更侧重于了解这些排序算法内在的思想，而不仅仅是算法本身）
另PS：在算法可视化网上的sort中可以看到以上所有排序算法的动态演示