C 语言写的快排程序

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

void quickSort(int a[], int len)
{
    if(len <= 0) {
        return;
    }
    int c = a[0];
    int mid = 0;
    for(int i = 1; i < len; ++i){
        if(a[i] < c){
            a[mid++] = a[i];
        }
    }
    a[mid] = c;
    quickSort(a, mid);
    quickSort(a + mid, len - mid - 1);
    return;
}

int main(int argc, char *argv[])
{
    int a[] = {5,3,1,2,4};
    int len = sizeof(a)/sizeof(int);
    quickSort(a, len);
    for(int i = 0; i < len; ++i){
        printf("a[%d] = %d\n", i,a[i]);
    }
    return 0;
}

首先找到第一个元素 c ，然后找到中点的位置，mid ，同时保证 a[0] 到 a[mid-1] 都小于 c ，a[mid+1] 到 a[len-1] 都大于 c 。之后把 c 放在，a[mid] 的位置。

最后，递归排序比 c 小的部分，和比 c 大的部分。

这个排序重用了原始数据的内存地址，但是递归调用的时候，需要用到额外的栈空间，所以空间复杂度不是 O(1) 。