上兩片第歸算法學(xué)習(xí)：

1）遞歸算法之分而治之策略
2）遞歸算法之歸并排序

　　上一篇學(xué)習(xí)中介紹了了遞歸算法在排序中的一個應(yīng)用：歸并排序，在排序算法中還有一種算法用到了遞歸，那就是快速排序，快速排序也是一種利用了分而治之策略的算法，它由C.A.R發(fā)明，它依據(jù)中心元素的值，利用一系列遞歸調(diào)用將數(shù)據(jù)表劃分成越來越小的子表。在每一步調(diào)用中，經(jīng)過多次的交換，最終為中心元素找到最終的位置。與歸并算法不同，快速排序是就地排序，而歸并排序需要把元素在臨時向量中拷貝，下面通過對以下向量進行排序來理解和加深快速排序算法的步驟：

v={800,150,300,650,550,500,400,350,450,400,900};

　　利用快速排序算法對此數(shù)據(jù)表進行排序的第0級劃分過程如下： 向量v的索引范圍為:[first,last) = [0,10),則中心點的索引為mid = (0+10)/2=5,中心點的值為v[5] = 500

　　快速排序算法的第一次劃分的目的就是將向量v依據(jù)v[5]的值劃分成兩個子表subList1和subList2，其中subList1中的值都小于v[5],而subList2中的值都大于v[5],我們將subList1稱為左子表，subList2稱為右子表，并且確定v[5]的最終位置

下面就是實現(xiàn)這一目的需要我們作出的工作步驟：

1）首先將中心元素與起始位置的元素進行交換。

2）分別掃描左子表和右子表，左子表掃描起始位置為 first+1, 右子表從last-1開始。左子表從左向右掃描掃描，右子表從右向左掃描。直到左子表掃描位置大于或者等于右子表掃描位置時候結(jié)束。

在第一個步驟中，得到如下的數(shù)據(jù)表

500  150  300 650 550 800 400 350 450 400 

　　而此時的左子表掃描位置處于索引1處，右子表掃描位置處于索引9處，先從左子表掃描，直到找到數(shù)據(jù)值大于中間值500的位置停止掃描，然后掃描右子表，直到找到數(shù)據(jù)值小于中間值500并且右子表的掃描位置（scanDown)要小于左子表開始位置，防止數(shù)據(jù)溢出。找到之后，交換左子表與右子表中中掃描位置的元素，圖示如下：

在交換v[3](650>500)與v[8](450<500)后，繼續(xù)掃描左子表和右子表，如圖

　　直到滿足條件scanUp>=scanDown，然后scanDown所在位置就是中心元素500的最終位置，交換v[0]與v[scanDown)=v[5],第一次劃分級別的最終結(jié)果數(shù)據(jù)集為：400,150,300,450,350,500,800,550,650,900,此時得到的左子表為:400,150,300,450,350,右子表為:800,550,650,900

　　下一個劃分級別是處理上一級別產(chǎn)生的子表，按照相同的處理方法分別處理左子表和右子表，左子表索引位置[0,5),右子表索引位置[6,10),按照上面的處理步驟處理左子表(400,150,300,450,350)得到的最終結(jié)果為:150,300,400,450,350 右子表最終處理結(jié)果為:550,650,800,900 在處理結(jié)果中300與650分別是中心值，他們現(xiàn)在的位置就是最終位置

　　在接下來的處理中，總是處理上一步驟中留下的子表，當(dāng)子表數(shù)目<=1的時候就不用處理子表了，而子表有兩個元素的時候，比較大小，然后交換兩元素位置即可。

大于2個元素的子表都和上面的處理步驟一樣，我們將上面的處理過程編寫出一個函數(shù)

private int PivotIndex(int[] v, int first, int last)，那么快速排序算法就是對此函數(shù)的遞歸調(diào)用

/// <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">結(jié)束位置</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);
 }
} 

　　快速排序因為每次劃分都能將中心值元素找到最終的位置，并且左邊值都小于中心值，右邊都大于中心值，它的時間復(fù)雜度平均和歸并算法一致為O(nlog2n);

　　任何一種基于比較的排序算法的時間復(fù)雜度不可能小于這個數(shù)，除非不使用比較的方法進行排序。

算法程序：http://xiazai.jb51.net/201606/yuanma/QuickSort(jb51.net).rar

最新評論