上兩片第歸算法學習：

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.VeVB.COm/201606/yuanma/QuickSort(VeVB.COm).rar