递归之快速排序

爱被打了一巴掌 2022-06-11 03:23 173阅读 0赞

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

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

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

#### Input ####

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

#### Output ####

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

#### Example Input ####

8
    49 38 65 97 76 13 27 49

#### Example Output ####

13 27 38 49 49 65 76 97

代码：

//快速排序：
    #include <stdio.h>
    #include <stdlib.h>
    void f(int a[],int l,int r)
    {
        int i,j,key;
        i = l;
        j = r;
         key = a[l];   //注意key的值为a[L]而不是a[0]，再次调用函数时，边界不一定为0；
        if(l>=r)
            return;   //若l>= r,直接返回 
        while(i<j)
        {
            while(a[j]>=key&&i<j)  //注意限制条件i<j
                j--;
            a[i] = a[j];
            while(a[i]<=key&&i<j)
                i++;
            a[j] = a[i];
        }
        a[i] = key;   //把key赋给a[i]
            f(a,l,i-1);  //上面将数组分成两部分，再次调用函数，继续分，从而达到排序的目的
            f(a,i+1,r);
    
    
    }
    int main()
    {
       int n,i;
       int a[100005];
       while(scanf("%d",&n) !=EOF)
       {
           for(i=0;i<=n-1;i++)
           {
               scanf("%d",&a[i]);
           }
           f(a,0,n-1);
           for(i=0;i<=n-2;i++)
            printf("%d ",a[i]);
           printf("%d\n",a[n-1]);
       }
        return 0;
    } 
    注意开数组的大小，否则容易运行超时

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2186/pid/3491.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2186/pid/3491.html