/*
 *	算法导论 第九章 中位数和顺序统计学
 *	线性时间选择元素
 */

#include <iostream>
#include <ctime>
using namespace std;

int minimum(int *arr, int len);
int randomizedSelect(int *arr, int p, int r, int i);
int randomizedPartition(int *arr, int p, int r);
void exchange(int arr[], int i, int j);
int partition(int arr[], int p, int r);
int select(int *arr, int p, int r, int i);
int partitionWithPivot(int *arr, int p, int r, int pivot);
void printArray(int arr[], int len, char *str);
int getMedian(int *arr, int p, int r);
void randomizedQuickSort(int *arr, int p, int r);

int main()
{
	int len = 15;
	int *arr = new int[len];

	srand(time(NULL));
	for (int i=0; i<len; i++)
	{
		arr[i] = rand() % 100;
	}
	printArray(arr, len, "原数组");
	cout<<"最小元素为："<<minimum(arr, len)<<endl;
	int i = 3;
	int elem = randomizedSelect(arr, 0, len-1, i);
	randomizedQuickSort(arr, 0, len-1);
	printArray(arr, len, "排序后的数组");
	cout<<"第 "<<i<<" 小的元素为："<<elem<<endl<<endl;

	for (int i=0; i<len; i++)
	{
		arr[i] = rand() % 100;
	}
	printArray(arr, len, "原数组");
	i = 10;
	elem = select(arr, 0, len-1, i);
	randomizedQuickSort(arr, 0, len-1);
	printArray(arr, len, "排序后的数组");
	cout<<"第 "<<i<<" 小的元素为："<<elem<<endl;

	delete[] arr;
	return 0;
}

/*
 *	求数组中的最小值
 *	时间复杂度为O(n)
 */
int minimum(int *arr, int len)
{
	int min = arr[0];
	for (int i=1; i<len; i++)
	{
		if (arr[i] < min)
			min = arr[i];
	}
	return min;
}

/*
 *	随机化选择算法
 *	选择arr[p..r]中第 i 小的元素
 *	使用快速排序中的随机化划分方法，平均情况下每次将选择空间缩小一半
 *	所以在平均情况下，时间复杂度为O(n)
 */
int randomizedSelect(int *arr, int p, int r, int i)
{
	if (p == r)
	{
		return arr[p];
	}

	int q = randomizedPartition(arr, p, r);
	int k = q - p + 1;
	if (k == i)
	{
		return arr[q];
	} else if (i < k) {
		return randomizedSelect(arr, p, q-1, i);
	} else {
		return randomizedSelect(arr, q+1, r, i-k);
	}
}

/*
 *	随机化快速排序
 *	期望时间复杂度为O(nlgn)
 */
void randomizedQuickSort(int *arr, int p, int r)
{
	if (p < r)
	{
		int q = randomizedPartition(arr, p, r);
		randomizedQuickSort(arr, p, q-1);
		randomizedQuickSort(arr, q+1, r);
	}
}

/*
 *	随机化划分
 */
int randomizedPartition(int *arr, int p, int r)
{
	srand(time(NULL));
	int i = p + rand() % (r-p+1);
	exchange(arr, i, r);
	return partition(arr, p, r);
}

void exchange(int arr[], int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

int partition(int arr[], int p, int r)
{
	int pivot = arr[r];
	int i = p - 1;//i前面的（包括i）的元素都是不大于pivot的，i后面的都是大于pivot的元素
	int j;//j后面的（包括j）都是还没有划分的
	for (j=p; j<=r-1; j++)
	{
		if (arr[j] <= pivot)
		{
			i++;
			exchange(arr, i, j);
		}
	}
	i++;
	exchange(arr, i, r);
	return i;
}

/*
 *	最坏情况下线性时间选择算法
 *	此算法依然是建立在快速排序的划分算法基础之上的
 *	但是与randomizedSelect算法的不同指之处，就是次算法的本质
 *	是保证了每次划分选择的划分主元一定是一个较好的主元，算法先对数组5个一组进行分组
 *	然后选择每组的中位数，再递归的选择各组中位数中的中位数作为数组的划分主元，以此保证划分的平衡性
 *	选择中位数的时候必须使用递归调用的方法才能降低时间复杂度
 *	从而保证在最坏情况下都得到一个好的划分
 *	最坏情况下时间复杂度为O(n)
 */
int select(int *arr, int p, int r, int i)
{
	if (p == r)
	{
		return arr[p];
	}

	int len = r-p+1;
	int medianCnt = 1;
	if (len > 5)
		medianCnt = len%5 > 0 ? len/5+1 : len/5;
	int *medians = new int[medianCnt];
	
	//使用插入排序找出每组的中位数
	for (int j=0, k=p; j<medianCnt; j++)
	{
		if (j == medianCnt-1)
		{
			medians[j] = getMedian(arr, k, r);
		} else {
			medians[j] = getMedian(arr, k, k+4);
			k += 5;
		}
	}
	//递归调用select线性时间函数自身选择中位数组中的中位数
	int pivot = select(medians, 0, medianCnt-1, (medianCnt+1)/2);
	delete[] medians;

	int q = partitionWithPivot(arr, p, r, pivot);
	int k = q-p+1;
	if (i == k)
	{
		return pivot;
	} else if (i < k) {
		return select(arr, p, q-1, i);
	} else {
		return select(arr, q+1, r, i-k);
	}
}

/*
 *	根据指定的划分主元pivot来划分数组
 *	并返回主元的顺序位置
 */
int partitionWithPivot(int *arr, int p, int r, int pivot)
{
	int i = p - 1;
	int j = p;

	for (; j<=r; j++)
	{
		//此处用<较为准确
		if (arr[j] < pivot)
		{
			i++;
			exchange(arr, i, j);
		}
	}
	
	for (int j=i+1; j<=r; j++)
	{
		if(arr[j] == pivot)
		{
			exchange(arr, i+1, j);
			break;
		}
	}

	return i+1;
}

/*
 *	利用插入排序选择中位数
 */
int getMedian(int *arr, int p, int r)
{
	//插入排序
	for (int i=p+1; i<=r; i++)
	{
		int key = arr[i];
		int j = i - 1;
		while (j >= p && arr[j] > key)
		{
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = key;
	}
	
	return arr[(p+r)/2];
}

void printArray(int arr[], int len, char *str)
{
	cout << str << endl;
	for (int i=0; i<len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}