---

前言

最近学习了快速排序，简单记录一下。

---

引例：三色旗问题

问题描述：
有一个只由0，1，2三种元素构成的整数数组，请使用交换、原地排序而不是使用计数进行排序。

解题思路：
定义两个下标left和right；
left的含义：使数组中<=left的部分都比1小，left的初始值为-1；
right的含义：使数组中>=right的部分都比1大，right的初始值为n；
从index = 0开始遍历；
根据index所指向的值分别进行不同的操作；
如果a[index] = 0，与left对应的值交换；
如果a[index] = 1，index++；
如果a[index] = 2，与right对应的值交换。

代码如下：

void holand(int a[], int n) {
    int index = 0, left = -1, right = n;
    while (index < right) {
        if(a[index] == 0) {
            swap(a[index++], a[++left]);
        }
        else if (a[index] == 1) {
            index++;
        }
        else if (a[index] == 2) {
            swap(a[index], a[--right]);
        }
    }

}

快速排序

方式一：三个下标

这个快排的思想和三色旗问题的思想差不多。选择一个基准值，创建两个下标（加上基准值的下标就是三个了），使得小于前一个下标的位置全都比基准值小，大于后一个下标的位置的值都比基准值大。

这个方法是遍历到大于或者小于基准值就马上交换基准值和遍历到的元素的位置。

代码如下：

void quickSort(vector<int>& nums, int left, int right) {
    if (left > right) return;
    int stand = nums[left], index = left, i = left - 1, j = right + 1;
    while (index < j) {
        if (nums[index] < stand) {
            swap(nums[index++], nums[++i]);
        }
        else if (nums[index] > stand) {
            swap(nums[index], nums[--j]);
        }
        else
        {
            index++;
        }
    }
    nums[--index] = stand;  //之前的 if(nums[index] < stand)中的语句会多加一个1，此处将它减去
    quickSort(nums, left, index - 1);
    quickSort(nums, index + 1, right);
}

方法二：一般解法

1. 先找大于基准值的元素，
2. 再找小于基准值的元素，
3. 然后交换两个元素，
4. 遍历直到两个下标相遇，
5. 最后后把基准值放在两个下标相遇的位置。

注意：这里先找大于基准值的元素，后找小于基准值的元素，这个顺序不能改变。这和最后将基准值放到指定位置时有关。

void quickSort2(vector<int>& nums, int left, int right) { //找一大一小数，然后交换
    if (left >= right) return;
    int i = left, j = right, temp = nums[left];
    while (i != j) {
        while (i < j && nums[j] >= temp) {
            j--;
        }
        while (i < j && nums[i] <= temp)
        {
            i++;
        }
        Swap(nums[i], nums[j]);
    }
    nums[left] = nums[i];
    nums[i] = temp;
    quickSort2(nums, left, i);
    quickSort2(nums, i + 1, right);

方式三：挖坑法

1. 将基准值的位置作为坑（一般是第一个）。
2. 先移动左下标，找比基准值小的元素，将这个元素填到坑的位置，此时坑的位置就是刚刚找到的元素的位置
3. 再移动右下标，找比基准值大的元素，将这个元素填到刚刚的坑的位置。
4. 直到两个下标相遇。
5. 将基准值填到两个下标相遇的位置。

void quickSort3(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int i = left, j = right, temp = nums[left], index = left;
    while (i != j) {
        while (i < j && nums[j] >= temp) {
            j--;
        }
        nums[index] = nums[j];
        index = j;
        while (i < j && nums[i] <= temp)
        {
            i++;
        }
        nums[index] = nums[i];
        index = i;
    }
    nums[i] = temp;
    quickSort3(nums, left, i);
    quickSort3(nums, i + 1, right);
}

---

总结

总的来说还是挖坑法比较好，因为前两个方法每次都需要调用交换函数（swap），而挖坑法只用简单的赋值。同时我们可以发现第一种方法调用交换函数的频率比第二种方法要高很多。
笔者认为挖坑法的注意点是跟踪好坑的位置。坑的位置记好了，然后按照一大一小的顺序填坑就行了。