总时间限制: 2000ms 单个测试点时间限制: 500ms 内存限制: 65536kB

描述

随机输入一组数，使用快速排序得到从小到大的序列。

输入

第1行是元素的个数，第2行是各个元素的值，每个元素以空格分隔。

输出

输出有1行，即排完序后由小到大的序列，每个元素之间以空格分隔。

样例输入1

5
9 7 8 5 3

样例输出1

3 5 7 8 9

样例输入2

10
9 8 7 6 5 4 3 2 1 6

样例输出2

1 2 3 4 5 6 6 7 8 9

思路

数组排序可以如下完成:

1. 设k = a[0]，将k挪到适当位置，使得比k小的元素都再k的左边，比k大的元素都在k的右边，和k相等的，不关心。（在O(n)时间内完成）
2. 把k左边的部分快速排序
3. 把k右边的部分快速排序

代码

// Using c99 standard
#include <stdio.h>
void swap(int* a, int* b) {
    *a = (*a) ^ (*b);
    *b = (*a) ^ (*b);   // b <- (a ^ b) ^ b, which is: b <- a
    *a = (*a) ^ (*b);   // a <- (a ^ b) ^ a, which is: a <- b
}
void QuickSort
(int array[], int start, int end) {
    if( start >= end )
       return;
    int pivot = array[start];
    int i = start, j = end;
    while(i != j) {     // partition
        while( j > i && array[j] >= pivot ) 
            j--;
        swap(&array[j], &pivot);
        while( j > i && array[i] <= pivot )
            i++;
        swap(&array[i], &pivot);
    }
    QuickSort(array, start, i-1);
    QuickSort(array, i+1, end);
}
int main() {
    int number;
    scanf("%d", &number);
    int array[number];
    for(int i = 0; i < number; i++) 
        scanf("%d", &array[i]);
    QuickSort(array, 0, 4);
    for(int i = 0; i < 5; i++) 
        printf("%d ", array[i]);
    return 0;
}