简单实现快速排序

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

#define size 100


void isort(int t[], int length)
{
    int i, j;
    int tmp;
    for(i = 1; i < length; i++) {
        tmp = t[i];
        for(j = i;j > 0; j--) {
            if(t[j-1] > tmp)            // 是与 tmp 比较 而不是 t[j]
                t[j] = t[j-1];
            else
                break;
        }
        t[j] = tmp;
    }
}

void swap(int &a, int &b){
    int tmp = a;
    a = b;
    b = tmp;
}


int select(int t[], int start, int end)
{
    int mid = (start + end) / 2;
    if(t[start] > t[mid])
        swap(t[start], t[mid]);
    if(t[start] > t[end])
        swap(t[start], t[end]);
    if(t[mid] > t[end])
        swap(t[mid], t[end]);
    swap(t[mid], t[end-1]);
    return t[end-1];
}


void msort(int t[], int length)
{
    int left = 0;
    int right = length - 1;
    int watershed;
    if(length <= 4) {
        isort(t, length);
        return ;
    }    
    watershed = select(t, left, right);
    int i, j;
    i = 0;
    j = right - 1;
    while(i < j) {
        while(t[++i] < watershed) {}        //i 会在大于等于 watershed 的地方停下
        while(t[--j] > watershed) {}        //j 会在小于等于 watershed 的地方停下
        if(i < j)
            swap(t[i], t[j]);
    }
    swap(t[i], t[right - 1]);
    msort(t, i + 1);
    msort(t + i + 1, length -i - 1);
}


int main()
{
    time_t seed;
    int n[size];

    seed = time(0);
    srandom(seed);

    for(int i = 0; i < size; i++) {
        n[i] = random()%1000;
    }
    msort(n, size);
    for(int i = 0; i < size; i++) 
        printf("%d ",n[i]);
    printf("\n");
    return 0;
}