12.快速排序

1荷兰国旗问题

①问题1： 给定一个数组arr和一个数num，将小于等于num的数放在数组的左边大于num的数放在数组的右边（不要求有序）。要求额外空间复杂度为O(1),时间复杂度为O(N)。

遍历数组元素，根据以下两种情况处理：

1. 当前数nums[i] < =num,nums[i]和≤区的下一个数交换，≤区右扩，i++
2. 当前数nums[i]>num，i++

【例】给定数组nums[3 5 6 7 4 3 8],给定一个数num

【代码如下】

void process(vector<int> &nums, int target) {
    int less = -1; //小于等于区
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] <= target) {
            swap(nums[++less], nums[i]);
        }
    }
}

②问题2：（荷兰国旗问题）： 给定一个数组arr和一个数num，将小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度为O(1),时间复杂度为O(N)。

遍历数组元素，根据以下两种情况处理：

1. 当前元素nums[i]<num,[i]和＜区下一个交换，＜区右括，i++
2. 当前元素nums[i]==num,i++
3. 当前元素nums[i]>num,[i]进而＞区前一个交换，＞区右扩，i不变

【例】给定数组nums[3 5 6 7 4 3 8],给定一个数num

【代码如下】

void process(vector<int> &nums, int target) {
    int less = -1, more = nums.size();
    for (int i = 0; i < more; ++i) {
        if (nums[i] < target) {
            swap(nums[++less], nums[i]);
        } else if (nums[i] == target) {
            continue;
        } else {
            swap(nums[--more],nums[i]);
            i--;
        }
    }
}

2快排1.0版本

选择[L, R]范围上的最后一个元素为target，在[L,R]上大于等于target或小于target分为小于等于区和大于区。此时小于区的最后一个元素已经排序完成，分别在小于区和大于区递归调用。

【代码】

//在[L,R]范围上划分小于等于区和大于区
int process(vector<int>& nums, int L, int R) {
    int less = L - 1; //小于等于区左边界
    //从L到大于区左边界遍历，分为两种情况处理
    for (int i = L; i <= R; ++i) {
        if (nums[i] <= nums[R]) {
            swap(nums[++less], nums[i]);
        }
    }
    return less;
}
void quickSort(vector<int>& nums, int L, int R) {
    if (L >= R) {
        return;
    }
    int target = nums[R];
    int mid = process(nums, L, R);
    quickSort(nums, L, mid - 1);
    quickSort(nums, mid + 1, R);
}

3快排2.0版本

利用荷兰国旗，在[L,R]范围上选择最后一个元素最为target，在[L,R]上根据大于target、小于target、等于target分出大于区、小于区、等于区，此时等于区的元素排序已经完成，分别在小于区和大于区递归调用。对比1.0版本，由于多了等于区，如果重复元素比较多，将比1.0版本省去很多比较步骤。

【代码】

//在[L,R]范围上划分小于区等于区大于区。
//返回数组vec长度为2，vec[0]是等于区左边界，vec[1]是等于区右边界
vector<int> process(vector<int>& nums, int L, int R) {
    int less = L - 1, more = R + 1;
    int target = nums[R];
    vector<int> res(2);
    for (int i = L; i < more; ++i) {
        if (nums[i] < target) {
            swap(nums[++less], nums[i]);
        } else if (nums[i] == target) {
            continue;
        } else {
            swap(nums[--more], nums[i--]);
        }
    }
    res[0] = less + 1;
    res[1] = more - 1;
    return res;
}
void quickSort(vector<int> &nums, int L, int R) {
	if (L >= R) {
        return;
    }
    vector<int> vec = process(nums, L, R);
    quickSort(nums, L, vec[0] - 1);
    quickSort(nums, vec[1] + 1, R);
}

4快排3.0版本

在2.0的基础上随机选取一个元素作为target。对比2.0版本，如果完全倒序，时间复杂度将退回O(N^2)，而采用随机选取元素将会保持时间复杂度为O(NlogN)。

//在[L,R]范围上划分小于区等于区大于区。
//返回数组vec长度为2，vec[0]是等于区左边界，vec[1]是等于区右边界
vector<int> process(vector<int>& nums, int L, int R) {
    int less = L - 1, more = R + 1;
    int select = L + rand() % (R - L + 1);
    int target = nums[select];
    vector<int> res(2);
    for (int i = L; i < more; ++i) {
        if (nums[i] < target) {
            swap(nums[++less], nums[i]);
        }
        else if (nums[i] == target) {
            continue;
        }
        else {
            swap(nums[--more], nums[i--]);
        }
    }
    res[0] = less + 1;
    res[1] = more - 1;
    return res;
}
void quickSort(vector<int>& nums, int L, int R) {
    if (L >= R) {
        return;
    }
    vector<int> vec = process(nums, L, R);
    quickSort(nums, L, vec[0] - 1);
    quickSort(nums, vec[1] + 1, R);
}