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

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

TimeLimit: 1000MS Memory Limit: 65536KB

SubmitStatistic

PRoblemDescription

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

Input

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

Output

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

ExampleInput

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: Accepted
Take time: 0ms
Take Memory: 156KB
Submit time: 2017-02-22 19:55:13
****************************************************/

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

相关推荐