快速排序的细节
快速排序的核心思想是在待排序数组需要处理的范围内选一个枢纽，把小于等于枢纽值的元素都移到数组左边，大于等于枢纽值的元素都移到右边，然后再对两边的数组递归调用快速排序函数，直到处理范围只剩下一个元素。因此，快速排序的核心就是划分数组，这也是快速排序的难点。很明显，我们需要两个指针，让左边的指针指向大于枢纽的元素，右边的指针指向小于枢纽的元素，然后交换这两个指针指向的元素。这两个指针可以从两端往中间移动(以下简称双指针)；也可以都往同一个方向移动，只是其中一个指针移动得快一些(以下简称快慢指针)。
双指针划分(直接交换)
直接编写双指针划分函数可能比较困难，我们先看两个比较简单的双指针题目。
LeetCode 344. 反转字符串
这道题很简单，直接交换双指针指向的元素即可，然后left指针向右移动一格，right指针向左移动一格。很明显，只有left < right时我们才需要进行交换。需要注意是否正确处理了可能出现的指针越界的情况。这里指针确实有可能越界(比如数组只有一个元素，那么完成一次移动后 left == 1， right == -1)，但是每个指针每次只移动一格，而且移动后都会检测是否有left < right，如果不满足left < right，那么不会访问数组。因此只要数组非空，这段代码不会出现数组下标越界的运行时异常。
class Solution {
public static void reverseString(final char[] s) {
if(s == null || s.length == 0) return;
for(int left = 0, right = s.length - 1; left < right; ++left, --right){
final char temp = s[left];
s[left] = s[right];
s[right] = temp;
}
}
}
LeetCode 905. 按奇偶排序数组
这道题也是双指针，不过不是每移动一格都要交换，而是发现左边指针并非指向偶数，右边指针并非指向奇数时再交换。因此，每个指针每次可能不只是移动一格，而是移动很多格，需要使用while语句。容易想到需要下面这两个while语句
while ((nums[left] & 1) == 0) ++left;
while ((nums[right] & 1) != 0) --right;
很遗憾，这样写是错的，我们不能直接把这两个while加到 reverseString 函数里面。因为我们不仅在for语句的小括号里面移动了指针，还在大括号里的while语句移动了指针。因此，需要在while语句下面检测是否有left < right。更麻烦的事情还在后面，如果数组里面全是奇数(或者偶数)，那么其中一个指针会越界，由于while语句内存在数组访问，因此while语句内会发生数组下标越界异常。因此，所有的while语句都要加上left < right的检测。经过小心的分析后，我得到了下面的代码
class Solution {
public static int[] sortArrayByParity(final int[] nums) {
if(nums == null || nums.length == 0) return nums;
for(int left = 0, right = nums.length - 1; left < right; ++left, --right){
while (left < right && (nums[left] & 1) == 0) ++left;
while (left < right && (nums[right] & 1) != 0) --right;
if(left >= right) break;
final int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
return nums;
}
}
LeetCode 912. 排序数组
有了这些铺垫，现在我们开始分析双指针的快速排序划分函数。很明显，划分函数的代码应该与 sortArrayByParity 函数类似。但是，我们不能直接这样写
for(int left = 0, right = nums.length - 1; left < right; ++left, --right){
while (left < right && nums[left] < pivot) ++left;
while (left < right && nums[left] > pivot) --right;
if(left >= right) break;
swap(nums, left, right);
}
原因是，我们需要把枢纽放在正确的位置，而正确的位置只有在for循环执行完才知道。
我们可能还出现了一个疑问，为什么while的判断是 nums[left] < pivot 和 nums[left] > pivot（以下简称方案1），而不是 <= 和 >=（以下简称方案2） 。事实上这两种判断都可以，但是黑皮书1指出，如果数组中枢纽出现了多次，使用方案1可避免划分出的两个子数组的大小相差太大，从而出现最坏的O(n^2)的情况。此外，目前我们使用方案1的判断，还有助于减少数组越界的可能性，减少一些其他的麻烦，具体情况下面会分析。
考虑这样一个数组，[3,1,2,4,0]，我们选择第0个元素作为枢纽，即pivot == 3
我们使用方案1，现在right指向元素0，left指向元素3，于是数组变成了[0,1,2,4,3]，很明显，枢纽没有放在正确的地方。即使我们使用方案2也是如此。原因在于，当某个指针停在枢纽时，无论我们是否选择交换双指针指向的元素，都是极其武断的，因为我们可能还有一些元素还没检测和交换，此时并不知道枢纽应该放在哪。所以，我们可以考虑先把枢纽移到处理范围之外，for循环执行完后，再把枢纽放进去
final int pivot = array[pivotPos];
int left = start;
swap(array, pivotPos, end);
for (int right = end - 1; ; ++left, --right){
while (array[left] < pivot) ++left;
while (left < right && array[right] > pivot) --right;
if(left >= right) break;
swap(array, left, right);
}
swap(array, left, end);
这里 ++left 那一行while语句删除了 left < right 的判断，因为我们把枢纽放在了最后，所以left肯定不会越界。而数组左边的元素可能都满足 array[right] > pivot，可能越界，因此 --right 的操作必须有 left < right 的判断。非常微妙的是，这里++left不能有 left < right 的判断，因为我们需要让left指针越过两个子数组的边界。比如，现在的数组是[2, 5, 1]，枢纽是5。我们把枢纽放在最后，得到了[2, 1, 5]，我们希望left能够指向5，即一个大于等于枢纽的数，这样我们 swap(array, left, right); 才能得到正确的结果，如果加上了left < right 的判断，则left无法越过子数组[2, 1]和[5]的中间边界，left指向1，最后得到的结果还是[2, 5, 1]。当然，++left的while语句可以加上left <= right 的判断，不过这是多余的。另外，可以在两个while语句都加上left <= right 的判断，不过这同样是不必要的。
我们还在for循环删除了 left < right 的判断，否则当待处理数组只有两个元素时，且left需要指向尾元素时，left将只能指向首元素。比如，有一个数组[2, 1]，移出枢纽后得到[1, 2]，则 end == 1，right == 0，left == 0。显然left应该指向2，但是由于不满足 left < right ，left不会自增，left依然指向1，所以得到的结果仍然是[2, 1]
由于枢纽已经放在了正确的位置，我们只需对闭区间[start, left - 1]和[left + 1, end]递归即可。由于left没有越界，所以我们可以保证这两个闭区间总是比原区间小，因此递归总是可以正确停止。
如果写成quickSort(array, start, left - 1); quickSort(array, left, end); 是错的，left可能等于start，此时范围没有减小，出现无限递归。
如果写成 quickSort(array, start, left); 和 quickSort(array, left, end); ，情况同上
如果写成quickSort(array, start, left); quickSort(array, left + 1, end); ，且pivotPos != end，则left会在pivotPos处停一下，并与right指针交换元素，这时right指针有机会像左移动至少一格，因此left指针不会到达end，在递归范围可以缩小，可以正确运行。如果pivotPos == end，且pivot是最大值，那么会有 left == end，出现无限递归
综上，我们得到了这样的代码
Code-DoublePointer-Swap-1
class Solution{
public static int[] sortArray(final int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static void quickSort(final int[] array, final int start, final int end){
if(start >= end) return;
final int pivotPos = (start + end) >> 1; //start,end也可
final int pivot = array[pivotPos];
int left = start;
swap(array, pivotPos, end);
for (int right = end - 1; ; ++left, --right){
while (array[left] < pivot) ++left;
while (left < right && array[right] > pivot) --right;
if(left >= right) break;
swap(array, left, right);
}
swap(array, left, end);
quickSort(array, start, left - 1);
quickSort(array, left + 1, end);
}
private static void swap(final int[] array, final int i, final int j){
final int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
如果要使用方案2，需要注意left指针遇到放在最右边的枢纽不会主动停下来，可能越界，因此必须在while语句加上left <= right的判断。right指针的while的判断也可以改成left <= right，可能有人觉得这样代码更美观。代码如下
Code-DoublePointer-Swap-2
class Solution{
public static int[] sortArray(final int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static void quickSort(final int[] array, final int start, final int end){
if(start >= end) return;
final int pivotPos = (start + end) >> 1; //start,end也可
final int pivot = array[pivotPos];
int left = start;
swap(array, pivotPos, end);
for (int right = end - 1; ; ++left, --right){
while (left <= right && array[left] <= pivot) ++left;
while (left < right && array[right] >= pivot) --right;
if(left >= right) break;
swap(array, left, right);
}
swap(array, left, end);
quickSort(array, start, left - 1);
quickSort(array, left + 1, end);
}
private static void swap(final int[] array, final int i, final int j){
final int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
双指针划分(直接交换，中位数)
前面的代码固定采用中间的元素作为枢纽，这在LeetCode上已经有很好的效率，执行用时都在10ms以下，而采用首元素或尾元素作为枢纽时执行用时都在1000ms左右。但是，黑皮书1并不建议这样做，作者说选中间的元素跟选首元素或尾元素本质上没有区别。目前还不清楚为什么在LeetCode上采用中间的元素作为枢纽会快那么多，不知道是不是测试用例的问题。黑皮书1建议采用首元素、中间元素和尾元素的中位数作为枢纽。为了找到中位数，我们进行了三次比较交换，这样顺便把中位数放在了中间的位置，如下所示
final int midPos = (start + end) >> 1;
if(array[start] > array[midPos]) swap(array, start, midPos);
if(array[start] > array[end]) swap(array, start, end);
if(array[midPos] > array[end]) swap(array, midPos, end);
但是这里不建议直接把这段代码加到Code-DoublePointer-Swap-1中，因为尾元素已经大于等于枢纽，而执行swap(array, pivotPos, end); 会造成不必要的交换。因此应该跳过尾元素，执行swap(array, pivotPos, end - 1);。类似的，start指针指向的元素也应该跳过，因为这样元素肯定小于等于枢纽，无需移动。我们在前面已经指出Code-DoublePointer-Swap-1的for循环条件不能有left < right的判断，但是如果待处理数组只有2个元素，比如[0, 0]，那么end == 1，pivotPos == 0, right = -1，将发生数组越界异常。事实上，如果待处理数组只有不多于3个元素，完全可以在三次比较交换后返回，这样就避免了数组越界的问题。此外，由于现在首元素小于等于枢纽，因此 --right的while语句不需要left < right的判断了，这可以提高运行效率。现在得到的代码如下
Code-DoublePointer-Swap-Mid-1
class Solution{
public static int[] sortArray(final int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static void quickSort(final int[] array, final int start, final int end){
if(start >= end) return;
final int midPos = (start + end) >> 1;
if(array[start] > array[midPos]) swap(array, start, midPos);
if(array[start] > array[end]) swap(array, start, end);
if(array[midPos] > array[end]) swap(array, midPos, end);
int left = start + 1;
final int pivotPos = end - 1;
if(left >= pivotPos) return;
swap(array, pivotPos, midPos);
final int pivot = array[pivotPos];
for (int right = pivotPos - 1; ; ++left, --right){
while (array[left] < pivot) ++left;
while (array[right] > pivot) --right;
if(left >= right) break;
swap(array, left, right);
}
swap(array, left, pivotPos);
quickSort(array, start, left - 1);
quickSort(array, left + 1, end);
}
private static void swap(final int[] array, final int i, final int j){
final int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
黑皮书1提供的代码有所不同，如下
Code-DoublePointer-Swap-Mid-2
class Solution {
public static int[] sortArray(final int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static void quickSort(final int[] array, final int start, final int end){
if(start >= end) return;
final int midPos = (start + end) >> 1;
if(array[start] > array[midPos]) swap(array, start, midPos);
if(array[start] > array[end]) swap(array, start, end);
if(array[midPos] > array[end]) swap(array, midPos, end);
final int pivotPos = end - 1;
swap(array, midPos, pivotPos);
final int pivot = array[pivotPos];
int left = start;
for(int right = pivotPos; left < right;){
while (array[++left] < pivot){}
while (array[--right] > pivot){}
if(left >= right) break;
swap(array, left, right);
}
swap(array, left, pivotPos);
quickSort(array, start, left - 1);
quickSort(array, left + 1, end);
}
private static void swap(final int[] array, final int i, final int j){
final int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
由于while语句中的数组访问总是先自增/自减下标再使用，因此交换元素后不需要专门调整下标。此外，我们也不需要让left = start + 1，right = pivotPos - 1，因为先自增/自减下标实际上交换时使用的下标是开区间(left, right)，而while可能访问的下标是闭区间[left, right] 或 [left - 1, right + 1] (比如数组有2个元素，那么end == 1，pivotPos == 0，++left == 1，--right == -1)，必须保证这个闭区间合法，所以for循环加上了left < right的判断。奇怪的是，我们之前已经知道Code-DoublePointer-Swap-1中的for循环不能加上这个判断，为什么Code-DoublePointer-Swap-Mid-2的for循环就必须加上这个判断呢？原因是，Code-DoublePointer-Swap-1的数组访问范围是闭区间[start, end - 1]，函数的第一行代码确保了处理范围至少有2个元素，因此闭区间[start, end - 1]也肯定有元素，且这个区间后还有一个元素。而Code-DoublePointer-Swap-Mid-2使用的是(start, end - 1)开区间，如果处理范围只有2个元素，那么end == 1，right的初始值为0，并且会立即自减，并发生数组下标越界异常。至于Code-DoublePointer-Swap-1中left指针的问题在这里不存在，因为前面3个比较交换已经把这两个元素正确排序了，且有midPos == pivotPos == left，因此这里实际上不会移动任何元素。如果不想在for循环加上这个判断，可以像Code-DoublePointer-Swap-Mid-1那样做
Code-DoublePointer-Swap-Mid-3
class Solution {
public static int[] sortArray(final int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static void quickSort(final int[] array, final int start, final int end){
if(start >= end) return;
final int midPos = (start + end) >> 1;
if(array[start] > array[midPos]) swap(array, start, midPos);
if(array[start] > array[end]) swap(array, start, end);
if(array[midPos] > array[end]) swap(array, midPos, end);
if(start + 2 >= end) return;
final int pivotPos = end - 1;
swap(array, midPos, pivotPos);
final int pivot = array[pivotPos];
int left = start;
for(int right = pivotPos; ;){
while (array[++left] < pivot){}
while (array[--right] > pivot){}
if(left >= right) break;
swap(array, left, right);
}
swap(array, left, pivotPos);
quickSort(array, start, left - 1);
quickSort(array, left + 1, end);
}
private static void swap(final int[] array, final int i, final int j){
final int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
值得注意的是，黑皮书的代码(Code-DoublePointer-Swap-Mid-2、Code-DoublePointer-Swap-Mid-3)的开区间，while语句里的自增/减再使用以及3次比较交换是配套使用的，不可以修改一部分而不同时修改配套的其他部分。不可以直接删除3个比较交换，然后把双指针区间改成开区间(start - 1, end)，原因是现在首元素可能依然大于枢纽，甚至枢纽就是最小的元素，因此right指针可能越界，出现数组下标越界异常。不过这里for循环不需要left < right的判断，因为right指针初始指向的元素左边肯定有元素
Code-DoublePointer-Swap-ERROR-1
class Solution {
public static int[] sortArray(final int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static void quickSort(final int[] array, final int start, final int end){
if(start >= end) return;
final int pivotPos = (start + end) >> 1;
final int pivot = array[pivotPos];
swap(array, end, pivotPos);
int left = start - 1;
for(int right = end; ;){
while (array[++left] < pivot){}
while (array[--right] > pivot){}
//应该改成 while (left < right && array[--right] > pivot){}
if(left >= right) break;
swap(array, left, right);
}
swap(array, left, end);
quickSort(array, start, left - 1);
quickSort(array, left + 1, end);
}
private static void swap(final int[] array, final int i, final int j){
final int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
双指针划分(不直接交换)
学校的教材2给出了一种不用直接调用swap函数的代码，但是需要额外的变量记录枢纽值。该代码在LeetCode的运行效率与直接交换的代码差不多。代码如下，有改动
class Solution{
public static int[] sortArray(final int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static int partition(final int[] array, final int start, final int end){
final int pivotPos = (start + end) >> 1;
final int pivot = array[pivotPos];
array[pivotPos] = array[start];
int left = start;
for(int right = end; left < right; ){
while (left < right && array[right] >= pivot) --right;
array[left] = array[right];
while (left < right && array[left] <= pivot) ++left;
array[right] = array[left];
}
array[left] = pivot;
return left;
}
private static void quickSort(final int[] array, final int start, final int end){
if(start >= end) return;
final int pivotPos = partition(array, start, end);
quickSort(array, start, pivotPos - 1);
quickSort(array, pivotPos + 1, end);
}
}
快慢指针划分
我在某培训机构送给别人的鼠标垫发现了新的快速排序算法，代码如下
Code-FastSlowPointer-1
class Solution {
public int[] sortArray(final int[] nums) {
if(nums == null || nums.length == 0) return nums;
quickSort(nums, 0, nums.length - 1);
return nums;
}
public void quickSort(int array[], int low, int high){
int pivot, p_pos, i, t;
if(low < high){
p_pos = low;
pivot = array[p_pos];
for(i = low + 1; i <= high; i++){
if(array[i] < pivot){
p_pos++;
t = array[p_pos];
array[p_pos] = array[i];
array[i] = t;
}
}
t = array[low];
array[low] = array[p_pos];
array[p_pos] = t;
quickSort(array, low, p_pos - 1);
quickSort(array, p_pos + 1, high);
}
}
}
经过分析，该代码使用了快慢指针。鼠标垫上第二个if里面写的是array[i] > pivot，是从大到小排序，为了方便在 LeetCode 测试，我改成了array[i] < pivot。不过这段代码存在很多影响可读性的不规范的地方，比如函数参数array使用了C语言风格的数组类型声明形式，变量i可见范围太大，变量命名不规范，if的大括号中代码过多导致缩进较多，交换变量的代码冗余。因此我把代码改成了这样
Code-FastSlowPointer-2
class Solution {
public static int[] sortArray(final int[] nums) {
if(nums == null || nums.length == 0) return nums;
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static void quickSort(final int[] nums, final int start, final int end){
if(start >= end) return;
int slow = start;
final int pivot = nums[start];
for(int fast = start + 1; fast <= end; ++fast){
if(nums[fast] < pivot){
swap(nums, fast, ++slow);
}
}
swap(nums, start, slow);
quickSort(nums, start, slow - 1);
quickSort(nums, slow + 1, end);
}
private static void swap(final int[] array, final int i, final int j){
final int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
Code-FastSlowPointer-2的算法本质上与Code-FastSlowPointer-1没有区别，这两段代码在LeetCode上的运行时间都超过了1000ms，效率相当糟糕。我们需要想办法优化这段代码。容易发现，Code-FastSlowPointer-2使用首元素作为枢纽，这是不合适的。根据之前的经验，我猜测使用中间元素作为枢纽可以提高效率，于是有了下面的代码
Code-FastSlowPointer-3
class Solution {
public static int[] sortArray(final int[] nums) {
if(nums == null || nums.length == 0) return nums;
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static void quickSort(final int[] nums, final int start, final int end){
if(start >= end) return;
final int pivotPos = (start + end) >> 1;
final int pivot = nums[pivotPos];
swap(nums, start, pivotPos);
int slow = start;
for(int fast = start + 1; fast <= end; ++fast){
if(nums[fast] < pivot){
swap(nums, fast, ++slow);
}
}
swap(nums, start, slow);
quickSort(nums, start, slow - 1);
quickSort(nums, slow + 1, end);
}
private static void swap(final int[] array, final int i, final int j){
final int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
双指针划分(直接交换，中位数，不移出枢纽)
经过前面的分析，我们知道如果要使用直接交换的方法把枢纽放到正确的位置，那么必须先把枢纽移到外面。假如数组已经有序，那么这些代码会带来不必要的交换。那么，我们能否像[LeetCode 905. 按奇偶排序数组]那样直接使用双指针，容忍枢纽没有放到正确的位置的情况呢？答案是可以的，我们可以降低对划分函数的要求，我们把数组划分成两部分，左边的元素都小于等于枢纽，右边的元素都大于等于枢纽，但不要求枢纽放在两个子数组中间。我们可以直接删除修改Code-DoublePointer-Swap-Mid-1，2，3中的部分代码。我们已经知道left越过了两个子数组的中间边界，因此需要对闭区间[start, left - 1]和[left, end]进行递归。之前写的所有代码的left指针都没有越界，因此闭区间[start, left - 1]和[left + 1, end]肯定都比原区间小。然而，如果left == start，那么闭区间[left, end]与原区间相同，此时递归无法停止。又或者，left == end + 1，那么闭区间[start, left - 1]与原区间相同。如果使用中位数的划分，这个问题很容易解决，因为这些代码本身就可以确保left指针在左开右闭区间(start, end]内。
Code-DoublePointer-Swap-Mid-NoSwap-1
class Solution{
public static int[] sortArray(final int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static void quickSort(final int[] array, final int start, final int end){
if(start >= end) return;
final int midPos = (start + end) >> 1;
if(array[start] > array[midPos]) swap(array, start, midPos);
if(array[start] > array[end]) swap(array, start, end);
if(array[midPos] > array[end]) swap(array, midPos, end);
int left = start + 1;
int right = end - 1;
if(left >= right) return;
final int pivot = array[midPos];
for (; ; ++left, --right){
while (array[left] < pivot) ++left;
while (array[right] > pivot) --right;
if(left >= right) break;
swap(array, left, right);
}
quickSort(array, start, left - 1);
quickSort(array, left, end);
}
private static void swap(final int[] array, final int i, final int j){
final int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
Code-DoublePointer-Swap-Mid-NoSwap-2
class Solution {
public static int[] sortArray(final int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static void quickSort(final int[] array, final int start, final int end){
if(start >= end) return;
final int midPos = (start + end) >> 1;
if(array[start] > array[midPos]) swap(array, start, midPos);
if(array[start] > array[end]) swap(array, start, end);
if(array[midPos] > array[end]) swap(array, midPos, end);
final int pivot = array[midPos];
int left = start;
for(int right = end; left < right;){
while (array[++left] < pivot){}
while (array[--right] > pivot){}
if(left >= right) break;
swap(array, left, right);
}
quickSort(array, start, left - 1);
quickSort(array, left, end);
}
private static void swap(final int[] array, final int i, final int j){
final int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
Code-DoublePointer-Swap-Mid-NoSwap-3
class Solution {
public static int[] sortArray(final int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static void quickSort(final int[] array, final int start, final int end){
if(start >= end) return;
final int midPos = (start + end) >> 1;
if(array[start] > array[midPos]) swap(array, start, midPos);
if(array[start] > array[end]) swap(array, start, end);
if(array[midPos] > array[end]) swap(array, midPos, end);
if(start + 2 >= end) return;
final int pivot = array[midPos];
int left = start;
for(int right = end; ;){
while (array[++left] < pivot){}
while (array[--right] > pivot){}
if(left >= right) break;
swap(array, left, right);
}
quickSort(array, start, left - 1);
quickSort(array, left, end);
}
private static void swap(final int[] array, final int i, final int j){
final int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
双指针划分(直接交换，不移出枢纽)
也可以改写Code-DoublePointer-Swap-1。考虑到left需要在左开右闭区间(start, end]内，如果pivot是最小值，那么right会移到指向首元素，此时left == right。本来这时已经不需要交换了，但是为了让left不等于start，我让left == right时再进行一次交换，即把if的条件改成 left > right。代码如下
Code-DoublePointer-Swap-NoSwap-1
pivotPos = (start + end) >> 1
pivotPos = start
class Solution{
public static int[] sortArray(final int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static void quickSort(final int[] array, final int start, final int end){
if(start >= end) return;
final int pivotPos = (start + end) >> 1;//start也可
final int pivot = array[pivotPos];
int left = start;
for (int right = end; ; ++left, --right){
while (array[left] < pivot) ++left;
//while (left < right && array[left] < pivot) ++left; 也可
while (left <= right && array[right] > pivot) --right;
if(left > right) break;
swap(array, left, right);
}
quickSort(array, start, left - 1);
quickSort(array, left, end);
}
private static void swap(final int[] array, final int i, final int j){
final int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
pivotPos = end
class Solution{
public static int[] sortArray(final int[] nums) {
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static void quickSort(final int[] array, final int start, final int end){
if(start >= end) return;
final int pivotPos = end;
final int pivot = array[pivotPos];
int left = start;
for (int right = end; ; ++left, --right){
while (left <= right && array[left] < pivot) ++left;
while (left < right && array[right] > pivot) --right;
if(left >= right) break;
swap(array, left, right);
}
quickSort(array, start, left - 1);
quickSort(array, left, end);
}
private static void swap(final int[] array, final int i, final int j){
final int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
前面的不移出枢纽的代码都没有使用方案2，因为不移出枢纽本身就比较复杂，而方案2会带来更多问题。我尝试使用方案2编写了不移出枢纽的代码，不过这个代码还不是对的。考虑数组[0, 1, 1, 0]，枢纽等于1。如果使用方案1，我们会让最左边的1跟最右边的0交换，这可以得到正确的结果。如果使用方案2，那么会跳过所有的1，结果依然是[0, 1, 1, 0]。代码如下
Code-DoublePointer-Swap-NoSwap-ERROR-1
class Solution {
public static int[] sortArray(final int[] nums) {
if(nums == null || nums.length == 0) return nums;
quickSort(nums, 0, nums.length - 1);
return nums;
}
private static void quickSort(final int[] nums, final int start, final int end){
if(start >= end) return;
final int pivotPos = (start + end) >> 1;
final int pivot = nums[pivotPos];
int left = start;
for(int right = end; ; ){
while (left < right && nums[left] <= pivot) ++left;
while (left < right && nums[right] >= pivot) --right;
if(left >= right) break;
swap(nums, left++, right--);
}
quickSort(nums, start, left - 1);
quickSort(nums, left, end);
}
private static void swap(final int[] array, final int i, final int j){
final int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
总结
- 快速排序的细节很多，也很复杂。如果只是为了应付面试，建议直接默写事先准备好的代码，比如Code-DoublePointer-Swap-Mid-1或Code-DoublePointer-Swap-Mid-3。建议不要现场写之前没验证过的比较复杂的代码。
- 不移出枢纽的分析比移出枢纽复杂许多，代码有很多坑，非常容易写错，目前并没有发现不移出枢纽的代码的运行效率有明显提高。此外，由于没有把枢纽放到正确的位置，像剑指 Offer 40. 最小的k个数这样的题也不能用这种代码。不移出枢纽的实用性可能不大，本文对此的讨论到此为止。
- 无论是快速排序还是其他的双指针题目，都需要注意指针越界，指针相遇的处理。如果使用了递归，还必须确保子问题都比原问题小。
1. 数据结构与算法分析 C语言描述（原书第2版）典藏版，[美] 马克·艾伦·维斯（Mark.Allen.Weiss)，机械工业出版社，2019 ↩
2. 数据结构，吴伟民/李小妹，高等教育出版社，2017 ↩