第九章中位数と順序統計学の「第i小要素の最悪の状況を探す線形時間の選択最悪の運行時間はO(n)アルゴリズムである」

#include <iostream>
#include <string.h>
using namespace std;


//            
void InsertionSort(int *a,int p,int r,int &mid)
{
	int i;
	for(int j=p+1;j<=r;j++)
	{
        i=j-1;
		int key=a[j];
		while(i>=p && a[i]>key)
		{
			a[i+1]=a[i];
			i--;
		}
		a[i+1]=key;
	}
	int d=r-p+1;
	if(d%2==0)
	{
		d=d/2-1;
	}
	else
	{
		d=d/2;
	}
	//cout<<d;
	mid=a[d+p];
}

//    a    ，  x 
void Select(int *a,int p,int r,int &x)
{
	if(p==r)
	{
		x=a[p];
		return;
	}
	int n=r-p+1;
	int m=0;
	if(n%5==0)
	{
		m=n/5;
	}
	else
	{
		m=n/5+1;
	}
	
	//              ...，         ，              ，    b 
    int b[m];
	int i=p;
	for(int j=0;j<m;j++)
	{
		int mid;
		if(i+4<=r)
		{
			InsertionSort(a,i,i+4,mid);
			b[j]=mid;
			i+=5;
		}
		else
		{
			InsertionSort(a,i,r,mid);
			b[j]=mid;
		}
		//cout<<"i="<<i<<" mid="<<mid<<" j="<<j<<" m="<<m<<" r="<<r;system("pause");
	}
	
	//            b，    Select，     x
	Select(b,0,m-1,x);
}

//     x，   a     
int Partition(int *a,int p,int r,int x)
{
	int index=-1;
	for(int i=p;i<=r;i++)
	{
		if(a[i]==x)
		{
			index=i;//cout<<i;system("pause");
			break;
		}
	}
	if(index==-1)
	{
	    cout<<"error"<<endl;
		exit(1);
	}
	int temp=a[index];
	a[index]=a[r];
	a[r]=temp;
	
	int i=p-1;
	for(int j=p;j<r;j++)
	{
		if(a[j]<=x)
		{
			i++;
			int tmp=a[i];
			a[i]=a[j];
			a[j]=tmp;
		}
	}
	int pivot=a[r];
	a[r]=a[i+1];
	a[i+1]=pivot;
	
	return i+1;
}

//   i   
void find(int *a,int p,int r,int i,int &result)
{
	int x;
	Select(a,p,r,x);
	
	// x   ，   a    
	int q=Partition(a,p,r,x);
	int k=q-p+1;
	if(k==i)
	{
		result=a[q];
	}
	else if(k>i)
	{
		find(a,p,q-1,i,result);
	}
	else
	{
		find(a,q+1,r,i-k,result);
	}
}

void Output(int *a,int n)
{
     for(int i=0;i<n;i++)
     {
         printf("%d ",a[i]);
     }
     cout<<endl;
}

int main()
{
    int n=11;
    int a[n];
    srand((unsigned int)time(NULL));
    for(int i=0;i<n;i++)
    {
         a[i]=rand()%n;
    }
    Output(a,n);
	int result=-1;
	int i;
	while(1)
	{
    	cout<<"        i ：i="; 
    	cin>>i;
        find(a,0,n-1,i,result);
    	cout<<"i="<<i<<" result="<<result<<endl;
     }
    //Output(a,n);
    system("pause");
    return 0;
}