使用类快速排序的方法，找出第k小的元素。k从0开始的。使用了快速排序的部分函数快速排序 //快速选择 template<typename Comparable> Comparable& quickSelect(vector<Comparable>& a, int left, int
使用类似快速排序的方法，找出第k小的元素。
k从0开始的。
使用了快速排序的部份函数 快速排序
//快速选择
template<typename Comparable>
Comparable& quickSelect(vector<Comparable>& a,int left,int right,int k)
{
if (left + 10 <= right)//这个子数组大于10，继续使用快速排序
{
Comparable pivot = median3(a,left,right);//关键值
int i = left;//i指向左侧
int j = right - 1;//j指向右侧，现在i和j都是已比较过的了，等下是先++和--
while (true)
{
while (a[++i] < pivot) {}//小于关键值的元素是1直放在左侧，找出1个大的元素
while (pivot < a[--j]) {}//大于关键值的元素是1直放在右侧，找出1个小的元素
if (i < j)
{
swap(a[i],a[j]);//i和j还没有交汇，交换位置
}
else
{
break;//这个时候i指向的数是应当比关键值大的了
}
}
swap(a[i],a[right - 1]);//将关键值放在i的位置
if (k <= i)
{
return quickSelect(a,i - 1,k);//k在左侧的子序列中
}
else if(k > i + 1)
{
return quickSelect(a,i + 1,right,k);//k在右侧的子序列中
}
else
{
return a[i];
}
}
else
{
//使用插入排序，数组大小小于10的时候
insertionSort(a.begin() + left,a.begin() + right + 1);
return a[k];//由于排序是在全部数组里面的，所以第k位置就是所要的值
}
}
template<typename Comparable>
Comparable& quickSelect(vector<Comparable>& a,int k)
{
return quickSelect(a,a.size() ⑴,k);
}
服务热线 19970861797
