//高速排序#include
     
      #include
      
       #include
       
        using namespace std;void qksort(int* arr, int cnt){	function
        
          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
         
           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
          
            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;}