快速排序原理与实现
快速排序
简介
快速排序是一种非常高效的排序算法，它使用了分治策略来递归地排序数组的不同部分。快速排序的核心在于它的**原地(partition)**函数，这个函数是算法性能的关键所在。
原地区分函数的工作原理：
-
选择枢轴(Pivot)：
快速排序首先从数组中选择一个元素作为枢轴（pivot）。枢轴的选择可以是数组中的任何元素，如第一个元素、最后一个元素、中间元素或随机元素。枢轴的好坏直接影响到快速排序的效率。 -
重新排序：
接下来，原地区分函数会重新排列数组中的元素，使得比枢轴小的所有元素都移动到枢轴的左边，而比枢轴大的所有元素都移动到右边。枢轴元素最终位于其最终位置，并且在这个位置左边的每一个元素都不大于枢轴，右边的每一个元素都不小于枢轴。 -
递归排序：
排序后，枢轴元素将数组分为两部分。算法递归地在枢轴的左右两边执行相同的操作，直到所有元素都正确排序。
时间复杂度分析
最优时间复杂度
在最优情况下，每次划分将数组近乎均等地分为两部分，即每次选择的枢纽（pivot）都位于数组的中间位置。这种情况下，快速排序的时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)，具体分析如下：
- 每次划分的复杂度：将长度为 (n) 的数组分成两部分，平均需要 (O(n)) 的时间。
- 递归调用的次数：每次划分后，问题规模减半，总共递归调用 l o g n log n logn 次。
综合起来，最优时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)。
平均时间复杂度
快速排序的平均时间复杂度也为 O ( n log n ) O(n \log n) O(nlogn)。在所有可能的输入序列中，大多数情况下，枢纽能将数组均匀划分为两个部分，因此其平均性能接近于最优情况。
最坏时间复杂度
在最坏情况下，每次选择的枢纽都是当前数组中的最小值或最大值，这会导致数组划分非常不均匀，即一个部分包含 n − 1 n-1