type
status
password
date
slug
summary
category
URL
tags
icon
排序 | 稳定性 | 排序方式 | 最坏 | 平均 | 最好 | 空间复杂度 |
冒泡排序 | 稳定 | 内部 | ||||
选择排序 | 稳定 | 内部 | ||||
插入排序 | 稳定 | 内部 | ||||
希尔排序 | 不稳定 | 内部 | ||||
堆排序 | 不稳定 | 内部 | ||||
快速排序 | 不稳定 | 内部 | 平均
最优
最坏 | |||
归并排序 | 稳定 | 外部 | ||||
计数排序 | 稳定 | 外部 | ||||
桶排序 | 稳定 | 外部 | ||||
基数排序 | 稳定 | 外部 |
- 稳定：在原序列中，
r[i]=r[j]，而且r[i]在r[j]之前；排序之后，r[i]仍在r[j]之前，则称这种排序算法是稳定的
- 不稳定：在原序列中，
r[i]=r[j]，而且r[i]在r[j]之前；排序之后，r[i]可能出现在r[j]后面，则称这种排序算法是不稳定的
桶排序的平均时间复杂度为线性的，其中。 如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到。 当然桶排序的空间复杂度为，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。 此外，桶排序是稳定的。
数学上的时间复杂度不代表实际运行时的情况
堆排比较的几乎都不是相邻元素，对cache极不友好，这才是很少被采用的原因。
冒泡排序
它重复地走访过要排序的数列，依次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
改进的冒泡排序
上面代码中里面一层的循环，如果某次扫描中没有执行交换，则说明此时数组已经全部有序列。进一步研究我们发现，如果
R[i..n]已是有序区间，上次的扫描区间是R[0..i]，记上次扫描时最后一次执行交换的位置为lastSwapPos，则lastSwapPos在0与i之间，不难发现R[lastSwapPos..n]区间也是有序的，否则这个区间也会发生交换；所以下次扫描区间就可以由R[0..i]缩减到[0..lastSwapPos]。- 空间复杂度：假设数组的元素个数是 ，整个排序的过程中，直接在给定的数组里进行元素的两两交换。
- 时间复杂度：
- 情景一：给定的数组按照顺序安排好只需要进行 次的比较，两两交换次数为 0，时间复杂度 ，这是最好的情况。
- 情景二：给定的数组按照逆序排列需要进行 次比较，时间复杂度是 ，这是最坏的情况。
- 情景三：给定的数组杂乱无章在这种情况下，平均时间复杂度是 。
选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
插入排序（链式存储方式）
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
- 空间复杂度：假设数组的元素个数是 ，整个排序的过程中，直接在给定的数组里进行元素的两两交换。
- 时间复杂度：
- 情景一：给定的数组按照顺序安排好只需要进行 次的比较，两两交换次数为 0，时间复杂度 ，这是最好的情况。
- 情景二：给定的数组按照逆序排列需要进行 次比较，时间复杂度是 ，这是最坏的情况。
- 情景三：给定的数组杂乱无章在这种情况下，平均时间复杂度是 。
希尔排序
希尔排序是简单插入排序的改进版。它与插入排序的不同之处在于，是将整个有序序列分割成若干小的子序列分别进行插入排序。下图的数组长度为10，其增量序列为：5（10/2），2（5/2），1（2/2），第一趟排序将增量为5的子序列进行插入排序，第二趟排序将增量为2的子序列进行插入排序，第三趟将增量为1的子序列进行插入排序，最终完成排序。
时间复杂度
希尔排序的时间复杂度与增量(即，步长gap)的选取有关。例如，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为 ；而Hibbard增量的希尔排序的最坏时间复杂度为 ，平均的时间复杂度为 ，Hibbard增量序列的取法为 ：
堆排序
堆是一个近似完全二叉树的结构，并同时满足子结点总是小于（或者大于）它的父节点。
堆排序的建堆复杂度为 ，循环调堆的复杂度是。总运行时间 。对于堆排序的最好情况与最坏情况的运行时间，因为最坏与最好的输入都只是影响建堆的运行时间 或者 ，而在总体时间中占重要比例的是循环调堆的过程，即 = 。因此最好或者最坏情况下，堆排序的运行时间都是 。而且堆排序还是 原地算法，所以空间复杂度是 。
用数组存储大顶堆
python API实现
归并排序
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
- 空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：；所以空间复杂度为:
快速排序
在数组中随机选一个数（默认数组首个元素），数组中小于等于此数的放在左边部分，大于等于此数的放在右边部分，这个操作确保了这个数是处于正确位置的，再对左边部分数组和右边部分数组递归调用快速排序，重复这个过程。直到整个序列有序。
空间复杂度
快排并没有开辟空间，但是使用了递归，递归会开辟栈帧。每次递归所需要的空间大小都是一样的而且就算是第N次递归，每次递归所需的栈空间也是一样的，所以每次递归中需要的空间是一个常量，并不会随着的变化而变化，每次递归的空间复杂度就是。所以递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度 = 每次递归的空间复杂度 * 递归深度
- 最好情况：整个数组被分成两段长度相等的子数组时，递归深度是。递推式如下
- 最坏情况：待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，复杂度是。递推式如下：
时间复杂度
- 最好情况：整个数组被分成两段长度相等的子数组时，复杂度是。递推式如下
- 最坏情况：待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，复杂度是。递推式如下：
代码
C++
python
计数排序
将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。 给 个输入元素，每个元素都是 范围内的整数，其中 也是整数，计数排序算法的空间复杂度是 ，空间复杂度是 。
桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序。
- 桶排序的时间复杂度是 ，空间复杂度是 。
如果要排序的数据有n个，我们把它们分在k个桶中，这部分算法的时间复杂度是 。这样每个桶里的数据就是 。每个桶内排序的时间复杂度就为 。 个桶就是 ；在每个桶排序好之后，将每个桶中的元素合并到一起的时间复杂度是 。综上，算法复杂度是。当桶的个数接近数据个数时，就是一个较小的常数，所以时间复杂度接近。
基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
设待排序的数组 ，数组中最大的数是 位数，基数为 （如基数为10，即10进制，最大有10种可能，即最多需要10个桶来映射数组元素）。处理一位数，需要将数组元素映射到 个桶中，映射完成后还需要收集，相当于遍历数组一遍，最多元素数为 ，则时间复杂度为 。所以，总的时间复杂度为 。
