[AlgoGo]排序算法
如何分析一个排序算法？
执行效率
- 最好、最坏、平均时间复杂度
最先需要考虑就是这三种时间复杂度，反应了算法随着问题规模增加求解时间的变化趋势。有的算法在近似有序和完全无序的情况下时间复杂度不同，所以需要分别分析。
- 时间复杂度系数、常数、低阶
当问题规模较小时，系数、常数、低阶等的影响会比较大，因此也考虑在内。
- 比较次数和交换次数
当复杂度相同时，两个算法的比较次数和交换次数决定了哪个耗时更少。
内存消耗
原地排序空间复杂度O(1)
稳定性
序列中相同大小的元素，在排序之后顺序是否会改变，不改变则为稳定排序算法
| 是否原地排序 | 是否稳定 | 最好、最坏、平均 | |
|---|---|---|---|
| 冒泡 | 是 | 是 | O(n) O(n^2) O(n^2) |
| 插入 | 是 | 是 | O(n) O(n^2) O(n^2) |
| 选择 | 是 | 否 | O(n^2) O(n^2) O(n^2) |
| 归并 | 否 | 是 | O(nlogn) |
| 快排 | 是 | 否 | O(nlogn) O(nlogn) O(n^2) |
基于比较的排序算法
冒泡、插入、选择 这三种算法都是基于比较的排序算法，因为需要逐个比较相邻元素，所以时间复杂度都是O(n^2)。
- 冒泡排序：
每次都比较相邻两个元素，较大的交换至后边，交换到最后的元素即本轮最大，每次遍历少遍历一个已排序的元素，遍历n次完成排序。
可以通过判断如果某轮一次交换也没有发生，则认为排序完成，提前退出。
- 插入排序
从第二个元素开始向后遍历，每次遍历将当前元素与其之前的元素挨个比较（从后往前比），当遇到小于当前元素的则插入到该元素后边，遍历完成后完成排序。
相比冒泡排序没有交换操作，赋值运算的次数更少。
- 选择排序
记录已排序的位置i，每次遍历i之后所有元素，找到最小的元素位置，将最小元素交换至i处，i增加1，当i到达数组尾部排序结束。
因为每次遍历都会从剩余元素中找最小，比较所有剩余的元素，所以时间复杂度无论最好最坏都是O(n^2)。反观插入和冒泡均可以在数组本来有序的情况下减少比较次数，时间复杂度最好可以到O(n)。
基于分治的排序
- 归并排序
递归实现，将数据分成前后两个部分，分别对两个部分进行归并排序，最后将两个部分的有序数据合并成一个。合并的过程需要O(n)的空间，因此不是原地排序。
- 快速排序
递归实现，同样将数据分成前后两个部分，分别对两个部分进行快速排序。在排序前需要选择pivot，保证pivot前的数全部小于pivot，pivot后边的数全部大于pivot。
外排序（空间要求多的）
- 桶排序
将待排序的数分成若干个组，在组内使用其他排序方式，然后按顺序合并多个组，得到有序数列。
- 计数排序
特殊的桶排序，每个数据一个桶
- 基数排序
应用场景有限，数据的每一位可以单独分离出来，从低位到高位将位数排序可以得到数据的顺序。
