图解快速排序（c++、递归）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了图解快速排序（c++、递归），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2120字，纯文字阅读大概需要4分钟。

内容图文

假设有如下数组：

A = {15,10,6,1}
B = {1}
C = {20,5}

对数组进行从小到大的排序，随机取一个数组里的值记为BaseValue，
然后将所有小于BaseValue值放在左边，所有大于BaseValue的放在右边（相等的就不动了）。
对于数组B来说不用进行操作就完成了目标，对于C来说进行一次上述操作就能完成排序。

但是对A数组来说就不是那么简单了。

我们用递归的方式来对数组进行拆分，直到数组长度<= 1（也就是B数组一样的状态）

1.先选择数组第一位作为随机值保存为基准值BaseValue,并将第一位用做调换位置的空位。

注意：有红色斜杆的格子意思是空位可覆盖。

2.向左遍历，发现arr[3]比BaseValue值小，放到左边第一个空位

3.当前空位在arr[3]

4.把大于BaseValue的放在右边空位

5.当前空位在arr[1]

6.重新从右向左遍历，发现arr[2] <= BaseValue ,放到左边空位

7.当 i <= j的时候，终止while循环

8.将基准值放到当前空位 arr[i]或arr[j].这样所有小于BaseValue的都在左边，大于的都在右边了。

9.再将数组拆分成左右俩个部分（不需要包含基准值了，位置已经正确）通过递归拆分成越来越小的部分，

直到startIndex >= endIndex。

 

10.如果选择第一位作为基准值必须先从右往左遍历，选择最后一位作为基准值就必须从左往右开始遍历。

 

void qsort1(std::vector<int> &v, int startIndex, int endIndex)
{
	if(startIndex >= endIndex)
		return;

	int tmp, i,j, BaseValue;
	i = startIndex;
	j = endIndex;
	//取数组第一个值作为基准值 根据大小的对比将数组分成左右俩边
	//存储了起始位置的值，为了空出一个位置来做调换。
	BaseValue = v[startIndex];

	while(i < j)
	{
		//从右开始向左遍历，找到小于基准值的那个数值的索引j(等于基准值的不管，跳过)
		while(i < j && v[j] >= BaseValue)
			--j;
		//将小于基准值的放到数组的左边
		v[i] = v[j];
		//从左向右遍历，找到大于基准值的那个数值的索引i(等于基准值的不管，跳过)
		while(i < j && v[i] <= BaseValue)
			++i;

		//将大于基准值的放到数组的右边
		v[j] = v[i];

	}
	//将基准值放回当前的空位上
	v[i] = BaseValue;

	//继续对当前基准值左、右边的内容进行重复的操作,直到拆分的数组长度<=1也就是startIndex>=endIndex
	//基准值的位置(当前是i和j,i=j)就不用变了。
	qsort1(v, startIndex, i - 1);
	qsort1(v, i + 1, endIndex);

}

int main(int argc, char const *argv[])
{
	
	std::vector<int> arr = {6,1,1,3,15,6,8,20,2,7,7,10};

	qsort1(arr, 0, arr.size()-1);
	printf("\n快速排序的结果：\n"); 
	for (int i = 0; i < arr.size(); ++i)
	{
		printf("%d ", arr[i]); 
	}

	return 0;
}

如果有用顺手点个赞不过分吧？

内容总结

以上是互联网集市为您收集整理的图解快速排序（c++、递归）全部内容，希望文章能够帮你解决图解快速排序（c++、递归）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---