排序专题

简要比较

来源：排序算法 - 维基百科，自由的百科全书

名称	数据对象	稳定性	时间复杂度		额外空间复杂度	描述
			平均	最坏
冒泡排序	数组					（无序区，有序区）。 从无序区透过交换找出最大元素放到有序区前端。
选择排序	数组					（有序区，无序区）。 在无序区里找一个最小的元素跟在有序区的后面。对数组：比较得多，换得少。
	链表
插入排序	数组、链表					（有序区，无序区）。 把无序区的第一个元素插入到有序区的合适的位置。对数组：比较得少，换得多。
堆排序	数组					（最大堆，有序区）。 从堆顶把根卸出来放在有序区之前，再恢复堆。
归并排序	数组					把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。 可从上到下或从下到上进行。
					如果不是从下到上
	链表
快速排序	数组					（小数，基准元素，大数）。 在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。
	链表
希尔排序	数组					每一轮按照事先决定的间隔进行插入排序，间隔会依次缩小，最后一次一定要是 1。
计数排序	数组、链表					统计小于等于该元素值的元素的个数 i，于是该元素就放在目标数组的索引 i 位（i≥0）。
桶排序	数组、链表					将值为 i 的元素放入 i 号桶，最后依次把桶里的元素倒出来。
基数排序	数组、链表					一种多关键字的排序算法，可用桶排序实现。

• 均按从小到大排列
• k 代表数值中的 "数位" 个数
• n 代表数据规模
• m 代表数据的最大值减最小值

相关概念

• 稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。
• 原地算法

详情

• 算法学习/排序/堆排序