博客

算法提高 快速排序

时间限制：1.0s   内存限制：256.0MB

问题描述


用递归来实现快速排序（quick sort）算法。快速排序算法的基本思路是：假设要对一个数组a进行排序，且a[0] = x。首先对数组中的元素进行调整，使x放在正确的位置上。同时，所有比x小的数都位于它的左边，所有比x大的数都位于它的右边。然后对于左、右两段区域，递归地调用快速排序算法来进行排序。

输入格式：输入只有一行，包括若干个整数（不超过10个），以0结尾。

输出格式：输出只有一行，即排序以后的结果（不包括末尾的0）。


输入输出样例

样例输入

5 2 6 1 7 3 4 0

样例输出

1 2 3 4 5 6 7

#include <stdio.h>

int partition(int a[], int begin, int end)
{
    int mid = (begin + end) / 2;
    a[0] = a[mid];
    a[mid] = a[begin];
    while (begin < end)
    {
        while (begin < end && a[end] >= a[0])
            end--;
        a[begin] = a[end];
        while (begin < end && a[begin] <= a[0])
            begin++;
        a[end] = a[begin];
    }
    a[begin] = a[0];
    return begin;
}

void quicksort(int a[], int begin, int end)
{
    if (begin >= end)
        return;

    int pivot = partition(a, begin, end);
    quicksort(a, begin, pivot - 1);
    quicksort(a, pivot + 1, end);
}

int main()
{
    int a[12] = { 0 };
    int n = 0, idx = 1, elem;

    scanf("%d", &elem);
    while (elem != 0)
    {
        n++;
        a[idx++] = elem;
        scanf("%d", &elem);
    }

    quicksort(a, 1, n);

    for (int i = 1; i <= n; ++i)
        printf("%d ", a[i]);

    return 0;
}