排序算法

最近看了一篇比较有趣的文章 《比冒泡算法还简单的排序算法：看起来满是bug的程序，居然是对的》，看了半天才看懂。 发现自己其实已经不太记得各种排序方法了，此处做一个复习总结。 （给自己看的笔记也不会很详细，毕竟大部分也都实现过，这里主要记录intuition。） 主要参考了这篇知乎的博文，《八大经典排序算法详解》。

鸽巢排序

• 基本思想：空间换时间，建立一个足够长的数组，按照数值的大小放到相应的位置，最后遍历删除空位置。
• 时间复杂度为 O(n)。但是如果需要排序的数中有特别大的，则数组需要建立的特别大，不方便使用。

桶排序

上述鸽巢排序可以看作一种极端的（桶数很多的）桶排序：

• 基本思想：空间换时间，将待排序的序列分到若干个桶中（桶具有顺序），每个桶内的元素再进行基于比较的排序。
• 时间复杂度为 O(k+n)，k 为最大值。
• 是稳定的排序方法。
• 限制比较多：只能int，空间消耗大，只有对于均匀数列效果好

插入排序

• 基本思想：将待插入样本按其值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
• 时间复杂度为 O(n^2)。
• 是稳定的排序方法。

快速排序

• 基本思想：在待排序的元素任取一个元素作为基准(通常选第一个元素，称为基准元素），将待排序的元素进行分块，比基准元素大的元素移动到基准元素的右侧，比基准元素小的移动到作左侧，从而一趟排序过程，就可以锁定基准元素的最终位置，对左右两个分块重复以上步骤直到所有元素都是有序的（递归过程）。
• 快速排序平均时间复杂度为 O(nlogn)，最坏情况为 O(n^2)，n越大，速度越快。
• 不是稳定的排序算法。

选择排序

• 基本思想：每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
• 时间复杂度 O(n^2)。
• 选择排序是不稳定的排序方法。（存在不相邻元素的互换）

希尔排序

• 基本思想：设置一定的步长序列 [a,b,c,1]（最后一个需要为1），然后根据步长来构建分组（以 a 为例，每个分组中都是相隔为a的一组样本：i, i+a, i+2a…），然后对分组里的样本进行排序，之后合并为新序列。a 步长进行完之后，在新的序列上使用下一个步长 b 得到下一个序列，如此往复。最后一个步长需要为1。
• 时间复杂度 平均时间 O(nlogn) 最差时间O(n^2)
• 是不稳定的排序方法。

堆排序

• 基本思想：利用最大堆或最小堆，先将所有值放入堆中储存，再一一取出，则排好序。
• 堆排序是一种选择排序,其时间复杂度为 O(nlogn)。堆排序是不稳定的

归并排序

• 基本思想：将待排序的数组分成前后两个部分，再递归的将前半部分数据和后半部分的数据各自归并排序，得到的两部分数据，然后使用merge合并算法将两部分数据合并到一起。
• 最好、最坏和平均时间复杂度都是 O(nlogn)，空间复杂度是 O(n)。
• 是稳定的排序算法。

冒泡排序

• 基本思想：持续比较相邻的元素。如果第一个比第二个大，就交换他们两个。直到没有任何一对数字需要比较。
• 冒泡排序最好的时间复杂度为 O(n)，冒泡排序的最坏时间复杂度为 O(n^2)，因为循环轮数不确定。因此冒泡排序总的平均时间复杂度为 O(n^2)。
• 算法适用于少量数据的排序。
• 是稳定的排序方法。

for i = 1 to n do
for j = i + 1 to n do
if A[i] > A[j] then
swap A[i] and A[j]

Bug 满满的“数组升序排序”

这个方法第一次见于《比冒泡算法还简单的排序算法：看起来满是bug的程序，居然是对的》。 伪代码如下。 这个代码相对于冒泡排序看起来有两个地方写错了，一个是判断时的小于号，一个是第二个 for 循环中的开始项。 但是这个算法竟然可以惊讶地得到正确的结果。

for i = 1 to n do
for j = 1 to n do
if A[i] < A[j] then
swap A[i] and A[j]

本质上是一种插入排序，即把第 i 位的数插入到前 i-1 位的数中，使得前 i 位的数有序。 不同于经典的插入排序是直接插，此处是进行交换插入。