快速排序实现(C++)
2021/6/14 20:21:20
本文主要是介绍快速排序实现(C++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
快速排序使用了“分而治之”(D&C: divide and conquer)的思路,我们需要:
- 选择基准值(通常我们取区间开头的元素为基准值)
- 依照其它各个元素相对于基准值的大小关系分成两组,小于(等于)的在一组,大于(等于)的在一组,注意不用给基准值分组了
- 应用递归思想对两个子数组分别继续进行快速排序
这是一种较高效的优雅算法,平均运行时间为O(n*log2(n)),实际运行时间与你的基准值选择有很大的关系
//快速排序 #include<iostream> #include<cstdio> using namespace std; void quicksort(int a[], int, int); int main() { int a[50], len; cin >> len; for (int i = 0;i < len;i++) cin >> a[i]; quicksort(a, 0, len - 1); for (int i = 0;i < len;i++) { cout << a[i] << ' '; if (i % 5 == 4) cout << endl; //每一行输出五个数(从小到大) } return 0; } void quicksort(int s[], int l, int r) { if (l < r) { int i = l, j = r, flag = s[l];//记录好左右起始位置,每一次使用最左侧值为基准值 while (i < j) { while (i < j && s[j] >= flag) j--; if (i < j) s[i++] = s[j];//这里的与下面的 if 判断挺关键的,防止“越界交换”!(本菜鸡在这上面吃过大亏了!) //从后往前走,找到第一个比 flag 小的数并且放到索引 l 处(该处数值被 flag 记录了下来,可以覆盖,并且也相当于该索引 j 处留了一个新的“空位”) while (i < j && s[i] < flag) i++; if (i < j) s[j--] = s[i];//同上相反情况理解 } s[i] = flag;//用 flag 区域分割成“左小右大” //用更小的区域进行有限次递归 quicksort(s, l, i - 1); quicksort(s, i + 1, r); } }
示例:
这篇关于快速排序实现(C++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享