C#遞歸算法尋覓數組中第K年夜的數。本站提示廣大學習愛好者：（C#遞歸算法尋覓數組中第K年夜的數）文章只能為提供參考，不一定能成為您想要的結果。以下是C#遞歸算法尋覓數組中第K年夜的數正文
1.概述
國人素來愛好論資排輩的,每一個人都想當老邁,其實當不成,當個老二,老三,老K也不錯,您必定看過如許的爭辯: 兩小我打罵,一小我異常強勢,別的一個忍耐不住了便說:"你算老幾呀?",上面就經由過程這篇文章就是要處理找出老幾的成績!
2.運用場景
在向量V[first,last)中查找出第K年夜元素的值
3.剖析
假如應用排序算法將向量V排好序，那末第K年夜元素就是索引為v.length-k的元素了，如許能處理成績，但效力不高，由於這相當於為了消滅仇敵一個小隊而動用了我們三軍的力氣，得失相當，回憶疾速排序中的分表，每次都將目的向量分為兩個子表，左子表中全體小於中央元素v[mid]，左邊都年夜於中央元素v[mid]，如許便可以減小了查找規模，由於我可以只查找左子表或許右子表就可以找到目的元素了。以下圖所示，我們可以將向量 v劃分紅以下
Left(<=KLargest) KLargest Right(>=KLargest)
依照如許的思緒，我們仍應用疾速排序中的分表戰略，起首將向量V從中央地位離開，分紅左和右，分好後，中央值的索引假如恰好等於K，就找到了，不然假如中央元素索引年夜於K，則在左子表中持續查找，疏忽右子表，假如中央值索引小於K，則在右子表中持續查找，如斯輪回來去。
疾速排序中的子表劃分函數為：
/// <summary>
/// 交流地位
/// </summary>
/// <param name="v"></param>
/// <param name="index1"></param>
/// <param name="index2"></param>
private void Swrap(int[] v, int index1, int index2)
{
int temp = v[index1];
v[index1] = v[index2];
v[index2] = temp;
}
/// <summary>
/// 將向量V中索引{first,last)劃分紅兩個左子表和右子表
/// </summary>
/// <param name="v">向量V</param>
/// <param name="first">開端地位</param>
/// <param name="last">停止地位</param>
private int PivotIndex(int[] v, int first, int last)
{
if (last == first)
{
return last;
}
if (last - first == 1)
{
return first;
}
int mid = (first + last) / 2;
int midVal = v[mid];
//交流v[first]和v[mid]
Swrap(v, first, mid);
int scanA = first + 1;
int scanB = last - 1;
for (; ; )
{
while (scanA <= scanB && v[scanA] < midVal)
{
scanA++;
}
while (scanB > first && midVal <= v[scanB])
{
scanB--;
}
if (scanA >= scanB)
{
break;
}
Swrap(v, scanA, scanB);
scanA++;
scanB--;
}
Swrap(v, first, scanB);
return scanB;
}
設計一個函數,FindKLargest(int[] v,int first,int last,int k);這個函數包含四個參數：向量V,開端地位first,停止地位last,和第k年夜中的K,則該函數為:
挪用FindKLargest後，由於數組是從小到年夜排序，所以第K年夜元素的值為V[v.Length-k];
void FindKLargest(int[] v, int first, int last, int k)
{
//表現分表中值的索引
int index = 0;
index = PivotIndex(v, first, last);
if (index == k)
{
//找到了K年夜
return;
}
if (index > k)
{
//只在左子表中查找
FindKLargest(v, first, index, k);
}
else
{
//只在右子表中查找
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
5.結論
應用遞歸算法可以將比擬龐雜的成績劃分為愈來愈小的小成績，如許可以或許使龐雜成績簡略化，如許的思緒在體系設計和架構中異樣有著相當主要的感化，一個好的架構師，面臨龐雜的成績，能伙頭解牛般化腐敗為奇異，而壞的卻常常拔苗助長，他們的專長是簡略成績龐雜化。
6.項目文件
http://xiazai.jb51.net/201606/yuanma/FindK(jb51.net).rar
