快速排序
快速排序是对冒泡排序的优化，使用了分治的思想。
步骤
-
选择基准元素（Pivot）：从数组中选择一个元素作为基准。常见的选择方法有：
- 选择第一个元素
- 选择最后一个元素
- 选择中间的元素
- 随机选择一个元素
- 三数取中法（选择第一个、最后一个和中间值的中间值）
-
划分操作（Partition）：将数组重新排列，使得所有小于基准的元素都位于基准的左侧，而所有大于基准的元素都位于基准的右侧。基准元素位于最终位置。理想情况下左右划分应相对均匀。
-
递归排序：
- 对基准左侧的子数组进行快速排序
- 对基准右侧的子数组进行快速排序
-
合并：由于快速排序是在原地排序（in-place），不需要额外的合并步骤。
复杂度分析
理想情况(平均情况)
- 假设划分均匀，那么共需要
O(logn)时间。 - 每次划分对每个数排序，即
n次。时间复杂度为O(nlogn)
最坏情况
- 原数组有序，且基准元素选择不优秀； 假设有数组[1,2,3,4,5,6,7,8,9]，基准元素为最后一个，递增排序；
第一次划分
- 基准：9
- 左侧子数组：[1, 2, 3, 4, 5, 6, 7, 8]
- 右侧子数组：[]
第二次划分
- 基准：8
- 左侧子数组：[1, 2, 3, 4, 5, 6, 7]
- 右侧子数组：[]
第三次划分
- 基准：7
- 左侧子数组：[1, 2, 3, 4, 5, 6]
- 右侧子数组：[]
可以看出，这其实就是冒泡，复杂度为O(n^2)，也可以看出，这个算法不稳定
总结
- 快速排序是一种高效的排序算法，平均时间复杂度为
O(nlogn) - 在最坏情况下，时间复杂度可能退化为
O(n^2)，但通过优化基准元素的选择，可以减少这种情况的发生。 - 快速排序是不稳定的排序算法，可能会改变相同元素的相对顺序。