CCF CSP刷题笔记

本篇博客用来记录我备考CSP的刷题笔记，用来督促自己学习，争取至少每日一题(ง๑ •̀_•́)ง

排序

快速排序

算法步骤

时间复杂度$O(n\log(n))$

• 选择数组中第一个元素作为基准target
• 设定两个指针i和j，其中：
  • i指向数组第一个元素，j指向数组最后一个元素
  • i从左往右遍历，直到i指向的元素大于target
  • j从右往左遍历，直到j指向的元素小于target
  • 若此时i<j，交换i和j指向的元素；否则直接跳出循环
  • 最后再将i和基准位置上的元素进行交换。（这样就实现了基准元素左侧的元素都$\leq$ target，基准元素右侧的元素都$>$target。
• 然后再对基准左侧和右侧的子数组分别递归执行该算法。
  模板：

void quick_sort(int arr[],int low,int high)
{
    if(low >= high) return;
    int i=low,j=high;
    int target = arr[low];

    while(i<j)
    {
        while(arr[j] >= target && i < j ) j--;
        if(i < j) arr[i] = arr[j];
        while(arr[i] <= target && i < j) i++;
        if(i < j) arr[j] = arr[i];
    }
    arr[i] = target;
    quick_sort(arr,low,i-1);
    quick_sort(arr,i+1,high);
}

例题

题目：912. 排序数组 - 力扣（LeetCode）
知识点：
本题中直接打板子会发现出现超时情况，因此我们就需要进行一些优化：

• 优化点1： 将target的选取随机化，这样能够避免一些数组的基准一直取到最差的情况。并且可以使用srand(time(nullptr));来优化随机数的选取。
• 优化点2： 使用Hoare分区法，左右指针不断交换元素，基准值始终留在数组里，循环结束后自然归位。
  代码：

class Solution {
private:
    void quick_sort(int arr[], int low, int high)
    {
        if (low >= high) return;

        int idx = low + rand() % (high - low + 1);
        swap(arr[low], arr[idx]);
        int target = arr[low];

        int i = low - 1, j = high + 1;
        while (i < j) {
            do i++; while (arr[i] < target);
            do j--; while (arr[j] > target);
            if (i < j) swap(arr[i], arr[j]);
        }

        quick_sort(arr, low, j);
        quick_sort(arr, j + 1, high);
    }

public:
    vector<int> sortArray(vector<int>& nums)
    {
        quick_sort(nums.data(), 0, (int)nums.size() - 1);
        return nums;
    }
};

最后成功通过