快排

快排

• 快速排序的最优情况是每一次取到的元素都刚好平分整个数组，T(n) = 2 * T(n/2) + O(n)，由 master 公式得到算法的时间复杂度为 O(nlogn)，空间复杂度为 O(logn)
• 最坏情况是数组本身有序，每一次取到的元素都是待排序列中的最值，效果相当于冒泡排序。这种情况下，算法的时间复杂度是 O(n^2)，空间复杂度为 O(n)

经典快排

• 确定性的快排在选取主元的时候，每次都选取最左边的元素。当序列为有序时，会发现划分出来的两个子序列一个里面没有元素，而另一个则只比原来少一个元素。为了避免这种情况，引入随机化来破坏这种有序状态。

#include <vector>

using namespace std;

class Solution {
public:
    void quickSort(vector<int> &array, int left, int right) {
        if (left >= right) return;
        int i = left;
        int j = right;
        int pivot = array[left];

        while (i < j) {
            while (i < j && pivot <= array[j]) {
                j--;
            }
            if (i < j) {
                array[i] = array[j];
                i++;
            }
            while (i < j && pivot >= array[i]) {
                i++;
            }
            if (i < j) {
                array[j] = array[i];
                j--;
            }
        }
        array[i] = pivot;
        quickSort(array, left, i - 1);
        quickSort(array, i + 1, right);
    }

    vector<int> sortArray(vector<int> &nums) {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

随机快排

• 在随机化的快排里面，随机选取待排序列中的一个元素作为主元，然后再进行划分，就可以降低选到最值的概率。

#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

class Solution {
public:
    void quickSort(vector<int> &nums, int left, int right) {
        if (left >= right) return;
        int i = left;
        int j = right;

        // 随机选个位置和第一个位置交换一下
        srand(time(nullptr));
        int pick = left + (rand() % (right - left + 1));
        swap(nums[left], nums[pick]);
        int pivot = nums[left];

        while (i < j) {
            while (i < j && nums[j] >= pivot) j--;
            if (i < j) nums[i++] = nums[j];
            while (i < j && nums[i] <= pivot) i++;
            if (i < j) nums[j--] = nums[i];
        }
        nums[i] = pivot;
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }

    vector<int> sortArray(vector<int> &nums) {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

荷兰国旗问题

• 也是由大佬 Edsger Dijkstra 提出的

75. 颜色分类

#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

class Solution {
public:
    void sortColors(vector<int> &nums) {
        // 下个放 0 的位置
        int left = 0;
        // 下个放 2 的位置
        int right = nums.size() - 1;
        int index = 0;
        while (index <= right) {
            // 如果 nums[index] 是 2，就放到最右边，直到这个位置不是 2
            while (index <= right && nums[index] == 2) {
                swap(nums[index], nums[right]);
                right--;
            }
            // 如果最后是 0，就发给到左侧区域
            if (nums[index] == 0) {
                swap(nums[index], nums[left]);
                left++;
            }
            index++;
        }
    }
};

荷兰国旗版快排

• 原版的快排只能以 pivot 为中心，小于等于 pivot 的在左侧，大于在右侧，之确保左侧最后一个是 pivot。处理过程是从两侧向中间。
• 荷兰国旗版快排，可以将所有等于 pivot 的放到一起，处理过程是从左到右。

912. 排序数组

#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

class Solution {
public:
    // 把所有等于 pivot 的元素都放到一起
    void quickSort(vector<int> &nums, int left, int right) {
        if (left >= right) return;

        // 随机选个位置和第一个位置交换一下
        srand(time(nullptr));
        int pick = left + (rand() % (right - left + 1));
        swap(nums[left], nums[pick]);
        int pivot = nums[left];

        // 下一个严格小于 pivot 的元素应该放的地方
        int l = left;
        // 下一个严格大于 pivot 的元素应该放的地方
        int r = right;

        int index = l;
        while (index <= r) {
            // 如果 nums[index] 大于 pivot，就放到最右边，直到这个位置不再大于 pivot
            while (index <= r && nums[index] > pivot) {
                swap(nums[index], nums[r]);
                r--;
            }
            // 此时 nums[index] 只会小于等于 pivot
            // 再把严格小于 pivot 的移到左侧
            if (nums[index] < pivot) {
                swap(nums[index], nums[l]);
                l++;
            }
            index++;
        }

        quickSort(nums, left, l - 1);
        quickSort(nums, r + 1, right);
    }

    vector<int> sortArray(vector<int> &nums) {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
};