排序算法

术语解释

1. 稳定排序

如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。

2. 非稳定排序

如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。

3. 原地排序

原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。

4. 非原地排序

需要利用额外的数组来辅助排序。

5. 时间复杂度

一个算法执行所消耗的时间。

6. 空间复杂度

运行完一个算法所需的内存大小。

分类	算法
交换排序	冒泡排序鸡尾酒排序奇偶排序梳排序侏儒排序臭皮匠排序 Bogo排序
选择排序	选择排序堆排序平滑排序笛卡尔树排序锦标赛排序圈排序弱堆排序
插入排序	插入排序希尔排序伸展排序二叉查找树排序图书馆排序耐心排序
归并排序	归并排序梯级归并排序振荡归并排序多相归并排序
分布排序	桶排序计数排序基数排序美国旗帜排序珠排序爆炸排序比较计数排序插值排序鸽巢排序相邻图排序闪电排序
并发排序	双调排序器 Batcher归并网络两两排序网络
混合排序	块排序 Tim排序内省排序 Spread排序归并插入排序
其他	拓扑排序煎饼排序意粉排序

选择排序（selection sort）—
快速排序（quick sort）—期望时间，最坏情况；对于大的、随机数列表一般相信是最快的已知排序
希尔排序（shell sort）—如果使用最佳的现在版本
堆排序（heap sort）—
克洛弗排序（Clover sort）—期望时间，最坏情况[来源请求]
梳排序—
平滑排序（smooth sort）—
内省排序（introsort）—
耐心排序（patience sort）—最坏情况时间，需要额外的空间，也需要找到最长的递增子序列（longest increasing subsequence）

// 使用第三个变量

temp = n
n = m
m = temp

// 不使用第三个变量

m = m + n
n = m - n
m = m - n

m ^= n
n ^= m
m ^= n