Quicksort

算法输入：输入n个元素的数组，A[1,..,n]

算法输出：按非降序排序数组A中的元素

算法思想：先选择主元素，然后找到这个主元在这个数组中的正确位置，然后依次递归就可以快速排序。

算法代码：

#include<stdio.h>
#include<malloc.h>

int split(int*A, int low, int high);
void exchange(int *A, int i, int j);
void quicksort(int *A, int low, int high);

int main()
{

    int N,i;
    int *A;
    A = (int*)malloc(N * sizeof(int));
    printf("Please input the number of the array:");
    scanf("%d", &N);
    printf("Please input the array:");
    for(i=0; i<N; i++)
        scanf("%d",&A[i]);

    quicksort(A, 0, N-1);
    for(i=0; i<N; i++)
        printf("%5d",A[i]);
    return 0;
}

//split算法，确定某一个主元的
int split(int*A, int low, int high)
{
    int i = low;
    int key = A[i];
    int j;
    for (j = low+1; j <= high; ++j)
    {
        if(A[j] <= key)
        {
            i = i + 1;
            if(i !=j)
                exchange(A, i, j);
        }
    }
    exchange(A, low, i);
    int w = i;
    return w;
}

void quicksort(int *A, int low, int high)
{
    if(low < high)
    {
        int w = split(A, low, high);
        quicksort(A, low, w-1);
        quicksort(A, w+1, high);
    }
}

void exchange(int *A, int i, int j)
{
    int tmp = A[i];
    A[i] = A[j];
    A[j] = tmp;
}