#include "test.h"

// 三数取中
int GetMid(const vector<int>& arr, int left, int right)
{
	int mid = (right - left) / 2 + left;
	if ((arr[left] < arr[mid] && arr[mid] < arr[right]) || (arr[right] < arr[mid] && arr[mid] < arr[left]))
	{
		return mid;
	}
	else if ((arr[mid] < arr[left] && arr[left] < arr[right]) || (arr[right] < arr[left] && arr[left] < arr[mid]))
	{
		return left;
	}
	else 
	{
		return right;
	}
}
// 原始快排
void QuickSortSubfunc1(vector<int>& arr,int begin,int end)
{
	if (begin >= end)
	{
		return;
	}
	
	int left = begin, right = end;

	// 将最左边的值作为key
	//int key = left;

	// 随机key
	//int key = rand() % (right - left + 1) + left;
	//swap(arr[key], arr[left]);
	//key = left;

	// 三数取中
	int key = GetMid(arr, left, right);
	swap(arr[key], arr[left]);
	key = left;

	while (left < right)
	{
		while (left < right && arr[right] >= arr[key])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[key])
		{
			left++;
		}
		swap(arr[right], arr[left]);
	}

	swap(arr[key], arr[left]);
	QuickSortSubfunc1(arr, begin, left - 1);
	QuickSortSubfunc1(arr, left + 1, end);
}
// 挖坑法
void QuickSortSubfunc2(vector<int>& arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int left = begin, right = end;

	// 将最左边的值作为key
	//int key = left;

	// 随机key
	//int key = rand() % (right - left + 1) + left;
	//swap(arr[key], arr[left]);
	//key = left;

	// 三数取中
	int key = GetMid(arr, left, right);
	swap(arr[key], arr[left]);
	key = left;

	int keyval = arr[key];
	while (left < right)
	{
		while (left < right && arr[right] >= arr[key])
		{
			right--;
		}
		if (left < right)
		{
			arr[key] = arr[right];
			key = right;
		}
		while (left < right && arr[left] <= arr[key])
		{
			left++;
		}
		if (left < right)
		{
			arr[key] = arr[left];
			key = left;
		}
	}
	arr[key] = keyval;
	QuickSortSubfunc2(arr, begin, key - 1);
	QuickSortSubfunc2(arr, key + 1, end);
}
// 快慢双指针
void QuickSortSubfunc3(vector<int>& arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int left = begin, right = end;

	// 将最左边的位置作为key
	//int key = left;

	// 随机key
	//int key = rand() % (right - left + 1) + left;
	//swap(arr[key], arr[left]);
	//key = left;

	// 三数取中
	int key = GetMid(arr, left, right);
	swap(arr[key], arr[left]);
	key = left;

	int slow = left, fast = left + 1;
	while (fast <= right)
	{
		if (arr[fast] < arr[key])
		{
			slow++;
			swap(arr[slow], arr[fast]);
		}
		fast++;
	}

	swap(arr[key], arr[slow]);
	QuickSortSubfunc3(arr, begin, slow - 1);
	QuickSortSubfunc3(arr, slow + 1, end);
}

// QuickSortThreeWay 三路快排，可以高效处理大量重复元素
void QuickSortThreeWay(vector<int>& arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	// 三数取中
	int key = GetMid(arr, left, right);
	swap(arr[key], arr[left]);
	int keyVal = arr[left];
	// 三项切分：[left, lt-1] < keyVal, [lt, gt] == keyVal, [gt+1, right] > keyVal
	int lt = left, gt = right, i = left + 1;
	while (i <= gt)
	{
		if (arr[i] < keyVal)
		{
			swap(arr[i], arr[lt]);
			lt++;
			i++;
		}
		else if (arr[i] > keyVal)
		{
			swap(arr[i], arr[gt]);
			gt--;
		}
		else
		{
			i++;
		}
	}
	QuickSortThreeWay(arr, left, lt - 1);
	QuickSortThreeWay(arr, gt + 1, right);
}

// NonRecursiveQuickSort 非递归快排
void NonRecursiveQuickSort(vector<int>& arr)
{
	int begin = 0, end = arr.size() - 1;
	stack<pair<int, int>> s;

	if (begin < end)
	{
		s.emplace(begin, end);
	}

	while (!s.empty())
	{
		int left = s.top().first, right = s.top().second;
		s.pop();

		int key = GetMid(arr, left, right);
		swap(arr[key], arr[left]);
		key = left;

		int slow = left, fast = left + 1;
		while (fast <= right)
		{
			if (arr[fast] < arr[key])
			{
				slow++;
				swap(arr[slow], arr[fast]);
			}
			fast++;
		}

		swap(arr[key], arr[slow]);
		if (left < slow - 1)
		{
			s.emplace(left, slow - 1);
		}
		if (slow + 1 < right)
		{
			s.emplace(slow + 1, right);
		}
	}
}

// QuickSort 快速排序
// 平均时间复杂度：O(N*logN)
// 空间复杂度：O(logN)
// 不稳定排序
void QuickSort(vector<int>& arr)
{
	int n = arr.size();
	//QuickSortSubfunc1(arr, 0, n - 1);
	//QuickSortSubfunc2(arr, 0, n - 1);
	//QuickSortSubfunc3(arr, 0, n - 1);
	//NonRecursiveQuickSort(arr);
	QuickSortThreeWay(arr, 0, n - 1);
}