AcWing基础部分Class1排序笔记

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

//
// Created by BlancheSun on 2022/8/4.
//
#include
#include

using namespace std;

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

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

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


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

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

    return 0;
}

// 归并排序
void MergeSort(vector& 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& vec, int start, int mid, int end) {
    // 拷贝初始化
    vector vec1(vec.begin()+start, vec.begin()+mid+1);
    vector 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& vec) {
    for (int i = 0; i < vec.size(); ++i) {
        cout << vec[i] << " ";
    }
    cout << endl;
}

// 快速排序
void quickSort(vector& 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& 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;
}

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

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

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

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

英语描述快排思想：

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

与归并排序不同，快排的核心在于分解的过程。在算法中具体体现在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]

• 优雅解法

  int partition(vector& 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;
  }
  

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

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

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

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

二分的本质：

• 寻找区间边界

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

m i d = l + r + 1 2 mid = frac{l+r+1}{2} mid=2l+r+1​

check函数检验是否满足红色部分的性质
i f ( c h e c k ( m i d ) ) { t r u e ：答案区间 [ m i d ,   r ] , l = m i d f a l s e ：答案区间 [ l , m i d − 1 ] , r = m i d − 1 if(check(mid))begin{cases}true：答案区间[mid, r],l=mid\ false：答案区间[l, mid-1],r=mid-1end{cases} if(check(mid)){true：答案区间[mid, r],l=midfalse：答案区间[l,mid−1],r=mid−1​

m i d = l + r 2 mid = frac{l+r}{2} mid=2l+r​

check函数检验是否满足绿色部分的性质
i f ( c h e c k ( m i d ) ) { t r u e ：答案区间 [ l ,   m i d ] ，  r = m i d f a l s e ：答案区间 [ m i d + 1 , r ] ，  l = m i d + 1 if(check(mid))begin{cases}true：答案区间[l, mid]， r=mid\ false：答案区间[mid+1, r]， l=mid+1end{cases} if(check(mid)){true：答案区间[l, mid]， r=midfalse：答案区间[mid+1,r]， l=mid+1​

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

#include
#include

using namespace std;

int main() {
    vector 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;
}

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

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

浮点数二分，找到一个数的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("%lfn", l);
}

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

• 快速排序

  剑指 Offer II 076. 数组中的第 k 大的数字 - 力扣（LeetCode）

  剑指 Offer 40. 最小的k个数 - 力扣（LeetCode）

• 归并排序

  剑指 Offer II 078. 合并排序链表 - 力扣（LeetCode）

  剑指 Offer II 074. 合并区间 - 力扣（LeetCode）

  剑指 Offer 51. 数组中的逆序对 - 力扣（LeetCode）

• 二分

  34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

  69. x 的平方根 - 力扣（LeetCode）

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

#include
#include
#include 

using namespace std;

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

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


class Solution {
public:
    vector getLeastNumbers(vector& arr, int k) {
        vector 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& 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 searchRange(vector& nums, int target) {
        vector 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    // 短路判断，如果是空数组，那么直接返回-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 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 nums = {5,7,7,8,8,10};
    int target = 8;
    vector res = s.searchRange(nums, target);
    cout << res[0] << " " << res[1] << endl;

    return 0;
}

// 逆序数
void MergeSort(vector& 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& vec, int start, int mid, int end, int& count) {
    vector vec1(vec.begin() + start, vec.begin() + mid + 1);
    vector 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& 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&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& 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);
    }
}