共计 2631 个字符，预计需要花费 7 分钟才能阅读完成。
疾速排序
首先选一个基准 pivot，而后过一遍数组，
- 把小于 pivot 的都挪到 pivot 的右边，
- 把大于 pivot 的都挪到 pivot 的左边。
这样一来，这个 pivot 的地位就确定了，也就是排好了 1 个元素。
而后对 pivot 右边 ???? 的数排序，
对 pivot 左边 ???? 的数排序，
就实现了。
那怎么排右边和左边？
答：同样的办法。
所以快排也是用的 分治法 的思维。
「分」
抉择一个 pivot，就把问题分成了
- pivot 右边
- pivot 左边
这两个问题。
「治」
就是最开始形容的办法，直到每个区间内 没有元素或者只剩一个元素 就能够返回了。
「合」
放在一起天然就是。
然而如何抉择这个 pivot？
取两头的？
取第一个？
取最初一个？
举个例子：{5, 2, 1, 0, 3}.
比方选最初一个，就是 3.
而后咱们就须要把除了 3 之外的数分成「比 3 大」和「比 3 小」的两局部，这个过程叫做 partition（划分）。
这里咱们依然应用「挡板法」的思维，不必真的弄两个数组来存这两局部，而是用两个挡板，把区间划分好了。
咱们用「两个指针」（就是挡板）把数组分成「三个区间」，那么
- 右边的区间用来放小于 pivot 的元素；
- 左边的区间用来放大于 pivot 的元素；
- 两头是未排序区间。
那么初始化时，咱们要保障「未排序区间」可能蕴含除了 3 之外的所有元素，所以
- 未排序区间 = [i, j]
这样右边和左边的区间就成了：
- [0, i)：放比 3 小的数；
- (j, array.length -2]：放比 3 大的数
留神 ⚠️ i, j 是不蕴含在左右区间里的呢。
那咱们的目标是 check 未排序区间里的每一个数，而后把它归到正确的区间里，以此来放大未排序区间，直到没有未排序的元素。
从左到右来 check：
Step1.
5 > 3, 所以 5 要放在右区间里，所以 5 和 j 指向的 0 替换一下：
这样 5 就排好了，指针 j –，这样咱们的未排序区间就少了一个数；
Step2.
0 < 3，所以就应该在右边的区间，间接 i++；
Step3.
2 < 3，同理，i++；
Step4.
1 < 3，同理，i++；
所以当两个指针错位的时候，咱们完结循环。
然而还差了一步，3 并不在正确的地位上呀。所以还要把它插入到两个区间两头，也就是和指针 i 替换一下。
齐姐申明：这里并不激励大家把 pivot 放最右边。
根本所有的书上都是放左边，既然放左右都是一样的，咱们就依照大家默认的、达成共识的来，没必要去“别树一帜”。
就比方围棋的四个星位，然而考究棋道的就是先落本人这边的星位，而不是伸着胳膊去够对手那边的。
那当咱们把 pivot 换回到正确的地位上来之后，整个 partition 就完结了。
之后就用递归的写法，对左右两边排序就好了。
最初还有两个问题想和大家讨论一下：
- 回到咱们最后 抉择 pivot的问题，每次都取最初一个，这样做好不好？
答：并不好。
因为咱们是想把数组宰割的 更平均 ， 平均的工夫复杂度更低；然而如果这是一个有序的数组，那么总是取最初一个是最不平均的取法。
所以应该 随机 取 pivot，这样就防止了因为数组自身的特点总是取到最值的状况。
- pivot 放在哪
随机选取之后，咱们还是要把这个 pivot 放到整个数组的最左边，这样咱们的未排序区间才是 间断的，否则每次走到 pivot 这里还要想着跳过它，心好累哦。
class Solution {public void quickSort(int[] array) {if (array == null || array.length <= 1) {return;}
quickSort(array, 0, array.length - 1);
}
private void quickSort(int[] array, int left, int right) {
// base case
if (left >= right) {return;}
// partition
Random random = new Random(); // java.util 中的随机数生成器
int pivotIndex = left + random.nextInt(right - left + 1);
swap(array, pivotIndex, right);
int i = left;
int j = right-1;
while (i <= j) {if (array[i] <= array[right]) {i++;} else {swap(array, i, j);
j--;
}
}
swap(array, i, right);
//「分」quickSort(array, left, i-1);
quickSort(array, i+1, right);
}
private void swap(int[] array, int x, int y) {int tmp = array[x];
array[x] = array[y];
array[y] = tmp;
}
}
这里的时空复杂度和分的是否平均有很大关系，所以咱们分状况来说：
1. 均分
工夫复杂度
如果每次都能差不多平均分，那么
- 每次循环的耗时次要就在这个 while 循环里，也就是 O(right – left)；
- 均分的话那就是 logn 层；
- 所以总的工夫是 O(nlogn).
空间复杂度
- 递归树的高度是 logn，
- 每层的空间复杂度是 O(1)，
- 所以总共的空间复杂度是 O(logn).
2. 最不平均
如果每次都能取到最大 / 最小值，那么递归树就变成了这个样子：
工夫复杂度
如上图所示：O(n^2)
空间复杂度
这棵递归树的高度就变成了 O(n).
3. 总结
理论呢，大多数状况都会靠近于 平均 的状况，所以平均的状况是一个 average case.
为什么看起来最好的状况实际上是一个均匀的状况呢？
因为即便如果没有取到最两头的那个点，比方分成了 10% 和 90% 两边的数，那其实每层的工夫还是 O(n)，只不过 层数变成了以 9 为底的 log，那总的工夫还是 O(nlogn).
所以快排的均匀工夫复杂度是 O(nlogn)。
稳定性
那你应该能看进去了，在 swap 的时候，曾经毁坏了元素之间的绝对程序，所以快排并不具备稳定性。
这也答复了咱们结尾提出的问题，就是
-
为什么对于 primitive type 应用快排，
- 因为它速度最快；
-
为什么对于 object 应用归并，
- 因为它具备稳定性且快。
以上就是快排的所有内容了，也是很常考的内容哦！那下一篇文章我会讲几道从快排引申进去的题目，猜猜是什么？????
如果你喜爱这篇文章，记得给我点赞留言哦～你们的反对和认可，就是我创作的最大能源，咱们下篇文章见！
我是小齐，纽约程序媛，终生学习者，每天晚上 9 点，云自习室里不见不散！
更多干货文章见我的 Github: https://github.com/xiaoqi6666…
