AcWing基础部分Class1排序笔记-EW帮帮网

微信交流群：https://732903.hlcode.cn/?id=NK1fWUR

排序笔记

包含两个典型的排序算法
$\begin{cases}归并排序\\快速排序\end{cases}$
程序实现如下：

//
// Created by BlancheSun on 2022/8/4.
//
#include<iostream>
#include<vector>

using namespace std;

// 工具函数
void printVec(vector<int>& vec);

// 归并排序
void MergeSort(vector<int>& vec, int start, int end);
void Merge(vector<int>& vec, int start, int mid, int end);

// 快速排序
void quickSort(vector<int>& vec, int start, int end);
int partition(vector<int>& vec, int start, int end);


int main() {
    // 归并排序
    vector<int> vec = {1,6,4,9,10,2,-1,6,5,8,7};
    MergeSort(vec, 0, vec.size()-1);
    printVec(vec);

    // 快速排序
    vector<int> vec2 = vec;
    quickSort(vec2, 0, vec2.size()-1);
    printVec(vec2);

    return 0;
}

// 归并排序
void MergeSort(vector<int>& vec, int start, int end) {
    if(start < end) {
        // 分
        int mid = (start + end) / 2;
        // 治
        MergeSort(vec, start, mid);
        MergeSort(vec, mid+1, end);
        // 合并
        Merge(vec, start, mid, end);
    }
}

void Merge(vector<int>& vec, int start, int mid, int end) {
    // 拷贝初始化
    vector<int> vec1(vec.begin()+start, vec.begin()+mid+1);
    vector<int> vec2(vec.begin()+mid+1, vec.begin()+end+1);
    // 末尾置一无穷大值，方便扫尾
    int infty = 999999;
    vec1.push_back(infty);
    vec2.push_back(infty);
    // merge的核心过程
    int i = 0, j = 0, k = start;
    while(k <= end) {
        if (vec1[i] <= vec2[j]) {
            vec[k++] = vec1[i++];
        }else {
            vec[k++] = vec2[j++];
        }
    }
}

void printVec(vector<int>& vec) {
    for (int i = 0; i < vec.size(); ++i) {
        cout << vec[i] << " ";
    }
    cout << endl;
}

// 快速排序
void quickSort(vector<int>& vec, int start, int end) {
    if (start < end) {
        // 分
        int pivot_index = partition(vec, start, end);
        // 治
        quickSort(vec, start, pivot_index - 1);
        quickSort(vec, pivot_index + 1, end);
        // 合并部分不需要再做工作
    }
}

int partition(vector<int>& vec, int start, int end) {
    int pivot = vec[end];
    int i = start - 1, j = start;
    while (j <= end) {
        if (vec[j] <= pivot) {
            i++;
            int temp = vec[i];
            vec[i] = vec[j];
            vec[j] = temp;
        }
        j++;
    }
    return i;
}

1.1.1 归并排序

分、治、合并三个步骤，重点在于合并的步骤；

合并步骤采取的方法是使用两个临时数组，存储目前已经有序的两段，将这两段通过双指针的形式扫描后合并。

特别的合并时可以在两个临时数组末尾各插入一个无穷大的数字，这样扫尾只需要一个循环即可。

否则还需要额外的循环做扫尾工作：两个for，检验i和j是否有未到某尾的，将其直接续接即可。

1.1.2 快速排序

英语描述快排思想：

快排算法是基于分治思想的一种算法，包括基本的分、治、合并三个步骤。

与归并排序不同，快排的核心在于分解的过程。在算法中具体体现在partition的部分。paritition的过程本质是选择一个数，让数组以这个数所在的位置为界，左侧的数据小于该数字，右侧的数大于该数字。实现时常采用两个指针扫描的方式不断交换下标所在的数字来实现。“治”的步骤则是对数组中以该数分成的两段分别递归处理。算法不需要进行合并步骤。

Fast sort is a kind of algorithm based on divide and conquer idea, including three basic steps: divide, conquer and merge.

Unlike merge sort, the key of quick sort is the devide step. The algorithm is embodied in the ‘partition’ part. The essence of the process of ‘paritition’ is to select a number, so that the array is bounded by the position of the number, the data on the left is less than the number, and the number on the right is greater than the number. The implementation often uses two pointer scanning method to constantly exchange the number of the subscript to achieve. The “conquer” step is to recursively process the two segments of the array divided by that number. The algorithm does not require a merge step.

快排的partition是核心，partition的实现方法有很多种：

暴力解法：辅助数组a[],b[]分别存储小于等于pivot和大于pivot的数

分别存储完毕后，将a[],b[]中的数字分别赋值给vector

这样求解需要额外的存储空间，但是时间复杂度上还是O(n)
常见解法：使用两个指针i,j，分别置于数组开始位置和末尾位置，向中间扫描

若出现vec[i]>pivot && vec[j]<pivot，那么交换vec[i]和vec[j]对应的数据

优雅解法

int partition(vector<int>& vec, int start, int end) {
    int pivot = vec[end];
    int i = start - 1, j = start;
    while (j <= end) {
        if (vec[j] <= pivot) {
            i++;
            int temp = vec[i];
            vec[i] = vec[j];
            vec[j] = temp;
        }
        j++;
    }
    return i;
}

1.2 二分

$\begin{cases}整数二分\\浮点数二分\end{cases}$

二分的循环结束条件：r < l，长度为1时循环结束；

性质一定是有边界的。通过性质判断有无解

1.2.1 整数二分

二分和单调性的关系：有单调性一定可以二分，没有单调性可能也可以使用二分。

二分的本质：

寻找区间边界

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ssEMZ1pm-1659958636331)(https://cdn.jsdelivr.net/gh/Holmes233666/blogImage@main/img/image-20220807162202655.png)]

寻找两个区间的端点（绿色点和红色点）对应两个不同的算法模板：

1.2.1.1 二分下界：红色点

$\frac{l+r+1}{2}$

check函数检验是否满足红色部分的性质
$if(check(mid))\begin{cases}true：答案区间[mid, \ r],l=mid\\ false：答案区间[l, mid-1],r=mid-1\end{cases}$

1.2.1.2 二分上界：绿色点

$\frac{l+r}{2}$

check函数检验是否满足绿色部分的性质
$if(check(mid))\begin{cases}true：答案区间[l, \ mid]，\ r=mid\\ false：答案区间[mid+1, r]，\ l=mid+1\end{cases}$

1.2.1.3 具体应用

如在数组1 1 2 2 3 3 4中求解3的起始下标和终止下标

#include<iostream>
#include<vector>

using namespace std;

int main() {
    vector<int> vec = {1, 1, 2, 2, 3, 3, 4};
    int l = 0, r = vec.size()-1;
    int target = 3;
    // 寻找下界
    while (l < r) {
        int mid = (l + r) >> 1;
        if (vec[mid] >= target) {
            r = mid;
        }else{
            l = mid + 1;
        }
    }
    if (vec[l] != target) cout << "-1 -1" << endl;
    else{
        cout << l << endl;  // 输出下界的结果  ----   通过性质判断 //
        // 寻找上界
        l = 0;
        r = vec.size() - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (vec[mid] <= target) {
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        cout << l << endl;
    }
    return 0;
}

1.2.2 浮点数二分

浮点数二分不需要处理边界，比如(r-l) < 10^6；

和整数二分一样，需要保证的是一定在区间内。

1.2.2.1 平方根的例子

浮点数二分，找到一个数的1/2的值，保证其精度为precision

void floatBinarySearch(double x, double precision) {
    double l = 0, r = x;
    while (r - l > precision) {
        double mid = (l + r) / 2;
        if (mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf\n", l);
}

习题练习 Day1

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7hBDfuI5-1659958636332)(https://cdn.jsdelivr.net/gh/Holmes233666/blogImage@main/img/image-20220808102018280.png)]

这里没有对应AcWing上习题练习，而是去力扣找了对应的题进行练习：

//
// Created by BlancheSun on 2022/8/8
// 寻找乱序数组中第k大/小的数
//

#include<iostream>
#include<vector>
#include <cmath>

using namespace std;

// 前k小的数
int randomizedPartition(vector<int>&vec, int start, int end);
int partition(vector<int>& vec, int start, int end);
int randomizedSelect(vector<int>& vec, int start, int end, int k);

// 逆序数
void Merge(vector<int>& vec, int start, int mid, int end, int& count);
void MergeSort(vector<int>& vec, int start, int end, int& count);

/****** partition算法的应用 ******/
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> res(0);
        if (k == 0) return res;
        int kIndex = randomizedSelect(arr, 0, arr.size()-1, k);
        for (int i = 0; i <= kIndex; ++i) {
            res.push_back(arr[i]);
        }
        return res;
    }
};

/*** 归并的应用：逆序数对数量（逆序数对：线代中的逆序数概念） ***/
class Solution2 {
public:
    int reversePairs(vector<int>& nums) {
        int count = 0;
        MergeSort(nums, 0, nums.size()-1, count);
        return count;
    }
};

/*** 二分：算术平方根 ***/
class Solution3 {
public:
    int mySqrt(int x) {
        double l = 0, r = x;
        while (r - l >= 1e-6) {
            double mid = (r + l) / 2;
            if (mid * mid >= x) {
                r = mid;
            }else{
                l = mid;
            }
        }
        return r;
    }
};

class Solution4 {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(0);
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (r + l) >> 1;
            if (nums[mid] >= target) {
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        if ( r<l || nums[l] != target) {    // 短路判断，如果是空数组，那么直接返回-1
            res.push_back(-1);
            res.push_back(-1);
        }else{
            res.push_back(l);
            l = 0, r = nums.size() -1;
            while (l < r) {
                int mid = (r + l + 1) >> 1;
                if (nums[mid] <= target) {
                    l = mid;
                }else{
                    r = mid - 1;
                }
            }
            res.push_back(l);
        }
        return res;
    }
};


int main() {

//    vector<int> nums = {1, 3, 2, 3, 1, 1};
//    Solution2 s;
//    cout << s.reversePairs(nums);

//    Solution3 s;
//    int x = 8;
//    cout << s.mySqrt(x);

    Solution4 s;
    vector<int> nums = {5,7,7,8,8,10};
    int target = 8;
    vector<int> res = s.searchRange(nums, target);
    cout << res[0] << " " << res[1] << endl;

    return 0;
}

// 逆序数
void MergeSort(vector<int>& vec, int start, int end, int& count) {
    if (start < end) {
        int mid = (start + end) / 2;
        MergeSort(vec, start, mid, count);
        MergeSort(vec, mid + 1, end, count);
        Merge(vec, start, mid, end, count);
    }
}

void Merge(vector<int>& vec, int start, int mid, int end, int& count) {
    vector<int> vec1(vec.begin() + start, vec.begin() + mid + 1);
    vector<int> vec2(vec.begin()+ mid + 1, vec.begin() + end + 1);
    vec1.push_back(65536);
    vec2.push_back(65536);
    int k = start, i = 0, j = 0;
    while (k <= end) {
        if (vec1[i] <= vec2[j]) {    // 小于的时候需要处理
            count += j;
            vec[k++] = vec1[i++];
        }else{                      // 大于等于时不需要处理
            vec[k++] = vec2[j++];
        }
    }
}

// 寻找乱序数组中第k小的数
int partition(vector<int>& vec, int start, int end) {
    int pivot = vec[end];
    int i = start - 1, j = start;
    while (j <= end) {
        if (vec[j] <= pivot) {
            i++;
            swap(vec[j], vec[i]);
        }
        j++;
    }
    return i;
}

int randomizedPartition(vector<int>&vec, int start, int end) {
    int pivot_index = rand() % (end - start + 1) + start;
    swap(vec[pivot_index], vec[end]);
    return partition(vec, start, end);
}

int randomizedSelect(vector<int>& vec, int start, int end, int targetRank) {
    if (start == end) return start;
    int pivot_index = randomizedPartition(vec, start, end);
    int k = pivot_index - start + 1;
    if (k == targetRank) {
        return pivot_index;
    }else if (targetRank < k) {
        return randomizedSelect(vec, start, pivot_index - 1, targetRank);
    }else {
        return randomizedSelect(vec, pivot_index + 1, end, targetRank - k);
    }
}

本文含有隐藏内容，请开通VIP 后查看

AcWing基础部分Class1排序笔记