快速排序：
快排板子：分治思想
1.确定分界点（x = a[l+r>>1]），这么做是为了避免有序的情况下，子问题规模依旧较大的问题（如果有序且分界点取在首个，那么数组被分为长度1和n-1）
2.调整区间，使得第一个区间<=x,第二个区间>=x；
3.递归两个区间
#include <iostream> #include <cstdio> using namespace std; const int N = 1e5+10; int a[N]; void quicksort(int l,int r,int a[]) { if (l>=r) return; int i = l-1,j = r+1,x = a[i+j>>1]; while (i<j) { do i++;while (a[i]<x); do j--;while (a[j]>x); if (i<j) swap(a[i],a[j]); } quicksort(l,j,a); quicksort(j+1,r,a); } int main() { int n; scanf("%d",&n); for (int i = 0;i<n;i++) scanf("%d",&a[i]); quicksort(0,n-1,a); for (int i = 0;i<n;i++) printf("%d ",a[i]); return 0; }
归并排序
1：确定分界点
2：递归
3：归并merge（注意可能一条链子输完了另一条还没有输完的情况）
归并板子：
#include <iostream> #include <cstdio> using namespace std; const int N = 1e5+10; int tmp[N];//临时容器 int a[N]; void mergesort(int l,int r,int a[]) { if (l>=r) return ; int mid = l+r>>1;//划分区间 mergesort(l,mid,a); mergesort(mid+1,r,a);//递归排序 int i = l,j = mid+1,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;j<k;j++,i++) a[i] = tmp[j];//复制到到原数组 } int main() { int n; scanf("%d",&n); for (int i = 0;i<n;i++) scanf("%d",&a[i]); mergesort(0,n-1,a); for (int i = 0;i<n;i++) printf("%d ",a[i]); return 0; }
经典例题：逆序对的数量：acwing788
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
输入样例：
1. 6 2. 2 3 4 5 6 1
输出样例：
5
逆序对分成三块，前两块ans加上函数自身的递归，第三块先排序再累加；
#include <iostream> #include <cstdio> using namespace std; typedef long long LL; const LL N = 1e5+10; LL a[N],tmp[N]; LL mergesort(LL l,LL r,LL a[]) { if (l>=r) return 0; LL mid = l+r>>1; LL ans = 0; ans+=mergesort(l,mid,a)+mergesort(mid+1,r,a); LL i = l,j = mid+1,k = 0; while (i<=mid&&j<=r) { if (a[i]<=a[j]) tmp[k++] = a[i++]; else { tmp[k++] = a[j++]; ans += mid-i+1; } } while (i<=mid) tmp[k++] = a[i++]; while (j<=r) tmp[k++] = a[j++]; for (LL i = 0,j = l;i<k;i++,j++) a[j] = tmp[i]; return ans; } int main() { LL n; scanf("%ld",&n); for (int i = 0;i<n;i++) scanf("%ld",&a[i]); LL ans = mergesort(0,n-1,a); printf("%ld",ans); return 0; }
