C语言递推与递归数据结构实验之排序八：快速排序

ゝ一世哀愁。 2022-06-01 06:54 157阅读 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>
    void struff(int s[], int l, int r)
    {
        int key, i, j;
        i = l;
        j = r;
        key = s[l];
        if(l >= r)
            return;
        while(i < j)
        {
            while(i < j && s[j] >= key)
            j--;
            s[i] = s[j];
            while(i < j && s[i] <= key)
            i++;
            s[j] = s[i];
        }
        s[i] = key;
        struff(s, l, i - 1);
        struff(s, i + 1, r);
    }
    int main()
    {
        int n, i;
        int s[100000];
        while(scanf("%d", &n) != EOF)
        {
            for(i = 0; i < n; i++)
            {
                scanf("%d", &s[i]);
            }
            struff(s, 0, n - 1);
            for(i = 0; i < n; i++)
            {
                if(i == 0)
                    printf("%d", s[i]);
                else
                    printf(" %d", s[i]);
            }
            printf("\n");
        }
        return 0;
    }

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