概述
国人向来喜欢论资排辈
,每个人都想当老大,实在当不成,当个老 2,老 3,老K也不错,您
定看过这样争论:两个人吵架,个人非常强势,另外个忍受不住了便说:\"你算老几呀?\",下面就通过这篇文章就是要解决找出老几问题! 2.应用场景
在向量V[first,last)中查找出第K大元素
值 3.分析
如果利用排序算法将向量V排好序
那么第K大元素就是索引为v.length-k元素了这样能解决问题但效率不高
这相当于为了歼灭敌人个小队而动用了我们全军力量得不偿失回想快速排序中分表每次都将目标向量分为两个子表左子表中全部小于中间元素v[mid]右边都大于中间元素v[mid]这样就可以减小了查找范围我可以只查找左子表或者右子表就能找到目标元素了
如下图所示我们可以将向量v划分成如下 Left(<=KLargest)KLargestRight(>=KLargest)
按照这样
思路我们仍使用快速排序中分表策略首先将向量V从中间位置分开分成左和右分好后中间值索引如果恰恰等于K就找到了否则如果中间元素索引大于K则在左子表中继续查找忽略右子表如果中间值索引小于K则在右子表中继续查找如此循环往复 快速排序中
子表划分
为: /**////<summary>
///交换位置
///</summary>
///<paramname=\"v\"></param>
///<paramname=\"index1\"></param>
///<paramname=\"index2\"></param>
privatevoidSwrap(
v,index1,index2) {
temp=v[index1]; v[index1]=v[index2];
v[index2]=temp;
}
/**////<summary>
///将向量V中索引{first,last)划分成两个左子表和右子表
///</summary> [Page]
///<paramname=\"v\">向量V</param>
///<paramname=\"first\">开始位置</param>
///<paramname=\"last\">结束位置</param>
private
PivotIndex(v,first,last) {
(last
first) {
last; }
(last-first1) {
first; }
mid=(first+last)/2; midVal=v[mid]; //交换v[first]和v[mid]
Swrap(v,first,mid);
scanA=first+1; scanB=last-1; for(;;)
{
while(scanA<=scanB&&v[scanA]<midVal)
{
scanA
; [Page]}
while(scanB>first&&midVal<=v[scanB])
{
scanB--;
}
(scanA>=scanB) {
; }
Swrap(v,scanA,scanB);
scanA
; scanB--;
}
Swrap(v,first,scanB);
scanB; }
设计
个,FindKLargest(v,first,last,k);这个包括 4个参数:向量V,开始位置first,结束位置last,和第k大中K,则该为: 
FindKLargest后
是从小到大排序所以第K大元素值为V[v.Length-k]; voidFindKLargest(
v,first,last,k) {
//表示分表中值
索引 index=0; index=PivotIndex(v,first,last);
(indexk) [Page]{
//找到了K大
; }
(index>k) {
//只在左子表中查找
FindKLargest(v,first,index,k);
}
{
//只在右子表中查找
FindKLargest(v,index,last,k);
}
}
4.运行结果:
原向量:v={100,200,50,23,300,560,789,456,123,258}
first=0;last=v.Length;k=3
输出:456
最新评论