刷题 排序算法-基于交换的排序算法

冒泡排序

• 时间复杂度：最好情况 O(n), 最坏情况 O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // 冒泡排序

        for (int i = nums.size() - 1; i >= 1; --i) {
            bool swapped = false;
            for (int j = 0; j < i; ++j) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums[j], nums[j + 1]);
                    swapped = true;
                }
            }
            if (!swapped) { // 没有发生交换，说明代码已经有序
                break;
            }
        }

        return nums;
    }
};

快速排序 图解 - 分治法

步骤：

• 随机选取一个位置 nums[i] = x
• 将大于 x 的值都移到 nums[i] 的左边，小于 x 的值都移动到 nums[i] 的右边
• 对 nums[0 ~i -1] 和 nums[i + 1 ~ n -1] 分别进行快速排序
• …

步骤中的核心问题：如何 将大于 x 的值都移到 nums[i] 的左边，小于 x 的值都移动到 nums[i] 的右边?

• 时间复杂度：最好情况 O(n), 最坏情况 O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定

class Solution {
public:
    void quickSort(vector<int>& nums, int left, int right) {
        if (left >= right) return; // 递归终止条件
        int p = partition(nums, left, right);
        quickSort(nums, left, p - 1);
        quickSort(nums, p + 1, right);
    }

    int partition(vector<int>& nums, int left, int right) {
        int p = left + rand() % (right - left + 1); // 生成 [left ~ right] 区间内的随机数
        swap(nums[p], nums[right]); // 将 pivot 和末尾值交换
        int i = left;
        // 维护的区间： [left, i) 区间内的值小于等于 nums[right]
        // [j, right) 区间内的值大于 nums[right]
        for (int j = left; j < right; ++j) {
            if (nums[j] <= nums[right]) {
                // 此时不满足我们对区间的要求了
                // 调整区间使其满足要求
                // {nums[left] ... nums[i-1]} {[nums[i] ... nums[j]]}
                swap(nums[i], nums[j]);
                ++i;
                // --> {nums[left] ... nums[i-1] nums[j]} { ... nums[i]]}
            }
        }
        swap(nums[i], nums[right]);
        return i;
    }

    vector<int> sortArray(vector<int>& nums) {
        srand(time(0));     // 以当前时间为随机数种子
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

但是上面这段代码提交还是会超过时间限制，由于当前的快速排序在处理包含大量相同元素的数组时，表现不佳。快速排序在最坏情况下的时间复杂度是 O(n^2)

使用三向切分的快速排序

三向切分是对标准快速排序的一种改进，特别适用于处理大量重复元素的情况。它将数组分为三个部分：

• 小于基准的部分
• 等于基准的部分
• 大于基准的部分

通过三向切分，可以避免在处理大量重复元素时退化为 O(n²)，使得时间复杂度保持在 O(n log n)。

class Solution {
public:
    void quickSort3Way(vector<int>& nums, int left, int right) {
        if (left >= right) return; // 递归终止条件
        int pivot = nums[left + rand() % (right - left + 1)]; // 选取随机基准
        int lt = left, i = left, gt = right;  // 初始化 lt、i、gt 指针
        // [left ~ lt) 小于 pivot
        // [lt, gt] 等于 pivot
        // [gt + 1, right] 大于 pivot 
        while (i <= gt) {
            if (nums[i] < pivot) {
                swap(nums[lt], nums[i]);
                ++lt;
                ++i;
            } else if (nums[i] > pivot) {
                swap(nums[i], nums[gt]);
                --gt;   // 不能++i，因为换下来的这个数的值还没有跟 pivot 比较过
            } else {
                ++i;
            }
        }
        // 递归处理小于和大于基准的部分
        quickSort3Way(nums, left, lt - 1);
        quickSort3Way(nums, gt + 1, right);
    }

    vector<int> sortArray(vector<int>& nums) {
        srand(time(0));  // 只需初始化一次随机数种子
        quickSort3Way(nums, 0, nums.size() - 1);
        return nums;
    }
};