问题 B: 算法10-6~10-8：快速排序
·
时间限制: 1 Sec 内存限制: 32 MB
提交: 4095 解决: 2233
题目描述
快速排序是对起泡排序的一种改进。它的基本思想是，通过一趟排序将待排序的记录分割成两个独立的部分，其中一部分记录的关键字均比另一部分的关键字小，在分成两个部分之后则可以分别对这两个部分继续进行排序，从而使整个序列有序。
快速排序的算法可以描述如下：
在本题中，读入一串整数，将其使用以上描述的快速排序的方法从小到大排序，并输出。
输入
输入的第一行包含1个正整数n，表示共有n个整数需要参与排序。其中n不超过100000。
第二行包含n个用空格隔开的正整数，表示n个需要排序的整数。
输出
只有1行，包含n个整数，表示从小到大排序完毕的所有整数。
请在每个整数后输出一个空格，并请注意行尾输出换行。
样例输入
10 2 8 4 6 1 10 7 3 5 9
样例输出
1 2 3 4 5 6 7 8 9 10
提示
在本题中，需要按照题目描述中的算法完成快速排序的算法。
快速排序是一种十分常用的排序算法，其平均时间复杂度为O(knlnn)，其中n为待排序序列中记录的个数，k为常数。大量的实际应用证明，在所有同数量级的此类排序算法中，快速排序的常数因子k是最小的，因此，就平均时间而言，快速排序是目前被认为最好的一种内部排序方法。
而在C语言的常用编译器中，qsort函数是一个非常常用的快速排序函数。
代码实现
#include<iostream>
using namespace std;
const int N=1e6+7; //注意 const
int a[N];
void quick_sort(int l,int r){
if(l>=r)return ;
int i=l-1 , j=r+1 , mid=a[(l+r)/2]; //注意 圆括号里是（l+r)
while(i<j){ //注意 是 i < j
while(a[++i]<mid);
while(a[--j]>mid);
if(i<j){swap(a[i],a[j]);} //注意 i < j NOT a[i]<a[j]
}
quick_sort(l,j); //注意 l.j
quick_sort(j+1,r); //注意 j+1 ,r
}
int main()
{
int n; cin>>n;
for(int i=0;i<n;i++){cin>>a[i];}
quick_sort(0,n-1); //$$$$ 0,n-1
for(int i=0;i<n;i++){cout<<a[i]<<" ";}
return 0;
}
//line 9:如果i所指的数比基准值要小，那么i将一直右移，直到比mid大或等
//line 9:因为等于也会终止循环，所以 i 一定不会越过mid；
//line 10:如果i所指的数比基准值要大，那么i将一直左移，直到比mid小或等
//line 11: swap()交换函数，可以替换成：
// { int temp; temp=a[i]; a[i]=a[j]; a[j]=temp;}
//取中间的数作为基准值 mid ;分成左半和右半;
// i 从头向 mid 走(不会越过)；直到将左半换全部成比 mid 小的
// j 从尾向 mid 走(不会越过)；直到将右半换全部成比 mid 大的
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
0
0- 0
已为社区贡献2条内容
所有评论(0)