优化版本是中间插值法 来源于洛谷深入浅出教程 原始版本来源于啊哈算法

#include <iostream>
/* 
给出了快排的优化版本 
*/ 
 
using namespace std;
void quicksort(long long int *p,int left,int right); 
int main()
{
	int n;
	int i,j;
	cin>>n;
	long long int a[n];
	long long int (*p)=a;
	for(i=0;i<n;i++)
	{
		cin>>a[i];
	}
	quicksort(a,0,n-1);
	for(i=0;i<n-1;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<a[i]<<endl;
	return 0;
}
void quicksort(long long int *p,int left,int right)
{
	int temp,i,j,t;//i，j都是走动的数字，t是交换数字存的数，temp暂存基准点
	if(left>right)
	return;
	i=left;
	j=right;
	
	int flag=p[(left+right)/2];
	do
	{
		while(p[i]<flag)i++;//两个while找数 但是没有判断相遇，因为会停在中间值前 或者中间值上 
		while(p[j]>flag)j--;
		if(i<=j)//因为do while，所以写此if 不再交换，不写等号程序跳不出循环 
		{
			temp=p[i];p[i]=p[j];p[j]=temp;//该程序没有把temp作为基准点 而是把temp作为两个数交换的工具 
			i++;j--;
		}
	}while(i<=j);//最后一次循环 会使得聚在中间点的ij向左右各跳一个，导致i>j这也是do while循环的目的 (即i=j两个while都停止，但是if中的语句使得i++，j--)
	if(left<j)quicksort(p,left,j);//left<j说明j没有遇到left 即最中间的那个数字还是没有排好 
	if(right>j)quicksort(p,i,right);
	
	//这是优化前的算法 
	/*
		快速排序基本思想
	首先确定一个基准点 基准点左右各一个数
	右侧先走 当遇到比基准点小的数停下
	左侧后走 当遇到比基准点大的数停下
	如果左右相遇 则相遇位置与基准点交换
	做一个递归
	相遇点左侧继续上述操作
	直到操作到最左侧
	最后右侧一直操作
	通过函数方式实现
	该函数只需给出左位置和右位置
	*/
	/*while(i!=j)
	{
		while(p[j]>=temp&&j>i)
		{
			j--;
		}
		while(p[i]<=temp&&j>i)
		{
			i++;
		}
		if(i<j)
		{
			t=p[i];
			p[i]=p[j];
			p[j]=t;
		}
	}
	p[left]=p[i];
	p[i]=temp;
		quicksort(p,left,i-1);
		quicksort(p,i+1,right);
	*/
}