ACM模板——排序 - 快速排序（三数取中 + 插排 + 聚集相等元素）

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
using namespace std;
typedef long long ll;
const int maxn=3e6+100;
int arr[maxn];
/* 直接插入排序 */
void InsertSort(int low,int high)
{
    int i,j;
    for(i=low+1;i<=high;i++)
    {
        if(arr[i]<arr[i-1])
        {
            arr[0]=arr[i];
            arr[i]=arr[i-1];
            for(j=i-2;arr[0]<arr[j];j--)
                arr[j+1]=arr[j];
            arr[j+1]=arr[0];
        }
    }
}
/* 取待排序序列中low、mid、high三个位置上数据，选取他们中间的那个数据作为枢轴 */
int SelectPivotMedianOfThree(int low,int high)
{
    int mid=low+((high-low)>>1); // >> 优先级低于 + -
    if(arr[mid]>arr[high]) swap(arr[mid],arr[high]);
    if(arr[low]>arr[high]) swap(arr[low],arr[high]);
    if(arr[mid]>arr[low]) swap(arr[mid],arr[low]);
    return arr[low]; // low的位置上保存这三个位置中间的值
}
/* 快排 */
void QSort(int low,int high)
{
    int first,last,left,right,llen,rlen;
    first=left=low, last=right=high, llen=rlen=0;
    if(high-low+1<=10)
    {
        InsertSort(low,high);
        return;
    }
    int key=SelectPivotMedianOfThree(low,high);
    while(low<high)
    {
        while(high>low && arr[high]>=key)
        {
            if(arr[high]==key)
            {
                swap(arr[right],arr[high]);
                right--, rlen++;
            }
            high--;
        }
        arr[low]=arr[high];
        while(high>low && arr[low]<=key)
        {
            if(arr[low]==key)
            {
                swap(arr[left],arr[low]);
                left++, llen++;
            }
            low++;
        }
        arr[high]=arr[low];
    }
    arr[low]=key;
    // 一次快排结束，把与枢轴 key 相同的元素移到枢轴最终位置周围
    int i=low-1, j=first;
    while(j<left && arr[i]!=key)
    {
        swap(arr[i],arr[j]);
        i--, j++;
    }
    i=low+1, j=last;
    while(j>right && arr[i]!=key)
    {
        swap(arr[i],arr[j]);
        i++, j--;
    }
    QSort(first,low-1-llen);
    QSort(low+1+rlen,last);
}
int main()
{
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    QSort(1,n);
    for(int i=1;i<=n;i++)
    {
        if(i==1)
            printf("%d",arr[i]);
        else
            printf(" %d",arr[i]);
    }
    puts("");
    return 0;
}