前言

        有时候，我们需要对数组进行排序，而在算法中，由于对效率的追求，选择排序和冒泡排序已经无法满足我们的需求。这时，我们就需要使用效率更高的快排。

程序设计思路

        在快速排序中，我们需要两个指针，分别是左指针和右指针,即left和right。他们从数组两端出发，相向而行。之后找到中点，作为基准数，比基准数大的和小的各自到一边（为讲解方便，这里讲升序）。当左右指针相遇时，我们已经将所有的数分为两组。之后，我们再次进行相同操作，直到将所有的数分组不断细化，最后每个数一组。

        这样一来，我们不难想到递归。即当主程序结束后，我们对两组数再次调用主程序本身，之后再次调用。

        这种方法的时间复杂度是O(n log n)。

代码实现

void qsort(long long a[],long long left,long long right){三个参数分别为数组名、左右端点
	long long i,j,t;//i、j分别存放左右端点
	if(left>=right) return;//特判，用于最后退出程序
	int x=(left+right)/2;//取中点
	swap(a[x],a[left]);//防止重复
	t=a[left];//基准数
	i=left;
	j=right;
	while(i<j){
		while(a[j]>=t && i<j) j--;//j不断向左，直到发现小数
		while(a[i]<=t && i<j) i++;//i不断向右，直到发现大数
		if(i<j) swap(a[i],a[j]);//如果i比j小，交换
		else break;
	}
	swap(a[left],a[i]);//调换回来
	
	//再次调用
	if(left<i) qsort(a,left,i-1);
	if(right>i) qsort(a,j+1,right);
}

sort( , , )函数使用

        在C++的STL库中，有一个sort函数，可以省去我们自写快排的烦恼。

        sort( , , )函数的第一个参数是数组头地址，第二个参数是数组尾地址。第三个是cmp函数名称。下面是对数组x[ ]进行排序的代码：

int k=sizeof(x)/sizeof(x[0];//获取数组长度
sort(x,x+k,);//在默认升序序情况下，无需编写cmp()函数

        当我们需要对数组进行降序排序时，就需要自写cmp函数，像这样：

bool cmp(int a,int b){//int为数组数据类型
    return a>b;
}

int k=sizeof(x)/sizeof(x[0];//获取数组长度
sort(x,x+k,cmp);

        sort还可以进行结构体排序，像下面这样：

bool cmp(class a,class b){
    return a.num<b.num;//降序，如需升序请将>改为<；此处对结构体中的元素num进行排序
}

int k=sizeof(x)/sizeof(x[0];//获取数组长度
sort(x,x+k,cmp);//在默认降序情况下，无需编写cmp()函数

        sort函数的时间复杂度为O(n log n)。

结语

        快排极大的提高了效率，使得程序运行速度更快，节省了时间。我是faryou，下次见！

本文链接：https://blog.faryou.eu.org/post/97.html 转载需经作者授权！