代码

void quick_sort(unsigned int a[], int first, int last)
{
    int i, j;
    unsigned int t;
    if(last - first <= 40)
    {
        for(i = first + 1; i <= last; i++)
        {
            t = a[i];
            for(j = i - 1; j >= first && t < a[j]; j--)
                a[j + 1] = a[j];
            a[j + 1] = t;
        }
        return;
    }

    t = a[first];  //第一个元素与中间元素交换
    a[first] = a[first + last >> 1];
    a[first + last >> 1] = t;
    unsigned int stdd = a[first];
    i = first + 1;
    j = last;

    for(;;)
    {
        while(i <= last && a[i] < stdd)
            i++;
        while(j > first && a[j] > stdd)
            j--;
        if(i > j)
            break;
#if 1  //测试证明，这种写法比另一种效率高
        t = a[i];
        a[i++] = a[j];
        a[j--] = t;
#elif 1
        t = a[i];
        a[i] = a[j];
        a[j] = t;
        i++;
        j--;
#endif

    }  //把数组分成>=stdd和<=stdd两部分。即便两个元素相等，也要进行交换。
    /**
    * 把a[i] < stdd、a[j] > stdd改成a[i] <= stdd、a[j] >= stdd虽然正确，
    * 但是当元素全都相同时，会引起两边的元素数量极其不平衡，使得递归深度增加、耗时增加。
    */
    a[first] = a[j];
    a[j] = stdd;

    quick_sort(a, first, j - 1);
    quick_sort(a, j + 1, last);
}

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

评测结果