1. 思想
快速排序思想:
- 首先选出一个基准值
- 然后将小于基准值的数放在其左边,大于基准值的数放在其右边
- 最后递归对左子序列和右子序列排序
2. 算法
- 一直移动右指针,直到其值比基准值小
- 然后把右指针的值给左指针
- 一直移动左指针,直到其值比基准值大
- 然后把左指针的值给右指针
- 把基准值放在指针重合位置
- 递归排序左子序列和右子序列
3. 代码
参考视频:https://www.bilibili.com/video/BV1at411T75o?from=search&seid=3646433316569041770
public static void quickSort(int[] array, int l, int r) {
if (l >= r) {
return;
}
int left = l;
int right = r;
int p = l;
int pValue = array[p];
while (left < right) {
// 一定要先排右边,因为此时基准值取的左边
while (left < right && array[right] > pValue) {
right--;
}
if (left < right) {
array[left] = array[right];
}
while (left < right && array[left] <= pValue) {
left++;
}
if (left < right) {
array[right] = array[left];
}
}
array[left] = pValue;
quickSort(array, l, left - 1);
quickSort(array, left + 1, r);
}
PS:生成随机数组
int[] array = Stream.generate(() -> (int) (Math.random() * 100)).limit(10).mapToInt(x -> x).toArray();
4. 复杂度
算法 | 平均时间复杂度 | 最好 | 最坏 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|---|
快速排序 | $O(nlog_2n)$ | $O(nlog_2n)$ | $O(n^2)$ | $O(nlog_2n)$ | 内部排序 | 不稳定 |