快速排序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;  
    }  

标签： swap

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。