代码

#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int n, maxdeep;
priority_queue<int, vector<int>, greater<int> > pq;
void insertSort(unsigned *arr,int l, int r) {
    for(int i = l + 1; i <= r; i++) {
        int j = i;
        while(j > l) {
            if(arr[j] < arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
                j--;
            } else {
                break;
            }
        }
    }
}
int getMaxDeep(int x) {
    int k;
    for(k = 0; x > 1; x >>= 1)  k++;
    return k * 2;
}
int getPivot(int l, int r) {
    int ix = l, iy = r - 1, iz = (l + r - 1) >> 1;
    int x = arr[ix], y = arr[iy], z = arr[iz];
    if(x > y) {
        if(x > z) {
            if(y > z) {
                return iy;
            } else {
                return iz;
            }
        } else {
            return ix;
        }
    } else {
        if(x > z) {
            return ix;
        } else {
            if(y > z) {
                return iz;
            } else {
                return iy;
            }
        }
    }
}
void heapSort(unsigned *arr,int l, int r) {
    for(int i = l; i <= r; i++) pq.push(arr[i]);
    for(int i = l; i <= r; i++) {
        arr[i] = pq.top();
        pq.pop();
    }
}
void introSortLoop(unsigned *arr,int l, int r, int deep) {
    if(l >= r)  return;
    if(r - l <= 16) {
        return;
    }
    if(deep >= maxdeep) {
        heapSort(l, r);
        return;
    }
    int i = l, j = r;
    swap(arr[l], arr[getPivot(l, r)]);
    int pivot = arr[l];
    while(i < j) {
        while(i < j && arr[j] >= pivot) j--;
        while(i < j && arr[i] <= pivot) i++;
        if(i < j)
            swap(arr[i], arr[j]);
    }
    swap(arr[l], arr[i]);
    introSortLoop(arr,l, i - 1, deep + 1);
    introSortLoop(arr,i + 1, r, deep + 1);
}
void introSort(unsigned *arr,int l,int r) {
    introSortLoop(arr,l, r - 1, 0);
    insertSort(arr,l, r - 1);
}

void sort(unsigned *a, int n) {
        maxdeep = getMaxDeep(n)
	introSort(a,1,n);
}

评测结果