基础算法---排序

快速排序

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

复杂度：时间复杂度O(nlogn)

代码框架：

void quick_sort(vector<int> &q, int l, int r){
?? ?// 递归终止的情况
?? ?if(l >= r) return;
?? ?// 选区分界线，这里选取数组中间的那个数
?? ?int i = l - 1, j = r + 1, x = q[l + r >> 1];
?? ?while(i < j){
?? ??? ?do i++; while(q[i] < x);
?? ??? ?do j--; while(q[j] > x);
?? ??? ?if(i < j) swap(q[i], q[j]);
?? ?}
?? ?quick_sort(q, l, i - 1);
?? ?quick_sort(q, j + 1, r);
}

题单

[215. 数组中的第K个最大元素 - 力扣（LeetCode）](https://leetcode.cn/problems/kth-largest-element-in-an-array/)

归并排序

基本思想：先将待排序的数组不断拆分，直到拆分到区间里只剩下一个元素的时候。不能再拆分的时候。这个时候我们再想办法合并两个有序的数组，得到长度更长的有序数组。当前合并好的有序数组为下一轮得到更长的有序数组做好了准备。一层一层的合并回去，直到整个数组有序。

复杂度：时间复杂度O(nlogn)

代码框架：

void merge_sort(vector<int> &arr, int l, int r) {?
????// 递归终止情况
????if(l >= r) return;
????// 第一步：分成子问题
????int mid = l + r >> 1;
????
????// 第二步：递归处理子问题
????merge_sort(arr, l, mid);
????merge_sort(arr, mid + 1, r);
????
????// 第三步：合并子问题
????int k = 0, i = l, j = mid + 1;
????vector<int> ?temp(r - l + 1);
????while(i <= mid && j <= r){
?????? ?if(arr[i] <= arr[j]) {
?????? ??? ?temp[k++] = arr[i++];
?????? ?} else{
?????? ??? ?temp[k++] = arr[j++];
?????? ?}
????}
????while(i <= mid) temp[k++] = arr[i++];
????while(j <= r) temp[k++] = arr[j++];
????
????// 第四步：复制回原数组
????for(int i = l, j = 0; i <= r; i++, j++){?
?????? ?arr[i] = temp[j];
????}
}

题单

[LCR 170. 交易逆序对的总数 - 力扣（LeetCode）](https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/)

[315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）](