C++ 快排算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++ 快排算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1467字，纯文字阅读大概需要3分钟。

内容图文

快速排序, 利用了分治思想, 将问题分成细小部分, 大问题打碎成一个个小问题, 一个一个的突破处理.
快排, 现实中有一个常见的场景, 就是一群人从矮到高排列.
先拿一个人出来, 这个人作为参照, 比这个人高的全部排在后面, 比这个人矮的全部排在前面.
排完后, 以这个人为分界, 前面都是比这个人矮的, 后面的都是比这个人矮的, 所以后面只需要前面部分和后面部分自己再按照上面的方式类推地进行排序就可以了

#include <iostream>
#include <stdio.h>
#include <vector>

using std::vector;

void quickSortSln(vector<int>& vec, int start, int end) {
	
	int j = end, i = start;
	
	// 返回条件, 不然会陷入死循环
	if (i >= j)
		return;

	// 记录分界值, 此时vec[start]当做让出了位置, 该位置算是空位
	int mid = vec[start];

	while (i < j) {
		for (; i < j; j--) {
			// 从右边界(最右端)开始找, 看看哪个值比分界值小
			// 比分界值小的就要挪到前面空位
			if (mid > vec[j]) {
				vec[i++] = vec[j];
				break;
			}
		}
		for (; i < j; i++) {
			// 从左边界(最左端)开始,比分界值大的,
			// 挪到后面的空位
			if (mid < vec[i]) {
				vec[j--] = vec[i];
				break;
			}
		}
	}
	vec[i] = mid; // 排完后,会有一个空位留给mid, 入列

	quickSortSln(vec, 0, i-1); // mid的前部分继续排
	quickSortSln(vec, i+1, end); // mid的后部分继续排
}

int main() {
	vector<int> vec = {23, 15, 37, 89, 2, 21, 43, 9, 56};

	int idx = 0;
	printf("traverse beg\n");
	while (idx < vec.size()) {
		printf("vec[%d] = %d\n", idx, vec[idx]);
		idx++;
	}
	printf("traverse end\n");

	quickSortSln(vec, 0, vec.size() - 1);

	std::cout << "traverse start\n";
	
	idx = 0;
	while (idx < vec.size()) {
		printf("vec[%d] = %d\n", idx, vec[idx]);
		idx++;
	}
	printf("traverse end\n");

	return 0;
}

内容总结

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

内容备注

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

内容手机端

---