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

比较分析

排序类别	排序算法	时间复杂度（最好）	时间复杂度（最坏）	时间复杂度（平均）	辅助空间复杂度	稳定性
插入排序	直接插入排序	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)	稳定

快速排序

步骤：

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

![[Pasted image 20241226134232.png]]

冒泡排序

步骤：

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

图示：
假设初始序列为：

索引	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 说明在此轮中没有交换产生，数列已经有序
(这样防止了在排序过程中，某轮结束后，已经有序但是仍然遍历的情况)