算法学习之快速排序

#include <stdio.h>
/*快速排序算法，复杂度O(nlogn)*/
void quick_sort(int *a,int from,int to)
{
    if(from >= to) //如果子数组只剩一个元素则递归完毕
        return;
    int key = a[from]; //等于数组的第一个元素
    int i = from;
    int j = to;
    while(i < j)
    {
        while(i < j && a[j] >= key) //找右边第一个比关键字小的数
            j--;
        a[i] = a[j];   //赋值到左边的一个空闲位置，这个i就是上次循环被移到后边的i，或者key所在的位置，所以不会覆盖掉
        while(i < j && a[i] <= key) //找左边第一个比关键字大的数
            i++;
        a[j] = a[i];   //复制到右边的一个空闲位置,因为这个j就是上次循环那个j的位置，所以直接覆盖
    }
    a[i] = key; //经过循环一遍后，除了key所有的数都找到了新位置，所以将key放到中枢位置
    quick_sort(a,from,i-1);//递归排序，左边子数组
    quick_sort(a,i+1,to);//递归排序右边子数组
}
int main()
{
    int n;
    int arry[100];
    scanf("%d",&n);
    int i;
    for(i = 0; i < n; i++)
        scanf("%d",&arry[i]);
    quick_sort(arry,0,n-1);
    for(i = 0; i < n; i++)
        printf("%d ",arry[i]);
    return 0;
}