【算法教程】【C/C++】基础数学:快排——程序设计思路与代码实现

faryou6个月前 (04-20)技术教程

前言

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


程序设计思路

        在快速排序中,我们需要两个指针,分别是左指针和右指针,即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 转载需经作者授权!

分享到:

扫描二维码推送至手机访问。

版权声明:本文由faryou的博客发布,如需转载请注明出处。

本文链接:https://blog.faryou.eu.org/post/97.html

标签: 算法基础C++
分享给朋友:

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。