快速排序C++實現

    //快速排序


#include<iostream>  
#include<functional>  
#include<Windows.h>  

using namespace std;  

void qksort(int* arr, int cnt)  
{  
    function<int(int*, int, int)> getPivot = [&](int* arr, int left, int right)->int  
    {  
        int mid = (left + right) / 2;  
        if (arr[left] > arr[mid])  
            swap(arr[left], arr[mid]);     
        if (arr[left] > arr[right])  
            swap(arr[left], arr[right]);  
        if (arr[mid] > arr[right])  
            swap(arr[mid], arr[right]);  
        swap(arr[mid], arr[right - 1]);  
        return arr[right - 1];  
    };  

    function<void(int*, int, int)> insertSort = [&](int* arr, int begin, int end)  
    {  
        int i = 0, j = 0;  
        for (i = begin + 1; i <= end; i++)  
        {  
            int tmp = arr[i];  
            for (j = i; j > begin && arr[j - 1] > tmp; j--)  
                arr[j] = arr[j - 1];  
            arr[j] = tmp;  
        }  
    };  

    function<void(int*, int, int)> qk = [&](int* arr, int left, int right)  
    {  
        if (left + 9 <= right)    //當數組元素大于等于10個的時候，我們用快速排序  
        {  
            int pivot = getPivot(arr, left, right);  
            int i = left;  
            int j = right - 1;  
            while (1)  
            {  
                while (arr[++i] < pivot){}  
                while (arr[--j] > pivot){}  
                if (i < j)  
                    swap(arr[i], arr[j]);  
                else  
                    break;  
            }  
            swap(arr[i], arr[right - 1]);  
            qk(arr, left, i - 1);  
            qk(arr, i + 1, right);  
        }  
        else                //當數組元素小于10個的時候我們用插入排序  
            insertSort(arr, left, right);  
    };  

    qk(arr, 0, cnt - 1);  
};  

int main()  
{  
    int arr[1000];  
    int tmp = -1;  

    for (int i = 0; i < 500; i++)  
    {  
        if (i % 2)  
            arr[i] = i*tmp;  
        else  
            arr[i] = i;  
    }  
    for (int i = 500; i < 1000; i++)  
    {  
        if (i % 2)  
            arr[i] = i*tmp;  
        else  
            arr[i] = i;  
    }  

    //我們可以對上面進行全不快排還是部分快排部分插入排序進行時間上的測試，理論上我們元素個數界限是10個，取十個在有些時候不一定是最佳的，但是可以避免一些有害的特殊情形  
    {  
        LARGE_INTEGER  large_interger;  
        double dff;  
        __int64  c1, c2;  
        QueryPerformanceFrequency(&large_interger);  
        dff = large_interger.QuadPart;  
        QueryPerformanceCounter(&large_interger);  
        c1 = large_interger.QuadPart;  

        qksort(arr, 1000);  

        QueryPerformanceCounter(&large_interger);  
        c2 = large_interger.QuadPart;  
        printf("計時%lf毫秒\n", (c2 - c1) * 1000 / dff);  
    }  

    for (auto i : arr)  
        cout << i << endl;  

    cin.get();  
    return 0;  
}  </pre>