首页 > 代码库 > SDUT 3398 数据结构实验之排序一:一趟快排
SDUT 3398 数据结构实验之排序一:一趟快排
数据结构实验之排序一:一趟快排
Time Limit: 1000MS Memory Limit: 65536KB
Submit Statistic
Problem Description
给定N个长整型范围内的整数,要求输出以给定数据中第一个数为枢轴进行一趟快速排序之后的结果。
Input
连续输入多组数据,每组输入数据第一行给出正整数N(N < = 10^5),随后给出N个长整型范围内的整数,数字间以空格分隔。
Output
输出一趟快速排序后的结果,数字间以一个空格间隔,行末不得有多余空格。
Example Input
8 49 38 65 97 76 13 27 49
Example Output
27 38 13 49 76 97 65 49
DQE:
排序算法可参照快速排序-百度百科所给出的C++标准示例,去掉递归执行即为一趟快排。
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 int f[100010]; 5 6 void qs(int l,int r) 7 { 8 if(l>=r) 9 return ; 10 int k=f[l]; 11 int i=l,j=r; 12 while(i<j) 13 { 14 while(i<j&&f[j]>=k) 15 j--; 16 f[i]=f[j]; 17 while(i<j&&f[i]<=k) 18 i++; 19 f[j]=f[i]; 20 } 21 f[i]=k; 22 // qs(l,i-1); 23 // qs(i+1,r); 24 } 25 26 int main() 27 { 28 int n,i; 29 while(scanf("%d",&n)!=EOF) 30 { 31 for(i=1;i<=n;i++) 32 scanf("%d",f+i); 33 qs(1,n); 34 for(i=1;i<=n;i++) 35 printf("%d%c",f[i],i==n?‘\n‘:‘ ‘); 36 } 37 return 0; 38 } 39 40 /*************************************************** 41 User name: *** 42 Result: Accepted 43 Take time: 0ms 44 Take Memory: 168KB 45 Submit time: 2016-12-03 13:44:08 46 ****************************************************/
SDUT 3398 数据结构实验之排序一:一趟快排
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。