上机4-快排和归并
（1）快速排序：
思想：分治思想
步骤：1.确定分界点，通常选q[l]，q[(l+r)/2]，q[r]，或者也可以随机一个位置。
2.调整区间，对于升序排序，就是将小于分界点值的元素放到分界点左边，大于的
放到右边，从而划分为左右两个区间。
3.递归处理左右两边区间。
Acwing 785.快速排序
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5 3 1 2 4 5输出样例：
1 2 3 4 5王道计算机版本的代码：使用首元素作为分界点，但是过不去这道题的所有样例
/*快速排序，王道版本代码 两个函数，quicksort和partition quicksort用于左右递归，partition用于划分其中一趟排序 */ int q[N];//用于存放输入数据 int n; int partition(int l,int r)//对当前区间调整，调整结束后返回基准值最终下标 { //进行划分 int px=q[l];//选第一个元素作为基准值 while(l<r) { while(l<r&&q[r]>=px) r--; q[l]=q[r]; while(l<r&&q[l]<=px) l++; q[r]=q[l]; } //将基准值放入最终位置 q[l]=px; return l; } void quickSort(int l, int r) { if(l>=r) return;//只有一个元素或者区间不合法时 int pivot=partition(l,r); //对基准值下标左右两侧的闭区间继续递归调整 quickSort(l,pivot-1); quickSort(pivot+1,r); }代码思路：使用中间值作为分界点
/*快速排序 acwing版本，使用中间元素作为分界点 */ #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N=100005; int q[N];//用于存放输入数据 int n; void quick_sort(int l,int r) { if(l>=r) return; int x=q[(l+r)/2]; int i=l-1,j=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(l,j); quick_sort(j+1,r); } int main() { cin>>n; for(int i=0;i<n;i++) cin>>q[i]; quick_sort(0,n-1); for(int i=0;i<n;i++) cout<<q[i]<<" "; return 0; }(2)归并排序：
思想：每次将两个有序的序列合并成一个有序的序列
步骤：先分别左右递归到最底层，再归并，每一层归并结束后再返回上一层。
需要开辟一个O(n)的辅助空间，时间复杂度为O(nlogn)
Acwing 787.归并排序
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5 3 1 2 4 5输出样例：
1 2 3 4 5代码思路：
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N=100005; int a[N],n; int tmp[N];//辅助空间 void merge_sort(int l,int r) { if(l>=r) return; int mid=(l+r)/2; merge_sort(l,mid);//递归左边 merge_sort(mid+1,r); int i=l,j=mid+1; int k=0; while(i<=mid&&j<=r) { if(a[i]<=a[j]) tmp[k++]=a[i++]; else tmp[k++]=a[j++]; } while(i<=mid) tmp[k++]=a[i++]; while(j<=r) tmp[k++]=a[j++]; //将合并后的序列放回原位置 for(int i=l,j=0;i<=r;i++,j++) a[i]=tmp[j]; } int main() { cin>>n; for(int i=0;i<n;i++) cin>>a[i]; merge_sort(0,n-1); for(int i=0;i<n;i++) cout<<a[i]<<" "; return 0; }归并排序经典用法是求逆序对的数量：
Acwing 788.逆序对的数量
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000，
数列中的元素的取值范围 [1,1e9]。
输入样例：
6 2 3 4 5 6 1输出样例：
5代码思路：
/*逆序对的数量 在归并排序合并升序序列的过程中，对于左右两个升序序列 如果l[i]>=r[j]那么l[i+1]...l[mid]肯定都大于r[j]，也就相当于这些l的元素都和r[j]形成一次逆序对 这种情况就需要计数一次。 所以对整个排序过程中的逆序对出现情况进行计数，最后输出结果 */ #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N=100005; int a[N],n; long long cnt=0;//注意逆序对可能会有很多，这里要用longlong定义计数器 int tmp[N]; void merge_sort(int l,int r) { if(l>=r) return; int mid=(l+r)/2; merge_sort(l,mid); merge_sort(mid+1,r); int i=l,j=mid+1; int k=0; while(i<=mid&&j<=r) { if(a[i]<=a[j])//这种情况前后不构成逆序对 tmp[k++]=a[i++]; else//这种情况,a[i]~a[mid]都与a[j]构成逆序对 { cnt+=(mid-i+1);//计数逆序对数量 tmp[k++]=a[j++]; } } while(i<=mid) tmp[k++]=a[i++]; while(j<=r) tmp[k++]=a[j++]; for(int i=l,j=0;i<=r;i++,j++) a[i]=tmp[j]; } int main() { cin>>n; for(int i=0;i<n;i++) cin>>a[i]; merge_sort(0,n-1); cout<<cnt<<endl; return 0; }