数据结构实验之排序八:快速排序
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
给定N(N≤10^5)个整数,要求用快速排序对数据进行升序排列,注意不得使用STL。
Input
连续输入多组数据,每组输入数据第一行给出正整数N(≤10^5),随后给出N个整数,数字间以空格分隔。
Output
输出排序后的结果,数字间以一个空格间隔,行末不得有多余空格。
Sample Input
8
49 38 65 97 76 13 27 49
Sample Output
13 27 38 49 49 65 76 97
Hint
Source
#include <stdio.h>
void pai(int a[] , int l , int r)
{
int i = l , j = r , key = a[l];
if (l > r)
{
return ;
}
while(i < j)
{
while(i < j && a[j] >= key)
{
j--;
}
a[i] = a[j];
while(i < j &&a[i] <= key)
{
i++;
}
a[j] = a[i];
}
a[i] = key;
pai(a , i + 1 , r);
pai (a , l ,i - 1);
}
int main ()
{
int n , i ;
int a[100001];
while(~scanf("%d" , &n))
{
for (i = 0 ; i < n ; i++)
{
scanf("%d" , &a[i]);
}
pai(a , 0 , n - 1);
for (i = 0 ; i < n ;i++)
{
printf("%d%c" , a[i] , i==n - 1?'\n':' ');
}
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)