找任意第k个小的元素
#include <stdio.h>
#include <stdlib.h>
#include <ctime>
#include <iostream>
using namespace std; template <class Type>
void Swap(Type &x,Type &y); inline int Random(int x, int y); template <class Type>
void BubbleSort(Type a[],int p,int r); template <class Type>
int Partition(Type a[],int p,int r,Type x); template <class Type>
Type Select(Type a[],int p,int r,int k); int main()
{
//初始化数组
int a[]; //必须放在循环体外面
srand((unsigned)time()); for(int i=; i<; i++)
{
a[i] = Random(,);
cout<<"a["<<i<<"]:"<<a[i]<<" ";
}
cout<<endl; cout<<"第83小元素是"<<Select(a,,,)<<endl; //重新排序，对比结果
BubbleSort(a,,); for(int i=; i<; i++)
{
cout<<"a["<<i<<"]:"<<a[i]<<" ";
}
cout<<endl;
} template <class Type>
void Swap(Type &x,Type &y)
{
Type temp = x;
x = y;
y = temp;
} inline int Random(int x, int y)
{
int ran_num = rand() % (y - x) + x;
return ran_num;
} //冒泡排序
template <class Type>
void BubbleSort(Type a[],int p,int r)
{
//记录一次遍历中是否有元素的交换
bool exchange;
for(int i=p; i<=r-;i++)
{
exchange = false ;
for(int j=i+; j<=r; j++)
{
if(a[j]<a[j-])
{
Swap(a[j],a[j-]);
exchange = true;
}
}
//如果这次遍历没有元素的交换,那么排序结束
if(false == exchange)
{
break ;
}
}
} template <class Type>
int Partition(Type a[],int p,int r,Type x)
{
int i = p-,j = r + ; while(true)
{
while(a[++i]<x && i<r);
while(a[--j]>x);
if(i>=j)
{
break;
}
Swap(a[i],a[j]);
}
return j;
} template <class Type>
Type Select(Type a[],int p,int r,int k)
{
if(r-p<)
{
BubbleSort(a,p,r);
return a[p+k-];
}
//(r-p-4)/5相当于n-5
for(int i=; i<=(r-p-)/; i++)
{
//将元素每5个分成一组，分别排序，并将该组中位数与a[p+i]交换位置
//使所有中位数都排列在数组最左侧，以便进一步查找中位数的中位数
BubbleSort(a,p+*i,p+*i+);
Swap(a[p+*i+],a[p+i]);
}
//找中位数的中位数
Type x = Select(a,p,p+(r-p-)/,(r-p-)/);
int i = Partition(a,p,r,x);
int j = i-p+;
if(k<=j)
{
return Select(a,p,i,k);
}
else
{
return Select(a,i+,r,k-j);
}
}
h