C++算法——快速排序
2022/4/30 12:42:38
本文主要是介绍C++算法——快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
算法思想:
- 1.先从数列中取出一个数作为基准数。
- 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
- 3.再对左右区间重复第二步,直到各区间只有一个数。
算法模板:
1 void quick_sort(int q[], int l, int r) 2 { 3 //递归的终止情况 4 if(l >= r) return; 5 //第一步:分成子问题 6 int i = l - 1, j = r + 1, x = q[l + r >> 1]; 7 while(i < j) 8 { 9 do i++; while(q[i] < x); 10 do j--; while(q[j] > x); 11 if(i < j) swap(q[i], q[j]); 12 } 13 //第二步:递归处理子问题 14 quick_sort(q, l, j), quick_sort(q, j + 1, r); 15 //第三步:子问题合并.快排这一步不需要操作,但归并排序的核心在这一步骤 16 }
例题: 给定你一个长度为 nn 的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。 输入格式 输入共两行,第一行包含整数 nn。 第二行包含 nn 个整数(所有整数均在 1∼1091∼109 范围内),表示整个数列。 输出格式 输出共一行,包含 nn 个整数,表示排好序的数列。 数据范围 1≤n≤1000001≤n≤100000 输入样例: 5 3 1 2 4 5 输出样例: 1 2 3 4 5
#include<bits/stdc++.h> using namespace std; const int N = 100010; int n; int q[N]; void quick_sort(int a[], int l, int r) { if (l >= r) return; int i = l - 1, j = r + 1; int num = a[l + r >> 1]; while(j > i) { do i ++; while(a[i] < num); do j --; while(a[j] > num); if (i < j) swap(a[i], a[j]); } quick_sort( a, l, j); quick_sort( a, j + 1, r); } int main() { cin >> n; for (int i = 0; i < n; i ++) cin >> q[i]; quick_sort(q, 0, n - 1 ); for (int i = 0; i < n; i ++) cout << q[i] << " "; return 0; }
2022-03-27 23:02:39
这篇关于C++算法——快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享