程序员需要会写的几种排序算法
我一直觉得写代码也可以写出艺术，在不懂画的人的眼里，《向日葵》不过是小孩子的涂鸦，在懂代码的人眼里，那看似混乱的字符，确是逻辑艺术的完美体现。
排序算法基础
排序算法，是一种能将一串数据按照特定的排序方式进行排列的一种算法，一个排序算法的好坏，主要从时间复杂度，空间复杂度，稳定性来衡量。
时间复杂度
时间复杂度是一个函数，它描述了该算法的运行时间，考察的是当输入值大小趋近无穷时的情况。数学和计算机科学中使用这个大 O 符号用来标记不同”阶“的无穷大。这里的无穷被认为是一个超越边界而增加的概念，而不是一个数。
想了解时间复杂度，我想讲讲常见的 O(1)，O(log n)，O(n)，O(n log n)，O(n^2) ，计算时间复杂度的过程，常常需要分析一个算法运行过程中需要的基本操作，计量所有操作的数量。
O（1）常数时间
O（1）中的 1 并不是指时间为 1，也不是操作数量为 1，而是表示操作次数为一个常数，不因为输入 n 的大小而改变，比如哈希表里存放 1000 个数据或者 10000 个数据，通过哈希码查找数据时所需要的操作次数都是一样的，而操作次数和时间是成线性关系的，所以时间复杂度为 O（1）的算法所消耗的时间为常数时间。
O（log n）对数时间
O（log n）中的 log n 是一种简写，loga n 称作为以 a 为底 n 的对数，log n 省略掉了 a，所以 log n 可能是 log2 n，也可能是 log10 n。但不论对数的底是多少，O（log n）是对数时间算法的标准记法，对数时间是非常有效率的，例如有序数组中的二分查找，假设 1000 个数据查找需要 1 单位的时间， 1000,000 个数据查找则只需要 2 个单位的时间，数据量平方了但时间只不过是翻倍了。如果一个算法他实际的得操作数是 log2 n + 1000， 那它的时间复杂度依旧是 log n， 而不是 log n + 1000，时间复杂度可被称为是渐近时间复杂度，在 n 极大的情况，1000 相对 与 log2 n 是极小的，所以 log2 n + 1000 与 log2 n 渐进等价。
O（n）线性时间
如果一个算法的时间复杂度为 O(n)，则称这个算法具有线性时间，或 O(n) 时间。这意味着对于足够大的输入，运行时间增加的大小与输入成线性关系。例如，一个计算列表所有元素的和的程序，需要的时间与列表的长度成正比。遍历无序数组寻最大数，所需要的时间也与列表的长度成正比。
O（n log n）线性对数时间
排序算法中的快速排序的时间复杂度即 O（n log n），它通过递归 log2n 次，每次遍历所有元素，所以总的时间复杂度则为二者之积， 复杂度既 O（n log n）。
O（n^2）二次时间
冒泡排序的时间复杂度既为 O（n^2），它通过平均时间复杂度为 O（n）的算法找到数组中最小的数放置在争取的位置，而它需要寻找 n 次，不难理解它的时间复杂度为 O（n^2）。时间复杂度为 O（n^2）的算法在处理大数据时，是非常耗时的算法，例如处理 1000 个数据的时间为 1 个单位的时间，那么 1000,000 数据的处理时间既大约 1000,000 个单位的时间。
时间复杂度又有最优时间复杂度，最差时间复杂度，平均时间复杂度。部分算法在对不同的数据进行操作的时候，会有不同的时间消耗，如快速排序，最好的情况是 O（n log n），最差的情况是 O（n^2），而平均复杂度就是所有情况的平均值，例如快速排序计算平均复杂度的公式为
![Uploading image-2_542306.png . . .]
image-1.png
最后的结果就是 1.39n * log2 n，与 n * log2 n 渐进等价，是的，1.3 倍在无穷大级别都不算什么，只要不和无穷大的 n 相关的乘数都可以通过渐进等价省略掉。
空间复杂度
和时间复杂度一样，有 O(1)，O(log n)，O(n)，O(n log n)，O(n^2)，等等，但谈论算法的空间复杂度，往往讲它的额外空间复杂度，例如冒泡排序算法只需要额外的常数空间，放置交换两个相邻数时产生的中间变量，及循环时候用来记录循环次数的变量。所以冒泡排序的额外空间复杂度为 O(1)。如果算法所需的额外空间为 O(n)，则操作数据的数目和所需的空间成线性关系。
稳定性
当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。
(4, 1) (3, 1) (3, 7) （5, 6）
在这个状况下，有可能产生两种不同的结果，一个是让相等键值的纪录维持相对的次序，而另外一个则没有：
(3, 1) (3, 7) (4, 1) (5, 6) （维持次序）
(3, 7) (3, 1) (4, 1) (5, 6) （次序被改变）
不稳定排序算法可能会在相等的键值中改变纪录的相对次序，这导致我们无法准确预料排序结果（除非你把数据在你的大脑里用该算法跑一遍），但是稳定排序算法从来不会如此。例如冒泡排序即稳定的存在，相等不交换则不打乱原有顺序。而快速排序有时候则是不稳定的。（不稳定原因会在讲快速排序时说明。）
常见排序算法
冒泡排序
冒泡排序是一种非常简单的排序算法，4，5 行代码就能实现，过程分为 4 个步骤：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
这个算法的名字由来是因为越大的元素，会经由交换慢慢的“浮”到数列的尾端。冒泡排序对 n 个项目需要 O(n^2) 的比较次数，且是在原地排序，所以额外空间复杂度为 O(1) 。尽管这个算法是最容易了解和实现的排序算法之一，但它相当于其它数列排序来说是很没有效率的排序，如果元素不多，对性能也没有太大要求，倒是可以快速写出冒泡排序来使用。博客中出现的代码都由 C++ 编写。
void bubbleSort(int array[], int length) {
int i, j;
for (i = 0; i < length - 1 ;i++)
for (j = 0; j < length - 1 - i; j++)
if (array[j] > array[j + 1])
swap(array[j], array[j+1]);
}
插入排序
插入排序简单直观，通过构建有序序列，对于未排序的元素，在已排序序列中从后向前扫描，找到相应位置并插入。时间复杂度为 O(n^2) ，原地排序，额外空间复杂度为 O（1）。
过程分为 6 个步骤：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
void insertSort(int array[], int length) {
int i, j;
int temporary;
//从第二个元素开始，将元素插入到已排好序的元素里。
for (i = 1; i < length; i++) {
//需要插入的新元素
temporary = array[i];
//从已排序的元素序列中从后向前扫描，找到已排序的元素小于或者等于新元素的位置，将新元素
//插入到该位置后
for (j = i - 1; j >= 0 && array[j] > temporary; j--)
array[j+1] = array[j];
array[j+1] = temporary;
}
}
选择排序
选择排序也是非常简单的排序算法，选择最小先排序，首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。时间复杂度为 O(n^2)，额外空间复杂度为 O(1)。
过程分为 5 个步骤：
- 从第一个元素开始，声明一个变量储存最小元素的位置，初始为第一个元素的位置。
- 取出下一个元素，与当前最小元素进行比较。如果元素比当前最小元素小，则变量储存这个元素的位置。
- 重复步骤 2，直到没有下一个元素，变量里储存的既最小元素的位置。
- 将最小元素放在排序序列的起始位置。
- 重复 1~3，从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
//选择排序 平均时间复杂度O(n^2) 额外空间复杂度O(1)
void selectionSort(int array[], int length) {
int i, j, min;
for (i = 0; i < length; i++) {
//找到最小元素存放到起始位置。
min = i;
for (j = i + 1; j < length; j++)
if (array[j] < array[min])
min = j;
swap(array[i], array[min]);
}
}
快速排序
快速排序从名字上来说并不能直观的记忆它的实现思路，但它和它的名字一样，很快速，快速排序是一个非常不错的排序算法，时间复杂度 O(n log n)，且通常明显比其他 Ο(n log n) 算法更快，这是最应该记忆，并能熟练写出的排序算法。
步骤为：
- 从数列中挑出一个元素，称为"基准"，
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区操作。递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
为了减少数组中不必要的移动，挑最后一个元素为基准，在剩下的元素的左右两端开始寻找，左边找到比它大的，右边找到比它小的，交换这个数的位置，继续寻找，只需要很少的交换步骤，即可将比基准大的和比基准小的数分开，最后左右两端汇集在一起，汇集在一起有两种情况。
- 第一种，左端汇集到右端身上，说明汇集之前左端的值比基准小，所以它需要向右移动去寻找，如果右端的值已经交换过了，则右端比基准大，左右两端已汇集，所以只要交换左端和基准的值就可以了。如果右端的值还没交换过，则与基准值进行比较，大于的话交换左端和基准的值，小于的话，则说明左边的值都比基准值小，去掉基准值，剩下的数继续快排。
- 第二种，右端汇集到左端身上，说明左端找到了比基准大的值，而汇集之前右端的值也比基准大，所以也只要交换左端和基准的值就可以了。
逻辑看起来很复杂，只是对递归到最深的地方对各种情况做处理。
void quickSortRecursive(int array[], int start, int end) {
if (start >= end)
return;
//从数列中挑出一个元素，称为"基准"。
int mid = array[end];
int left = start;
int right = end - 1;
while (left < right) {
//从左开始找，找到大于等于 mid 的数停止。
while (array[left] < mid && left < right) left++;
//从右开始找，找到小于 mid 的数停止。
while (array[right] >= mid && right > left) right--;
//交换left和right位置的数
swap(array[left], array[right]);
}
//使 left 位置数小于它左边的数，大于它右边的数。
if (array[left] >= array[end])
swap(array[left], array[end]);
else
left++;
//递归地把小于基准值元素的子数列和大于基准值元素的子数列排序
quickSortRecursive(array, start, left - 1);
quickSortRecursive(array, left + 1, end);
}
为什么说快速排序有时候是不稳定的呢，如上面代码所写，相等的都按比基准小做处理，因为基准在最右端，所以顺序不会变，这是稳定的，但有时候快速排序为了防止某些极端情况，（比如本身就是顺序排序，这个时候时间复杂度就是 O(n^2)），往往挑选中间的数移至末尾作为基准，这个时候就会打乱与基准相等数的顺序，就是不稳定的。(所以这些排序算法重要的是思路，代码是可以根据情况进行改变的)
递归的时候由于函数调用是有时间和空间的消耗的，所以快速排序的空间复杂度并不是 O(1)，因为最差情况，递归调用 n 次，所以最差空间复杂度为 O(n)，最好情况，递归调用 log n 次，所以最优空间复杂度为 O(log n)，因为额外空间复杂度一般看最差情况，因为时间可以平均，但空间一定得满足，所以它的额外空间复杂度为 O(n)。
堆排序
堆排序比其它排序更难理解一点，但堆排序很有意思，它需要利用堆这种数据结构，堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。小于则是最小堆，根结点为堆的最小值，大于则是最大堆，根节点为堆得最大值。而堆排序则利用最大堆的性质，一个一个找出最大数的值。堆可以通过数组来实现。下图是一个一维数组，第一个元素是根节点，每一个父节点都有两个子节点，可以从图中得出这样的规律，
- 父节点 i 的左子节点在位置 (2 * i + 1);
- 父节点 i 的右子节点在位置 (2 * i + 2);
- 子节点 i 的父节点在位置 floor((i - 1) / 2);
image-3.png
floor 函数的作用是向下取整，所以左子节点右子节点都能通过这个公式找到正确的父节点。
先上代码。
//堆排序 平均时间复杂度O(n log n) 额外空间复杂度O(1)
void maxHeap(int array[], int start, int end) {
int dad = start;
int son = dad * 2 + 1;
while (son < end) {
//比较两个子节点的大小。
if (son + 1 < end && array[son] < array[son + 1])
son++;
//如果父节点大于子节点，直接返回。
if (array[dad] > array[son])
return;
//如果父节点小于子节点，交换父子节点，因为子节点变了，所以子节点可能比孙节点小，需继续
//比较。
swap(array[dad], array[son]);
dad = son;
son = dad * 2 + 1;
}
}
void heapSort(int array[], int length) {
int i;
//i从最后一个父节点开始调整
for (i = length / 2 - 1; i >= 0; i--) {
//形成最大堆，第一个元素为最大数。
maxHeap(array, i, length);
}
//将第一个元素放置到最后，再将前面的元素重新调整，得到最大堆，将此时最大的数放置到倒数第二
//位置，如此反复。
for (int i = length - 1; i > 0; i--) {
swap(array[0], array[i]);
maxHeap(array, 0, i);
}
}
maxHeap 函数是用来使以此父节点作为根节点的堆为最大堆，先比较两个子节点的大小，找到最大的子节点，再与根做比较，如果根大则已经是最大堆，如果根小，则交换子节点和根节点的数据，此时子节点还得保证以它为根节点的堆为最大堆，所以还需要与孙节点进行比较。函数结束既调整完毕。
heapSort 函数里先从最后一个父节点开始调整，调整完的数与有序数列前一位交换，形成新的有序数列，此时再对剩下来的数进行堆调整，因为两个子节点已经是最大堆了，所以这个时候是直接以第一个元素为根调整，只需要操作 log2 n 次，所以排好一个数据的平均时间渐进等价于 log2 n，所以堆排序的时间复杂度为 O(n log n)。堆排序是原地排序，所以额外空间复杂度为 O(1)。堆排序和快速排序一样，是一个不稳定的排序，因为在根的位置左子树和右子树的数据，你并不知道哪个元素在原数组处于前面的位置。
总结
我最喜欢堆排序，它最差的时间复杂度也是 O(n log n)，而快速排序虽然比它更快点，但最差的时间复杂度为 O(n^2)，且堆排序的空间复杂度只有 O(1)。还有很多很有意思的排序方法，我稍微了解了一下思路，并未都写一遍。建议不管是哪个方向的程序员，都将这些常见的排序算法写写，体验一下编程之美。
生活不应该只有 API 的调用，还应该有逻辑与优雅。
PS:算法虽然很有意思，但也一定要刹住，别一不小心被勾搭的转方向了。- -！
最后留个项目链接:JMSort，这是我看完堆排序之后得到的灵感尝试写的排序算法，大概思路就是两两比较之后每四个进行一次比较，最后将得到的最大的数放置在数组末尾，剩下的继续比较。因为上次比较的数据是可以复用的，所以应该效率也不低，不过暂时只写了个没复用版本(因为复用版本被我写乱了)，时间复杂度 O(n^2)，实际运行效率就比冒泡快一点 TAT，等着我以后来优化，目标优化到 O(n log n) 的时间复杂度。
下图是1W条随机数据所需的排序时间。
| 排序方法 | 时间（微秒） |
|---|---|
| 冒泡排序 | 316526 |
| 快速排序 | 1345 |
| 插入排序 | 74718 |
| 选择排序 | 127416 |
| 堆排序 | 2076 |
| JM排序 | 205141 |
