1.排序
快速排序（AcWing785）
主要思想：基于分治思想
l是待排序区间的左边界，r是右边界
-
确定分界点
x，可以取左边界的值q[l]，或右边界的值q[r]，或者中间位置的值q[(l + r)/2] -
根据基准值，调整区间，使得左半边区间的值全都
≤ x，右半边区间的值全都≥ x采用双指针：左指针
i从左边界l-1开始，往右扫描，右指针j从右边界r+1开始，往左扫描为什么初始是l-1，r+1？
因为后续的不管执行交换与否，首先都先将i，j向内移动一位，所以一开始的两个指针都设置为超出边界一个位置
当满足条件
q[i] < x时，i右移；直到不满足条件时，即q[i] >= x，i停下;然后移动右指针
j，j当满足条件q[j] > x时，j左移；直到不满足条件时，即q[j] <= x，j停下；交换
q[i]和q[j]将i右移一位，j左移一位，重复上面的操作，直到i和j相遇(最终i和j的位置为：i==j或i=j+1)。 此时左半区间的数都满足≤x，且左半区间的最后一个数的下标为j，右半区间的数都满足≥ x,且右半区间的第一个数的下标为i -
递归处理左右两段，
若用
j来作为区间的分界，则[l, j]都是≤x，[j + 1, r]都是≥x若用
i来作为区间的分界，则[l, i - 1]都是≤x，[i, r]都是≥x
注意：
递归取
[l, j]，[j + 1, r]区间时，基准值不能取右边界x=q[r]，不然会出现死循环问题，此时常取左边界x=q[l]或中间值 （eg:1,2 会出现死循环）同理当递归取
[l, i - 1]，[i,r]区间时，基准值不能取左边界x=q[l]，不然会出现死循环问题，此时常取左边界x=q[r] 或中间值 （eg:1,2 会出现死循环）快排不稳定，平均时间复杂度nlogn
#include <iostream>
#include <algorithm> //包含swap函数
using namespace std;
const int N=1e6+10;
int n;
int a[N];
void quick_sort(int a[],int l,int r){
if(l>r) return;
int x=a[(l+r)/2],i=l-1,j=r+1;
while(i<j){
while(a[++i]<x);
while(a[--j]>x);
if(i<j) swap(a[i],a[j]);
}
//递归
quick_sort(a,l,j); //或[l,i-1]
quick_sort(a,j+1,r); //或[i,r]
}
AcWing.786 求第k个数
第k个数
给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。
输入格式 第一行包含两个整数 n 和 k。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整数数列。
输出格式 输出一个整数，表示数列的第 k 小数。
数据范围 1≤n≤100000, 1≤k≤n
输入样例： 5 3 2 4 1 5 3
输出样例： 3
**实现思路：**使用基于快速排序的快速选择思想(O(n))，相比直接用快速排序输出第k个数(O(nlogn))时间复杂度更小
- 根据快速排序的思想，将数组划分为两个区间，分别递归两个区间，直到左区间⇐基准值，右区间>=基准值。
- 设左区间的数据个数为
sl，右区间的数据个数为sr。 - 则若k⇐sl，就意味着最终答案在左区间，则后续无需再递归右区间排序，只需递归左区间，输出左区间的第k个数即为结果
- 同理，若k>sl，就意味着最终答案在右区间，则后续无需再遍历左区间，只需递归右区间，输出右区间第k-sl个数即为结果。
#include <iostream>
using namespace std;
int N=1e6+10;
int n,k;
int a[N];
//返回最终结果
int quick_sort(int l,int r,int k){
//先正常进行快排
if(l==r) return a[l];//若区间中只有一个数 直接返回为结果
int i=l-1,j=r+1,x=a[(l+r)/2];
while(i<j){
while(a[++i]<x);
while(a[--j]>x);
if(i<j) swap(a[i],a[j]);
}
int sl=j-l+1;//左区间数据个数
if(k<=sl) return quick_sort(l,j,k);//结果在左区间，只递归左区间
return quick_sort(j+1,r,k-sl);//结果在右区间，只递归右区间
}
int mian(){
cin>>n>>k;
for(int i=0;i<n;i++) cin>>a[i];
cout<<quick_sort(0,n-1,k)<<endl;
return 0;
}归并排序（AcWing787）
主要思想：也是基于分治思想
1.先确认分界点，一般取中间点(l+r)/2
2.对左右两个区间分别递归排序
3.将两侧排好序的两个有序数组合二为一
实现思路：设置左右指针和一个临时数组temp，左指针指向左区间的的第一个元素，右指针指向右区间的第一个元素，循环比较左右指针所指元素，两者较小的元素放入temp数组中，指针后移继续比较。直至某一指针到达末尾，将其中一个未放置完的区间的数再都放入temp数组。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int n;
int a[N]，temp[N];
void merge_sort(int a[],int l,int r){
if(l>r) return;
int mid=(l+r)/2;
merge_sort(a,l,mid),merge_sort(a,mid+1,r);//递归左右区间
int k=0,i=l,j=mid+1;//k为临时数组的指针，i为左区间指针，j为右区间指针
while(i<=mid && j<=r){
while(a[i]<=a[j]) temp[k++]=a[i++];
else temp[k++]=a[j++];
}
while(i<=mid) temp[k++]=a[i++];//左区间有剩余
while(j<=r) temp[k++]=a[j++];//右区间有剩余
//最后将temp数组的数据放回a数组
for(int i=l,k=0;i<=r;i++,k++)
a[i]=temp[k];
}
注意：
归并排序稳定，时间复杂度为nlogn
AcWing.788 求逆序对数量
实现思路：
- 根据归并排序的思想，将数组分为各自有序的左右两个区间
[l,mid],[mid+1,r]，采用双指针开始分别指向两个区间的第一个元素，相互比较选出较小的那个元素，然后后移，不断循环，直到一个区间遍历完。 - 在比较过程中，设
i指向左区间，j指向右区间，由于两个区间各自有序，逆序对只会出现一种情况，即左区间存在大于右区间元素的元素。 - 若
a[i]>a[j]，则左区间中从i开始到mid的元素都大于a[j]，与a[j]组成逆序对，数量为mid-i+1
**注意：**对于给定n个数，最坏的情况为逆序，则逆序对数为n(n-1)/2个，题中数据个数范围为100000，则最大结果会超出int的存储范围(-2^31~2^31-1)，所以虽好使用long long来存储最终结果
#include <iostream>
using namespace std;
typedef long long LL;
int N=100010;
int a[N],tmp[N];
int n;
LL merge_sort(int l,int r){
if(l>=r) return 0;
int mid=l+r>>2;
LL res=merge_sort(l,mid)+merge_sort(mid+1,r);//左右区间分别进行归并
//归并过程
int k=0,i=l,j=mid+1;
while(i<=mid && j<=r){
if(a[i]<=a[j]) tmp[k++]=a[i++];
else{
tmp[k++]=a[j++];
res+=mid-i+1;
}
}
//某个区间剩余元素
while(i<=mid) tmp[k++]=a[i++];
while(j<=r) tmp[k++]=a[j++];
//物归原主
for(int i=l,j=0;i<n;i++,j++) a[i]=tmp[j];
return res;
}
int mian(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
cout<<merge_sort(0,n-1)<<endl;
return 0;
}