【左程云算法全讲3】归并排序与随机快排

系列综述：
💞目的：本系列是个人整理为了秋招面试的，整理期间苛求每个知识点，平衡理解简易度与深入程度。
🥰来源：材料主要源于左程云算法课程进行的，每个知识点的修正和深入主要参考各平台大佬的文章，其中也可能含有少量的个人实验自证。
🤭结语：如果有帮到你的地方，就点个赞和关注一下呗，谢谢🎈🎄🌷！！！
🌈【C++】秋招&实习面经汇总篇

文章目录

- - 归并排序
  - 快速排序
- 参考博客

😊点此到文末惊喜↩︎

归并排序

是否可递归：大问题能否通过范围缩小但是同等定义的子问题搞定
归并排序

// 将两个数组从小到大合并成为一个
void Merge(vector<int> &vec, int L, int mid, int R) {const int n = R-L+1;vector<int> tmp(n, 0);  // 注意长度int i = 0;      // 工作指针int p1 = L;     // 左半部分的工作指针int p2 = mid+1; // 右半部分的工作指针// 两者较小的赋值给tmp数组while (p1 <= mid && p2 <= R) {tmp[i++] = (vec[p1] <= vec[p2] ? vec[p1++] : vec[p2++]); }// 收尾while (p1 <= mid) {tmp[i++] = vec[p1++];}while (p2 <= R) {tmp[i++] = vec[p2++];}// 赋值for (int i = 0; i < n; ++i) {vec[L+i] = tmp[i];  // key：注意递归中赋值的起始位置}}
// 递归形式
void Process(vector<int> &vec, int L, int R) {// 递归出口if (L == R) return ;// 划分int mid = L + ((R-L)>>1);Process(vec, L, mid);Process(vec, mid+1, R);// 合并Merge(vec, L, mid, R);
}
// 非递归形式
void Process(vector<int> &vec) {if (vec.size() < 2) return ;const int n = vec.size();int merge_size = 1;		// 每次合并单位while (merge_size < N) {int L = 0; 		// 每次从0开始while (L < N) {	// 合并相邻merge_size的区间int mid = L+merge_size-1;if (mid >= N) break;	// 避免右边界溢出int R = min(mid+merge_size(), N-1);merge(vec, L, mid, R);L = R+1;}if (merge_size > N / 2) break;	// 避免溢出，提前停止merge_size <<= 1;}
}

求数组小和，表示第i个数左侧小于等于该数的个数，然后整个数组的每个数的小和相加
- 逆反：相当于求第i个数右侧比i值大的个数
- 归并排序可以解决两个范围比较的问题

// 将两个数组从小到大合并成为一个
int Merge(vector<int> &vec, int L, int mid, int R) {const int n = R-L+1;vector<int> tmp(n, 0);  // 注意长度int i = 0;      // 工作指针int p1 = L;     // 左半部分的工作指针int p2 = mid+1; // 右半部分的工作指针// 两者较小的赋值给tmp数组int res = 0;while (p1 <= mid && p2 <= R) {// 在右组中找到比左组大的数，右组是有序的，所以可以直接通过下标计算出右组更大的有几个res += vec[p1] < vec[p2] ? (R-p2+1)*vec[p1] : 0;tmp[i++] = (vec[p1] < vec[p2] ? vec[p1++] : vec[p2++]); }// 收尾while (p1 <= mid) {tmp[i++] = vec[p1++];}while (p2 <= R) {tmp[i++] = vec[p2++];}// 赋值for (int i = 0; i < n; ++i) {vec[L+i] = tmp[i];  // key：注意递归中赋值的起始位置}return res;}int Process(vector<int> &vec, int L, int R) {// 递归出口if (L == R) return 0;// 划分int mid = L + ((R-L)>>1);return Process(vec, L, mid) + Process(vec, mid+1, R);+ Merge(vec, L, mid, R);
}

快速排序

partition过程：进行划分但不严格要求两部分内部有序，将小于等于num的数放在左边，将大于等于num的数放在右边
代码

// 划分
int parititon(vector<int> &vec, int left, int right) {// 随机化处理：避免完全有序的情况int idx = left + rand() % (right - left + 1);swap(vec[left], vec[idx]);// 算法部分int pos = left;int pivot = vec[left];while (left < right) {while (vec[right] >= pivot && left < right) right--;while (vec[left] <= pivot && left < right) left++;swap(vec[left], vec[right]);}swap(vec[left], vec[pos]);return left;
}void QuickSort(vector<int> &vec, int left, int right) {if (left > right) return ;int mid = parititon(vec, left, right);QuickSort(vec, left, mid-1);QuickSort(vec, mid+1, right);}
// main中需要 srand((int)time(NULL));