【算法导论】第$i$小的元素

时间复杂度：$O(n)$.

基本思想：和快速排序的思想相似，也是对数组进行递归划分，但是有所差别的是，快速排序会递归处理划分的两边，而随机化的选择算法只选择一边。

具体步骤为:首先，随机选择一个数组元素作为主元，从而将数组分解为两个子数组，并得到主元在元素中的位置$q$，假设较小子数组元素的个数为$k-1$；然后比较$i$与$k$的大小，来确定下一次递归选择哪一边的子数组（注意$i$的值的改变情况）；最后，当$i==k$时，就求得了第$i$小的元素。具体实例见图解：

具体的程序实现如下：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int Partition(int*arrayA,int n,int p,int r);
int RandomPartition(int* arrayA,int n,int p,int r);
int RandomSelect(int* arrayA,int n,int p,int r,int i);

void main()
{
	int arrayA[8]={2,1,3,4,8,6,7,5};
	int n=sizeof(arrayA)/sizeof(int);
	int p=0;
	int r=7;
	int i=4;
	int result=0;
	result=RandomSelect(arrayA,n,p,r,i);
	printf("数组中第%d小的数是%d\n",i,result);

}


/**************************************************\
函数功能：将原数组分成全大于和全小于x的两个子数组
输入：原始数组、要对数组进行操作的起始和结束下标p、r
	  即只对数组指定部分进行操作。
输出：x在数组中的位置
\**************************************************/
int Partition(int*arrayA,int n,int p,int r)
{
	int x=arrayA[r];//使主元x选为数组选中部分的最后一个元素
	int i=p-1;
	int temp=0;
	for(int j=p;j<=r-1;j++)
	{
		if(arrayA[j]<=x)
		{
			i++;
			temp=arrayA[i];
			arrayA[i]=arrayA[j];
			arrayA[j]=temp;
		}
	}
	temp=arrayA[i+1];
	arrayA[i+1]=arrayA[r];
	arrayA[r]=temp;

	return i+1;//最终主元的位置
}


/**************************************************\
函数功能：用随机数确定主元
输入：原始数组、要对数组进行操作的起始和结束下标p、r
	  即只对数组指定部分进行操作
输出：x在数组中的位置
\**************************************************/
int RandomPartition(int* arrayA,int n,int p,int r)
{
	int suiji=0;
	srand(time(0));
	suiji=rand()%(r-p)+p;//产生大于等于p,小于r的随机数
  printf("suiji=%d\n",suiji);
	int temp=0;
	temp=arrayA[r]; //使主元由随机数确定
	arrayA[r]=arrayA[suiji];
	arrayA[suiji]=temp;

	return Partition(arrayA,n,p,r);
}

/**************************************************\
函数功能：找出数组中第i小的数
输入：原始数组、要对数组进行操作的起始和结束下标p、r
	  即只对数组指定部分进行操作
输出：x在数组中的位置
\**************************************************/
int RandomSelect(int* arrayA,int n,int p,int r,int i)
{
	int q=0;
	
	if(p==r)
		return arrayA[p];

	for(int j=p;j<=r;j++)
		printf("%d ",arrayA[j]);
	printf("\n");
	q=RandomPartition(arrayA,n,p,r);//主元的位置
	printf("gaihou:\n");
	for(int j=p;j<=r;j++)
		printf("%d ",arrayA[j]);
	printf("\n\n");

	int k=q-p+1;
	if(i==k)
		return arrayA[q];
	else if(i<k)
		return RandomSelect(arrayA,n,p,q-1,i);
	else
		return RandomSelect(arrayA,n,q+1,r,i-k);

}