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

1） 遞歸算法學(xué)習(xí)系列一（分而治之策略）
2） 遞歸算法學(xué)習(xí)系列二（歸并排序） 

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

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

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

快速排序算法的第一次劃分的目的就是將向量v依據(jù)v[5]的值劃分成兩個(gè)子表subList1和subList2，其中subList1中的值都小于v[5],而subList2中的值都大于v[5],我們將subList1稱為左子表，subList2稱為右子表，并且確定v[5]的最終位置：下面就是實(shí)現(xiàn)這一目的需要我們作出的工作步驟：

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

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

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

500  150  300 650 550 800 400 350 450 400  ,而此時(shí)的左子表掃描位置處于索引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],第一次劃分級(jí)別的最終結(jié)果數(shù)據(jù)集為：400,150,300,450,350,500,800,550,650,900,此時(shí)得到的左子表為:400,150,300,450,350,右子表為:800,550,650,900

下一個(gè)劃分級(jí)別是處理上一級(jí)別產(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)在的位置就是最終位置

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

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

private int PivotIndex(int[] v, int first, int last)，那么快速排序算法就是對(duì)此函數(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)劃分成兩個(gè)左子表和右子表
       /// </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)
           {
               //有兩個(gè)元素的子表
               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);
           }
       } 

      快速排序因?yàn)槊看蝿澐侄寄軐⒅行闹翟卣业阶罱K的位置，并且左邊值都小于中心值，右邊都大于中心值，它的時(shí)間復(fù)雜度平均和歸并算法一致為O(nlog2n);

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

算法程序：/Files/jillzhang/QuickSort.rar


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

1） 遞歸算法學(xué)習(xí)系列一（分而治之策略）
2） 遞歸算法學(xué)習(xí)系列二（歸并排序）

-------------------------------------------------------
人老了，腦袋不好用了，偶爾用算法來(lái)練練腦子，可以防止早衰。呵呵
                                                        jillzhang jillzhang@126.com