快速排序

2022/3/5 23:17:02

本文主要是介绍快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

快速排序

快速排序的基本思想是通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所以数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

快速排序的流程:

注意:f是表示指的数比标杆值小的下标值,而b是表示指的数比标杆值大的下标值

代码示例:

void quick_sort(int parr[], int low, int hight)	//快速排序
{
	int t = parr[low];	//确定标杆值
	int f = low + 1;	//表示指的数比标杆值小的下标值
	int	b = hight;		//表示指的数比标杆值大的下标值

	if (low >= hight) return;	//表示只有一个元素,无需定位

	int tempval;
	while (f <= b)//表示待查找的区间还没有找完(只有f>b才能算找完)
	{
		while (f <= b && parr[f] <= t) f++;//表示区间没有找完,且f指的数又比标杆小
		while (f <= b && parr[b] >= t) b--;//表示区间没有找完,且b指的数又比标杆大
		if (f < b)//定位区间还没搜索完,但f指向了比标杆大的数,b指向了比标杆小的数
		{
			tempval = parr[f];
			parr[f] = parr[b];
			parr[b] = tempval;
			f++;
			b--;
		}
	}
	//循环完,b指针应该停在了标杆的位置,f指针停在了标杆的下一个位置
	parr[low] = parr[b];
	parr[b] = t;
	quick_sort(parr, low, b - 1);//标杆的左边递归
	quick_sort(parr, b + 1, hight);//标杆的右边递归
}


这篇关于快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程