C#遞歸算法之疾速排序。本站提示廣大學習愛好者：（C#遞歸算法之疾速排序）文章只能為提供參考，不一定能成為您想要的結果。以下是C#遞歸算法之疾速排序正文
上兩片第歸算法進修：
1）遞歸算法之分而治之戰略
2）遞歸算法之合並排序
上一篇進修中引見了了遞歸算法在排序中的一個運用：合並排序，在排序算法中還有一種算法用到了遞歸，那就是疾速排序，疾速排序也是一種應用了分而治之戰略的算法，它由C.A.R創造，它根據中間元素的值，應用一系列遞歸挪用將數據表劃分紅愈來愈小的子表。在每步驟用中，經由屢次的交流，終究為中間元素找到終究的地位。與合並算法分歧，疾速排序是當場排序，而合並排序須要把元素在暫時向量中拷貝，上面經由過程對以下向量停止排序來懂得和加深疾速排序算法的步調：
v={800,150,300,650,550,500,400,350,450,400,900};
應用疾速排序算法對此數據表停止排序的第0級劃分進程以下： 向量v的索引規模為:[first,last) = [0,10),則中間點的索引為mid = (0+10)/2=5,中間點的值為v[5] = 500
疾速排序算法的第一次劃分的目標就是將向量v根據v[5]的值劃分紅兩個子表subList1和subList2，個中subList1中的值都小於v[5],而subList2中的值都年夜於v[5],我們將subList1稱為左子表，subList2稱為右子表，而且肯定v[5]的終究地位
上面就是完成這一目標須要我們作出的任務步調：
1）起首將中間元素與肇端地位的元素停止交流。
2）分離掃描左子表和右子表，左子表掃描肇端地位為 first+1, 右子表從last-1開端。左子表從左向右掃描掃描，右子表從右向左掃描。直到左子表掃描地位年夜於或許等於右子表掃描地位時刻停止。
在第一個步調中，獲得以下的數據表
500 150 300 650 550 800 400 350 450 400
而此時的左子表掃描地位處於索引1處，右子表掃描地位處於索引9處，先從左子表掃描，直到找到數據值年夜於中央值500的地位停滯掃描，然後掃描右子表，直到找到數據值小於中央值500而且右子表的掃描地位（scanDown)要小於左子表開端地位，避免數據溢出。找到以後，交流左子表與右子表中中掃描地位的元素，圖示以下：
在交流v[3](650>500)與v[8](450<500)後，持續掃描左子表和右子表，如圖
直到知足前提scanUp>=scanDown，然後scanDown地點地位就是中間元素500的終究地位，交流v[0]與v[scanDown)=v[5],第一次劃分級其余終究成果數據集為：400,150,300,450,350,500,800,550,650,900,此時獲得的左子表為:400,150,300,450,350,右子表為:800,550,650,900
下一個劃分級別是處置上一級別發生的子表，依照雷同的處置辦法分離處置左子表和右子表，左子表索引地位[0,5),右子表索引地位[6,10),依照下面的處置步調處置左子表(400,150,300,450,350)獲得的終究成果為:150,300,400,450,350 右子表終究處置成果為:550,650,800,900 在處置成果中300與650分離是中間值，他們如今的地位就是終究地位
在接上去的處置中，老是處置上一步調中留下的子表，當子表數量<=1的時刻就不消處置子表了，而子表有兩個元素的時刻，比擬年夜小，然後交流兩元素地位便可。
年夜於2個元素的子表都和下面的處置步調一樣，我們將下面的處置進程編寫出一個函數
private int PivotIndex(int[] v, int first, int last)，那末疾速排序算法就是對此函數的遞歸挪用
/// <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;
}
public void Sort(int[] v, int first, int last)
{
if (last - first <= 1)
{
return;
}
if (last - first == 2)
{
//有兩個元素的子表
if (v[first] > v[last - 1])
{
Swrap(v, first, last - 1);
}
return;
}
else
{
int pivotIndex = PivotIndex(v, first, last);
Sort(v, first, pivotIndex);
Sort(v, pivotIndex + 1, last);
}
}
疾速排序由於每次劃分都能將中間值元素找到終究的地位，而且右邊值都小於中間值，左邊都年夜於中間值，它的時光龐雜度均勻和合並算法分歧為O(nlog2n);
任何一種基於比擬的排序算法的時光龐雜度弗成能小於這個數，除非不應用比擬的辦法停止排序。
算法法式：http://xiazai.jb51.net/201606/yuanma/QuickSort(jb51.net).rar
