/*
//动画https://www.bilibili.com/video/BV1DP4y1n71W/?spm_id_from=333.1387.favlist.content.click&vd_source=0788d142b89e213fc290e2ffa2561fd2
//快排时间复杂度分析https://www.cnblogs.com/fengty90/p/3768827.html
下面是最简单的特征数据
5
1 4 5 3 9
5 
1 2 3 4 5
5 
5 4 3 2 1
5 
1 1 1 1 1
*/
#include<iostream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
const int maxn=1E5+10;//没开玩笑，zyc又少写了个0 RE了
int a[maxn], n;
using namespace std;
void print_arr(){
	for(int i=0;i<n;i++)	
		printf("%d ", a[i]);//cout<<a[i]<<" ";	
	cout<<endl;
}
void my_quick_sort(int l, int r){
//1置位：将标杆pivot放到它应有的位置 
//2divide：步骤一中必然发生和每个数字的比较，那既然已经比了，就要做点别的事，比如把比pivot小的放左边，大的放右边
//3conquer：缩小重复12步骤的左右边界
	if(l>=r)	return;

	int t=l;
	while(t<r&&a[t]<=a[t+1]){
		t++;
	}
	if(t>=r)	return;//特判如果本身就是单调非递减，那就不用分治了

//	int pivot=l, ptr=l;//最基础的写法，固定pivot是l。ptr指向分界线，pivot最终位置 
	int pivot=(rand()%(r-l+1))+l, ptr=l;//随机pivot
	swap(a[pivot], a[l]);//随机pivot后把它和l交换就可以复用下面针对基础写法pivot=l写的代码

	for(int i=l+1;i<=r;i++){
		if(a[i]<a[l]){//比pivot小的放ptr分界线（该界限左边小右边大）
			swap(a[i], a[++ptr]);//分界线右移
		}//比pivot大的先不动，如果后面出现比pivot小的就会替换过来
	}
	swap(a[l], a[ptr]);
//	print_arr();
	my_quick_sort(l, ptr-1); 
	my_quick_sort(ptr+1, r); 
}
int main(){
	cin>>n;
	// srand(time(0));
	for(int i=0;i<n;i++)	
		scanf("%d", &a[i]);//cin>>a[i];
	my_quick_sort(0,n-1);
	print_arr();//调试+输出
	return 0;
}

//归并排序
#include<iostream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
const int maxn=1E5+10;
int a[maxn], temp[maxn], n;//此处@猴哥学单词，数组缩写为a不是因为字母表而是array，temp是temporary代表临时中转
using namespace std;
void print_arr(){//抽取反复用到的代码成函数，调试+输出
	for(int i=0;i<n;i++)	
		printf("%d ", a[i]);//cout<<a[i]<<" ";	
	cout<<endl;
}
void my_merge_sort(int l, int r){
	if(l>=r)	return;
	int mid=((r-l)>>1)+l;//(l+r)/2的防溢出写法
	my_merge_sort(l,mid);//要搭配合适的mid否则容易死循环 
	my_merge_sort(mid+1,r);
	int p1=l, p2=mid+1, pt=l;//左区间指针、右区间指针、temp数组指针（temp存部分sorted array,防止原数组被覆盖）
	while(p1<=mid&&p2<=r){//双指针取小的数放过来 
		if(a[p1]<=a[p2]){
			temp[pt++]=a[p1++]; 
		}else{
			temp[pt++]=a[p2++];
		}
	}
	while(p1<=mid){//左右两边序列不一定等长，还有尾巴没处理 
		temp[pt++]=a[p1++];
	}
	while(p2<=r){
		temp[pt++]=a[p2++];
	}
	for(int i=l; i<=r; i++){
		a[i]=temp[i];
	}
//	print_arr();
}
int main(){
	cin>>n;
	srand(time(0));
	for(int i=0;i<n;i++)	
		scanf("%d", &a[i]);//cin>>a[i];
	my_merge_sort(0,n-1);
	print_arr();//调试+输出
	return 0;
}

归并排序（推荐）

#include <bits/stdc++.h>
using namespace std;
unsigned int p[100010],tmp[100010],n;
void merge(unsigned int l,unsigned int r){
    if(l>=r)return;
    unsigned int mid=(l+r)/2;
    merge(l,mid);
    merge(mid+1,r);
    unsigned int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r){
        if(p[i]<=p[j])tmp[k++]=p[i++];
        else tmp[k++]=p[j++];
    }while(i<=mid)tmp[k++]=p[i++];
    while(j<=r)tmp[k++]=p[j++];
    for(i=l,j=0;i<=r;i++,j++)p[i]=tmp[j];
}
int main(){
    cin>>n;
    for(unsigned int i=0;i<n;i++)cin>>p[i];
    merge(0,n-1);
    for(unsigned int i=0;i+1<n;i++)cout<<p[i]<<" ";
    cout<<p[n-1]<<endl;
    return 0;
}

快排

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
unsigned int ans[100010],n;
void quick_sort(int l,int r) {
	if(l>=r)return;
	int t=l;
	while(t<r&&ans[t]<=ans[t+1])t++;
	if(t>=r)return;
	int mid=l+(r-l)/2;
	if(ans[mid]<ans[l])swap(ans[mid],ans[l]);
	if(ans[r]<ans[l])swap(ans[r],ans[l]);
	if(ans[mid]<ans[r])swap(ans[mid],ans[r]);
	int pivot=r;
	swap(ans[pivot],ans[l]);
	unsigned int i=l,j=r,base=ans[l];
	while(i<j){
		while(i<j&&ans[j]>=base)j--;
		while (i<j&&ans[i]<=base)i++;
		if(i<j)swap(ans[i],ans[j]);
	}
	swap(ans[l],ans[i]);
	quick_sort(l,i-1);
	quick_sort(i+1,r);
}
int main() {
	srand(time(NULL));  // 初始化随机种子
	scanf("%u",&n);
	for(unsigned int i=0;i<n;++i)scanf("%u",&ans[i]);
	quick_sort(0,n-1);
	for(unsigned int i=0;i<n;++i)printf("%u ",ans[i]);
	return 0;
}

堆排：

#include<bits/stdc++.h>
using namespace std;
template<typename T,typename Comp=less<T>>
struct heap{
    vector<T>tree{1};
    int n=0;
    Comp comp;
    heap(Comp cmp=Comp{}):comp(cmp){}
    T top(){return tree[1];}
	int heap_size(){
		return n;
	}void push(T x){
        n++;
        tree.push_back(x);
        int pthis=n,parent=n/2;
        while(parent>=1&&comp(tree[pthis],tree[parent])){
            swap(tree[pthis], tree[parent]);
            pthis=parent;
            parent/=2;
        }
    }void pop(){
        swap(tree[1],tree[n]);
        tree.pop_back();
        n--;
        int pthis=1;
        while(pthis*2<=n){
            int left=pthis*2,right=pthis*2+1,minchild=left;
            if(right<=n&&comp(tree[right],tree[left]))minchild=right;
			if(comp(tree[minchild],tree[pthis])){
                swap(tree[pthis],tree[minchild]);
                pthis=minchild;
            }else break;
        }
    }
};
int main() {
    heap<int>ppp;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		ppp.push(x);
	}
	for(int i=0;i<n;i++){
		cout<<ppp.top()<<" ";
		ppp.pop();
	}
    return 0;
}

归并排序

//如果·左区间：  5 6 7  
//右区间：  1 2 9  

//1：由于 5>1，所以产生了逆序对，这里，我们发现，左区间所有还没有被合并的数都比 1 大，所以1与左区间所有元素共产生了 3 个逆序对(即tot_numleft-i+1对)，统计答案并合并 1 
//2：由于 5>2，由上产生了3对逆序对，统计答案并合并 2
//3：由于 5<9, 没有逆序对产生，右区间下标 j++
//4：由于 6<9, 没有逆序对产生，右区间下标 j++
//5：由于 7<9, 没有逆序对产生，右区间下标 j++




#include<bits/stdc++.h> 
using namespace std;
#define int long long
// long long a[11561511];
const int N=1E6;
long long a[N],b[N],cyt=0;;
void guib(int left,int right){
   //归并
   if(left==right ){//区间已经有序
      return;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   //lancas Lancas
   }
   int le=left,centre=left/2+right/2,ri=centre+1;//le=左区间扫的指针 ri=左区间扫的指针 center是中间数 使用等差数列a+b/2求出                                          lancas Lancas
   int l2=left;
   guib(left,centre);//左区间
   guib(centre+1,right);//右区间
   while(le<=centre&&ri<=right){//是否扫完
      if(a[le]<=a[ri]){
         b[l2++]=a[le++];//组合成有序数组·
         // l2++;
         // le++;
      }
      else{
         b[l2++]=a[ri++];
         //cyt+=1
         cyt+=centre-le+1;


      }


   }
   while(le<=centre){//是否扫完
      // if(a[le]<a[ri]){
      //    b[l2++]=a[le++];
      //    // l2++;
      //    // le++;
      // }
      // else{
      //    b[l2++]=a[ri++];
      //    //cyt+=1
      //    cyt+=centre-i+1;
         

      // }
      b[l2++]=a[le++];



   }
   while(ri<=right){//是否扫完
      // if(a[le]<a[ri]){
      //    b[l2++]=a[le++];
      //    // l2++;
      //    // le++;
      // }
      // else{
      //    b[l2++]=a[ri++];
      //    //cyt+=1
      //    cyt+=centre-i+1;
         

      // }
      b[l2++]=a[ri++];



   }
   for(int i=left;i<=right;i++)//覆盖元素组
      a[i]=b[i];

}
signed main(){
   int n,cnt=0;
   cin>>n;
   for(int i=1;i<=n;i++){
      cin>>a[i];
   }
   // for(int i = 1; i <= n; i ++){
   //    for(int j = i; j <= n; j ++){
   //       if(a[i] > a[j])cnt ++;
   //    }
   // }
   guib(1,n);
   for(int i=1;i<=n;i++){
      cout<<a[i]<<" ";
   }

   




   return 0; 
}

双指针快排

#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#define N (int)(1e5+1)

using namespace std;

int a[N],n;

void quicksort(int a[],int l,int r)
{
	if(l>=r)return;
	
	int i=l,j=r,key=rand()%(r-l+1)+l,temp;
	
	temp=a[key];
	a[key]=a[l];
	a[l]=temp;
	key=l;
	
//	printf("key=%d\n",key);
	
	while(true)
	{
		while(a[i]<a[key]) i++;
		while(a[j]>a[key]) j--;
		
		if(i>=j) break;
		
//		printf("%d %d\n",i,j);
		temp=a[i];
		a[i]=a[j];
		a[j]=temp;
		i++;j--;
	}
	
	temp=a[key];
	a[key]=a[j];
	a[j]=temp;
	
	quicksort(a,l,j-1);
	quicksort(a,j+1,r);
}

int main()
{
	scanf("%d",&n);
	srand(time(NULL));
	
	for(int i=0;i<n;++i)
		scanf("%d",&a[i]);
		
	quicksort(a,0,n-1);
	
	for(int i=0;i<n;++i)
		printf("%d ",a[i]);
		
	return 0;
}