//高速排序

#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;

}