sdutacm-数据结构实验之排序八：快速排序

数据结构实验之排序八：快速排序

TimeLimit: 1000MS Memory Limit: 65536KB

SubmitStatistic

PRoblemDescription

给定N(N≤10^5)个整数，要求用快速排序对数据进行升序排列，注意不得使用STL。

Input

 连续输入多组数据，每组输入数据第一行给出正整数N(≤10^5)，随后给出N个整数，数字间以空格分隔。

Output

 输出排序后的结果，数字间以一个空格间隔，行末不得有多余空格。

ExampleInput

8

4938 65 97 76 13 27 49

ExampleOutput

1327 38 49 49 65 76 97

Hint

Author

#include <iostream>#include<bits/stdc++.h>using namespace std;int a[100002];void quicksort(int l,int r){    int i,j;    if(l>r)    return;    i = l;    j = r;    int temp = a[l];    while(i!=j)    {        while(a[j]>=temp&&i<j)        {        j--;        }        a[i] = a[j];        while(a[i]<=temp&&i<j)        {        i++;        }        a[j] = a[i];        //if(i<j)        //{        //swap(a[i],a[j]);        //}    }   a[i] = temp;   //swap(a[l],a[i]);   quicksort(l,i-1);  quicksort(i+1,r);    return ;}int main(){    int n;    while(~scanf("%d",&n))    {    for(int i=0;i<n;i++)    {        scanf("%d",&a[i]);    }    quicksort(0,n-1);    int top = 1;    for(int i=0;i<n;i++)    {    if(top)top=0;    else printf(" ");    printf("%d",a[i]);    }    cout<<endl;    }    return 0;}/***************************************************User name: jk160505徐红博Result: AcceptedTake time: 0msTake Memory: 156KBSubmit time: 2017-02-22 19:55:13****************************************************/