常见的排序算法过程和比较分析

比较分析

排序类别	排序算法	时间复杂度（最好）	时间复杂度（最坏）	时间复杂度（平均）	辅助空间复杂度	稳定性
插入排序	直接插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定
插入排序	折半插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定
插入排序	希尔排序	O(n)	O(n²)	O(n^1.3)	O(1)	不稳定
交换排序	冒泡排序	O(n)	O(n²)	O(n²)	O(1)	稳定
交换排序	快速排序	O(nlog₂n)	O(n²)	O(nlog₂n)	O(log₂n)	不稳定
选择排序	简单选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
选择排序	堆排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(1)	不稳定
归并排序	二路归并排序	O(nlog₂n)	O(nlog₂n)	O(nlog₂n)	O(n)	稳定
基数排序	基数排序	O(d(n + k))	O(d(n + k))	O(d(n + k))	O(n + k)	稳定

快速排序

步骤：

1. 任取一元素作为枢轴（pivot），图中取的枢轴值为 56。
2. 将序列划分成两部分，左部分元素值 <= 枢轴，右部分元素值 >= 枢轴。
3. 然后递归处理左右部分，直到子序列为空或只剩一个元素。
   图示：
   pivot = 56

索引	0	1	2	3	4	5	6	7	8	9	10
值	空(56)	23	45	76	69	20	45	93	16	82	27
	👆left										👆right

index = 0 存放枢轴 56 ，
(1) 若 right 对应的值小于 56 则填到 left 处，然后 left++（此时 right 处有空需要左边的填到右边）
(2) 若 right 对应的值大于 56 则不需改变只需要 right--
(3) 若 (1) 成立则看 left++后指向的位置是否大于 56，若大于 56 则填到 right 处，后 right--；
若 left++后的值小于 56 则不改变位置 left++（空位仍在右边）
(4) 重复上述过程直到划分完毕

• 选择枢轴（pivot = 56）：
  • 左部分（left）：<= pivot
  • 右部分（right）：>= pivot
• 操作步骤：
  • right 从右往左找比枢轴小的元素去填 left 的坑。
  • left 从左往右找比枢轴大的元素去填 right 的坑。

冒泡排序

步骤：

1. 从序列的第一个元素开始，依次比较相邻的两个元素。
2. 如果前一个元素大于后一个元素，则交换它们的位置。
3. 对整个序列重复上述比较和交换操作，每次遍历都会将当前未排序部分的最大元素 “冒泡” 到末尾。
4. 持续进行上述操作，直到整个序列有序。

图示：
假设初始序列为：

索引	0	1	2	3	4	5	6	7	8	9	10
值	27	23	45	76	69	20	45	93	16	82	56

(1) 第一轮比较：

• 比较第 0 个元素和第 1 个元素（27 和 23），因为 27 > 23，交换位置。
• 序列变为：23，27，45，76，69，20，45，93，16，82，56
• 比较第 1 个元素和第 2 个元素（27 和 45），不交换。
• 依次类推，比较第 2 个元素和第 3 个元素（45 和 76），不交换……
• 比较第 9 个元素和第 10 个元素（82 和 56），因为 82 > 56，交换位置。
• 第一轮结束后，最大的元素 93 “冒泡” 到了末尾。
  (2) 第二轮比较：
• 重复上述比较和交换操作，但这次只需要比较到倒数第二个元素，因为最大元素已经在末尾了。
• 第二轮结束后，第二大的元素 82 “冒泡” 到了倒数第二个位置。
  (3) 持续进行上述操作：
• 每一轮都会将当前未排序部分的最大元素移动到正确位置。
• 直到整个序列有序。
• 操作步骤总结：
  • 每一轮从序列的开头开始，依次比较相邻元素，如果顺序不对就交换。
  • 每一轮过后，未排序部分的最大元素就会移动到末尾，下一轮比较的范围就减少一个元素。
  • 重复这个过程，直到整个序列有序。
    优化方式
• 设置一个 bool 类型的swapped 变量每一轮初始化为 false，只要在本轮内存在交换操作，那么久 swapped = true
• 如果某一轮执行完毕后 swapped 仍然为 fasle 说明在此轮中没有交换产生，数列已经有序
  (这样防止了在排序过程中，某轮结束后，已经有序但是仍然遍历的情况)

堆排序

堆

• 是个完全二叉树 (除最下面一层都是满的，最下面一层从左到右依次排序，没有空的)
• 大根堆 任意节点>=其左右孩子
• 小根堆 任意节点<=其左右孩子
  一般用顺序存储存放堆
  如下所示 上边是逻辑结婚下边是存储结构

下标从 1 开始 index有这个规律
父亲 = $\lfloor i/2\rfloor$ 左孩子 = $2i$ 右孩子 = $2i+1$

步骤

1. 建堆
   • 从最后一个非叶结点开始依次向下调整
2. 排序
   • 每轮堆顶换到最后，向下调整新的堆顶 (n - 1) 轮

手算

快速排序

• 手算快速排序时 L R 指针左右移动
• R 指到< pivot 的放到 L 处（L 原先为空， 放入后 R 为空 L 非空）
  然后视角切换到 L
  若 R 未指到< pivot 的则 R 继续移动
• L 指到> pivot 的放到 R 处（R 原先为空，放入后 L 为空 R 非空 ）
  然后视角切换到 R
  若 L 未指到> pivot 的则 L 继续移动
• L == R 时，pivot 归位
• 递归的处理 pivot 左右两边的部分，方法同上

堆排序

看到一组乱序关键字时

• 先按照关键字目前的顺序，依次填入一棵完全二叉树 (横着一行一行的填入)
• 然后依次调整树为大根堆/小根堆
• 调整完成之后树的根节点和最后一个关键字 (序号最大的) 调换位置
  此时的便是第一轮排序后的结果 (最后一个也就是刚由根节点调换过来的关键字已归位)
• 然后再不包括最后一个关键字的基础上对于前 n-1 个数重新做上述工作
• 直到每个关键字都归位