從事.net工作兩年,當初學到的數據結構算法一直沒有在實際工作中用到.近日閑來無事,突發奇想要溫習一下簡單的數據結構算法.今日,用了一個下午的時間完成了排序中的"快速排序",以此作為入駐博客園的首篇隨筆!思想向后,是否將其放到金喜正規買球?最后,還是厚著臉皮,大著膽子決定放.但始終戰戰兢兢,心中不免忐忑.雖然內容很簡單,但確實我是在用心寫,希望它能夠被人看到.好了,閑話少敘,在下已做好挨罵準備!如果管理員覺得此文不妥,就請隨意處置吧,呵呵.

      快速排序 是采用遞歸的方式對待排序的數列進行若干次的操作,每次操作使得被操作的數列部分以某個元素為分界值分成兩部分,一部分小于該分界值,另一部分大于該分界值.該分界值一般被稱為"樞軸".

 ;     以數列 14,11,25,37,9,28 為例,詳細描述執行一趟快速排序的算法:

      1,選擇待排序數列的樞軸,一般以數列的首元素作為樞軸.此數列中,我們選擇首元素14作為樞軸,nPivot = 14.

      2,設定兩個指針 i 和 j ,分別指向數列的首元素和尾元素. i 指向首元素14, j 指向尾元素28.示意圖如下:

      3,向前移動尾指針 j ,使其指向從數列尾部算起首個小于樞軸(即14)的元素,并將該元素置換到頭指針 i 指向的位置._nArray[i] =_nArray[j].示意圖如下:

      首次執行該操作時 i 指針指向處的值實際上就是樞軸的值,此處的操作可以理解為 i 指針指向處的值已在之前被置換到樞軸中,此時, i 指向處已經是一個空位,在此時用找到的小于樞軸的元素填在此處.

      4,向后移動頭指針 i ,使其指向從數列頭部算起首個大于樞軸(即14)的元素,并將該元素置換到尾指針 j 指向的位置._nArray[j] =_nArray[i].示意圖如下:

    ;  此處同樣可以理解為 j 指針指向處的值已在上一步操作中置換了出去. j 處已是一個空位.

      5,如此重復執行步驟3和步驟4,直至 i==j 時結束該循環.

      6,退出了該循環后, i 與 j 必定指向同一位置.在該位置的前部元素,其值均小于樞軸.而在該位置的后部元素,其值均大于樞軸.顯而易見,此時 i 和 j 同時指向的位置就應該是樞軸的"新家"._nArray[i]=nPivot.如下圖:

      至此,一趟排序結束.待排序數列的首元素將該數列分成了比其小和比其大的兩部分.如下圖:

      接著,我們對這一大一小兩部分子數列執行相同的排序操作.

      如此"遞歸",直至對整個數列完成排序操作. 

      以下是c#實現代碼:

 1using System;
 2
 3public class Sort
 4{
 5    public class Quick_Sort
 6    {
 7        private static int QuickSort_Once(int[] _pnArray, int _pnLow, int _pnHigh)
 8        {
 9      ;      int nPivot = _pnArray[_pnLow];      //將首元素作為樞軸
10            int i = _pnLow, j = _pnHigh;
11
12   &nbsp;      &nbsp; while (i < j)
13          &nbsp; { 
14   &nbsp;       &nbsp;    //從右到左,尋找首個小于nPivot的元素
15                ;while (_pnArray[j] >= nPivot && i<j) j--;
16    &nbsp;           //執行到此,j已指向從右端起首個小于nPivot的元素
17     ;          &nbsp;//執行替換
18    &nbsp;  &nbsp;        _pnArray[i] = _pnArray[j];
19                //從左到右,尋找首個大于nPivot的元素
20 &nbsp;        ;      while (_pnArray[i] <= nPivot && i<j) i++;
21    &nbsp;           //執行到此,i已指向從左端起首個大于nPivot的元素
22         &nbsp;      //執行替換
23                _pnArray[j] = _pnArray[i];
24  &nbsp;         }
25
26           &nbsp;//推出while循環,執行至此,必定是i=j的情況
27   &nbsp;        //i(或j)指向的即是樞軸的位置,定位該趟排序的樞軸并將該位置返回
28 &nbsp;   &nbsp;      _pnArray[i] = nPivot;
29        &nbsp;   return i;
30        }
31
32        private static void QuickSort(int[] _pnArray, int _pnLow, int _pnHigh)
33        {
34    ;        if (_pnLow >= _pnHigh) return;
35
36     &nbsp;      int _nPivotIndex = QuickSort_Once(_pnArray, _pnLow, _pnHigh);
37       &nbsp;    //對樞軸的左端進行排序
38  &nbsp;         QuickSort(_pnArray, _pnLow, _nPivotIndex-1);
39            //對樞軸的右端進行排序
40  &nbsp;         QuickSort(_pnArray, _nPivotIndex + 1,_pnHigh);
41        }
42
43        public static void Main()
44        {
45 &nbsp;         Console.WriteLine("請輸入待排序數列(以\",\"分割):");
46      &nbsp;     string _s = Console.ReadLine();
47 &nbsp;      &nbsp;   string[] _sArray = _s.Split(",".ToCharArray());
48       ;     int _nLength = _sArray.Length;
49         &nbsp;  int[] _nArray = new int[_nLength];
50       &nbsp;    for (int i = 0; i < _nLength; i++)
51&nbsp;           {
52    &nbsp;           _nArray[i] = Convert.ToInt32(_sArray[i]);
53 ;           }
54            QuickSort(_nArray, 0, _nLength-1);
55 &nbsp;          Console.WriteLine("排序后的數列為:");
56&nbsp;     ;      foreach (int _n in _nArray)
57           &nbsp;{
58                Console.WriteLine(_n.ToString());
59 &nbsp;          }
60        }
61    }
62}
63