排序——快速排序（快慢指针实现）

之前总结过快排的两种解法，可以参考快排的两种常见解法，最近又发现一种更容易理解的方法，在这里做下记录。

这是一种使用 “快慢指针比较” 的方法，来实现快速排序算法。

实现快速排序算法的关键，先在数组中选择一个数字（可以理解为轴值），把数组中的数字分为两部分，比选择的数字小的数字移到数组的左边，比选择的数字大的数字移到数组的右边。

int partition(vector<int>& nums, int start, int end) {

    int index = (start + end) / 2;
    swap(nums, index, end);

    int small = start - 1;
    for (index = start; index < end; ++index) {
        if (nums[index] < nums[end]) {
            ++small;
            if (small != index) {
                swap(nums, small, index);
            }

        }
    }

    ++small;
    swap(nums, small, end);
    return small;
}

解释：

这里的快慢指针，index是快指针，small是慢指针，

慢指针指向的位置，其元素都是比轴值大，当快指针和轴值比较，对应的值比轴值小时，交换快指针和慢指针的值，就是把小的放在前面，快慢指针相同时，不用交换，

因为上次交换完，small指向的是上次交换完的结果，比轴值要小，把慢指针small往后移动一个，本次交换要把快指针index指向的新小元素挪到前面，如果small等于index就不用交换，如果small不等于index，在small和index之间的元素必定要比轴值大，所以可以实现，把小的元素放在前面，把大的元素放在后边，如果听到这里还不清楚，建议自己画图，实际走一遍。

确保慢指针从-1开始，最后再加回来，其上的值和轴值最后交换，完成一轮partition。

边缘条件

如果首次随机index对应的值是最大的数，一轮partition只把最大的数调到了最后，

如果首次随机index对应的值是最小的数，一轮partition只把最小的数调到了最前。

完整例子

例子：65,58,95,10,57,62,13,106,78,23,85

#include<vector>
#include<iostream>
#include<cstdlib>
using namespace std;

void swap(vector<int>& nums, int one, int two) {    // 交换操作
    int temp = nums[one];
    nums[one] = nums[two];
    nums[two] = temp;
}

int partition(vector<int>& nums, int start, int end) {    // 一轮数组分割
    int index = (start + end) / 2;    // 最科学的方法是随机选择轴值，这里选择中值也是可以的
    swap(nums, index, end);            // 把轴值放在数组的最后，完成一轮parttiion比较后，再把轴值交换回轴值在排序后该在的位置

    int small = start - 1;        // 保证慢指针small从0开始
    for (index = start; index < end; ++index) {        // 只交换比较start和end-1之间的数
        if (nums[index] < nums[end]) {        // 满足快指针的值小于轴值的条件时
            ++small;                        // 因为上次交换完，small指向的是上次交换完的结果，比轴值要小，把慢指针small往后移动一个，本次交换要把快指针index指向的新小元素挪到前面，如果small等于index就不用交换，如果small不等于index，在small和index之间的元素必定要比轴值大，所以可以实现，把小的元素放在前面，把大的元素放在后边，如果听到这里还不清楚，建议自己画图，实际走一遍。
            if (small != index) {            // 快慢指针相同时，不用交换
                swap(nums, small, index);
            }

        }
    }

    ++small;        // 因为之前开始时减了1，进行初始化，所以最后轴值该待的位置应该是small再加上1
    swap(nums, small, end); // 把轴值换到一次parttiion后正确的位置，这是轴值前面全是比它小的小的，轴值后面全是比它大的
    return small;
}

void quicksort(vector<int>& nums, int start, int end) {
    if (start == end)    // 相等的时候退出，从下往上合并
        return;
    int index = partition(nums, start, end);    // 分割
    if (index > start) {            // 边缘条件限制，必须加，否则会导致访问数组以外的地址，溢出
        quicksort(nums, start, index - 1);
    }
    if (index < end) {                // 同上
        quicksort(nums, index + 1, end);
    }
}

int main() {
    vector<int> numbers{3,2,1,5,6,4};

    quicksort(numbers, 0, numbers.size() - 1);

    for (int i = 0; i < numbers.size(); i++) {
        cout << numbers[i] << endl;
    }
    system("pause");
    return 0;
}