#pragma once
#include<iostream>
using namespace std;

//插入排序,升序
void Insert_Sort(int array[],const int left,const int right)
{
	for (int i = left; i <= right; i++)
	{
		int j = i - 1;
		int key = array[i];
		while (j >= left&&array[j] >= key)
		{
			array[j + 1] = array[j];
			j--;
		}
		array[j + 1] = key;
	}
}

//找array的中位数的中位数，interval为分段间隔
int FindMedia(int array[],int left,int right,const int interval)
{
	//到头了，不再分段，直接排序，返回中位数
	if (right - left +1 <= interval)
	{
		Insert_Sort(array,left,right);
		return(array[(left + right) / 2]);
	}

	//分段，对新的中位数数组递归找中位数
	int *media_array = new int[(right - left +1 ) / interval];
	int i = 0;
	while (i<(right - left+1) / interval)
	{
		Insert_Sort(array,i*interval+left,(i + 1)*interval-1+left);
		media_array[i] = array[i*interval + interval / 2+left];
		i++;
	}
	return FindMedia(media_array,(right - left+1) / interval-1,interval);
}

//找中位数的位置下标
int FindMediaIndex(int array[],int media,int right)
{
	for (int i = left; i <=right; i++)
		if (array[i] == media)
			return i;
}

//寻找array中left-right这一段（right-left+1个元素）中第第k小的数（策略：interval分化中项的中项做pivot）
int SelectK(int array[],const int k,const int interval)
{
	//找中位数的中位数
	int media = FindMedia(array,right,interval);
	//找media在array中的位置
	int media_index = FindMediaIndex(array,media,right);
	//media放尾部
	swap(array[media_index],array[right]);
	int i = left;
	int j = right - 1;
	while (i<j)
	{
		while (array[i] < media)
			i++;
		while (array[j] >= media)
			j--;
		if (i < j)
			swap(array[i],array[j]);
	}
	swap(array[right],array[i]);
	//三种情况
	//第k小数在media右边
	if (i-left < k - 1)//第k大的数的下标应为k-1
		return SelectK(array,i + 1,k - (i -left+ 1),interval);
	//第k小数在media左边
	if (i-left>k - 1)
		return SelectK(array,i - 1,k,interval);
	//第k小数即为media
	return media;
}



void main()
{
	int array[] = { 0,45,78,55,47,4,1,2,7,8,96,36,45 };
	int arraysize = sizeof(array) / sizeof(int);//数组长度
	int k = 3;//找第k大的数
	int interval = 5;//分段间隔

	int result = SelectK(array,arraysize - 1,interval);
	cout << "第" << k << "小的数为:" << result << endl;
	
	//打印数组，便于检查
	cout << "数组排序后：" << endl;
	Insert_Sort(array,arraysize - 1);
	for (int i = 0; i < arraysize; i++)
		cout << array[i] << ' ';
	cout << endl;
	system("pause");
}