排序算法汇总
本文是对常见的排序算法的一个简单总结，也是算法导论第三版的一些摘要记录，以作备忘和查询。
1. 排序的定义：输入：n 个数的一个序列 输出：序列的一个排列 ，满足 a1’
2. 排序算法复杂度概览
- 稳定性：稳定的排序算法在排序过程中相等的元素之间的相对顺序不会发生变化。
- 内/外排序：内排序是所有排序操作都在内存中完成，而外排序则是由于数据太大，因此把数据放在磁盘中，通过磁盘和内存的数据传输才能进行排序。
- 时间复杂度：一个算法执行所耗费的时间。
- 空间复杂度：运行完一个程序所需内存的大小。
3. 术语解释
- 时间复杂度：算法的时间复杂度反映了算法执行时间随输入规模变化的情况。常见的排序算法时间复杂度有 O(n^2)、O(nlogn)、O(n) 等。
- 空间复杂度：描述算法所需额外空间的量级。
4. 关于时间复杂度的排序:
- (O(n^2)) 排序：简单排序如直接插入、选择和冒泡排序。
- (O(nlogn)) 排序：快速排序、堆排序、归并排序和部分情况下的计数排序、基数排序。
- O(n) 排序：基数排序（当数字的位数固定时）和桶排序（当桶的数量合适时）。
5. 稳定性排序算法：归并排序、基数排序、计数排序是稳定的排序算法。
接下来，将详细介绍几种典型的排序算法：
冒泡排序
语言描述：
1. 比较相邻的元素，如果第一个元素比第二个元素大，则交换它们的位置。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这样在最后的i-1次扫描后，最大（或最小）的元素就像被“推”（或“浮”）到正确的位置上。
3. 重复步骤1和2，直到没有更多的元素需要交换，也就是该序列已经排序完成。
伪代码描述及时间、空间复杂度略。
插入排序
语言描述：
1. 从第一个元素开始，认为该元素已被排序；取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，则将该元素移到下一位置；重复步骤3，直到找到已排序的元素小于或者等于新元素的位置或已遍历完有序序列。
4. 把新元素放到合适的位置。
5. 重复步骤3-4，直到所有元素均已排序。
伪代码描述及时间、空间复杂度略。
选择/简单选择排序
语言描述及时间、空间复杂度与插入排序类似。简单选择法是通过每次从待排序列中选择最小（或最大）的元素来与未排好的序列的第一个元素进行交换来达到目的的。每次找到最小（或最大）的元素需要 O(n) 的时间复杂度，所以总的时间复杂度为 O(n^2)。
希尔排序（缩小增量排序）
基本步骤：选择一个增量序列 t1，t2，...，tk，其中 ti > tj 且 t_k = 1；根据增量序列进行多轮间隔为 ti 的子序列直接插入排序；最后增量为 1 时对整个序列进行一次直接插入排序。时间复杂度为 O(nlogn)，但最差情况仍为 O(n^2)。空间复杂度为 O(1)。
归并排序（Merge Sort）
语言描述：分解待排序列为两个子序列，分别对这两个子序列进行归并排序；合并两个已排好的子序列得到一个有序序列。递归地完成这个操作直到整个序列有序为止。时间复杂度为 O(nlogn)，空间复杂度为 O(n)。
快速排序（Quick Sort）
语言描述：选择一个基准值作为基准；将小于基准的值放在左边，大于基准的值放在右边；递归地对基准值左右两侧进行同样的操作直到子序列完全有序。最佳情况下时间复杂度为 O(nlogn)，最差情况仍为 O(n^2)。空间复杂度根据实现方式不同而变化，但通常为 O(logn) 到 O(n)。