代码

#include <algorithm>

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

int fun(int *a, int l, int r) {
    int mid = (l + r) >> 1;
    if(a[l] > a[mid]) {
        swap(a[l], a[mid]);
    }
    if(a[l] > a[r]) {
        swap(a[l], a[r]);
    }
    if(a[mid] > a[r]) {
        swap(a[mid], a[r]);
    }
    swap(a[mid], a[r - 1]);
    return a[r - 1];
}

void insertionsort(int *a, int n) {
    int j, p;
    int tmp;
    for(p = 1; p < n; p++) {
        tmp = a[p];
        for(j = p; j > 0 && a[j - 1] > tmp; j--) {
            a[j] = a[j - 1];
        }
        a[j] = tmp;
    }
}

void quicksort(int *a, int l, int r) {
    int i, j;
    int p;
    if(l + 3 <= r) {
        p = fun(a, l, r);
        i = l; j = r - 1;
        for(;;) {
            while(a[++i] < p) {}
            while(a[--j] > p) {}
            if(i < j) {
                swap(a[i], a[j]);
            }
            else {
                break;
            }
        }
            swap(a[i], a[r - 1]);
            quicksort(a, l, i - 1);
            quicksort(a, i + 1, r);
    }
    else {
        insertionsort(a + l, r - l + 1);
    }
}

void sort(int *a, int n) {
	quicksort(a, 0, n - 1);
}

评测结果