從事net工作兩年當初學到的數據結構算法一直沒有在實際工作中用到近日閒來無事突發奇想要溫習一下簡單的數據結構算法今日用了一個下午的時間完成了排序中的快速排序以此作為入駐博客園的首篇隨筆!思想向後是否將其放到首頁?最後還是厚著臉皮大著膽子決定放但始終戰戰兢兢心中不免忐忑雖然內容很簡單但確實我是在用心寫希望它能夠被人看到好了閒話少敘在下已做好挨罵准備!如果管理員覺得此文不妥就請隨意處置吧呵呵
快速排序 是采用遞歸的方式對待排序的數列進行若干次的操作每次操作使得被操作的數列部分以某個元素為分界值分成兩部分一部分小於該分界值另一部分大於該分界值該分界值一般被稱為樞軸
以數列 為例詳細描述執行一趟快速排序的算法:
選擇待排序數列的樞軸一般以數列的首元素作為樞軸此數列中我們選擇首元素作為樞軸nPivot =
設定兩個指針 i 和 j 分別指向數列的首元素和尾元素 i 指向首元素 j 指向尾元素示意圖如下:
向前移動尾指針 j 使其指向從數列尾部算起首個小於樞軸(即)的元素並將該元素置換到頭指針 i 指向的位置_nArray[i] =_nArray[j]示意圖如下:
首次執行該操作時 i 指針指向處的值實際上就是樞軸的值此處的操作可以理解為 i 指針指向處的值已在之前被置換到樞軸中此時 i 指向處已經是一個空位在此時用找到的小於樞軸的元素填在此處
向後移動頭指針 i 使其指向從數列頭部算起首個大於樞軸(即)的元素並將該元素置換到尾指針 j 指向的位置_nArray[j] =_nArray[i]示意圖如下:
此處同樣可以理解為 j 指針指向處的值已在上一步操作中置換了出去 j 處已是一個空位
如此重復執行步驟和步驟直至 i==j 時結束該循環
退出了該循環後 i 與 j 必定指向同一位置在該位置的前部元素其值均小於樞軸而在該位置的後部元素其值均大於樞軸顯而易見此時 i 和 j 同時指向的位置就應該是樞軸的新家_nArray[i]=nPivot如下圖:
至此一趟排序結束待排序數列的首元素將該數列分成了比其小和比其大的兩部分如下圖:
接著我們對這一大一小兩部分子數列執行相同的排序操作
如此遞歸直至對整個數列完成排序操作
以下是c#實現代碼:
using System;
public class Sort
{
public class Quick_Sort
{
private static int QuickSort_Once(int[] _pnArray int _pnLow int _pnHigh)
{
int nPivot = _pnArray[_pnLow]; //將首元素作為樞軸
int i = _pnLow j = _pnHigh;
while (i < j)
{
//從右到左尋找首個小於nPivot的元素
while (_pnArray[j] >= nPivot && i<j) j;
//執行到此j已指向從右端起首個小於nPivot的元素
//執行替換
_pnArray[i] = _pnArray[j];
//從左到右尋找首個大於nPivot的元素
while (_pnArray[i] <= nPivot && i<j) i++;
//執行到此i已指向從左端起首個大於nPivot的元素
//執行替換
_pnArray[j] = _pnArray[i];
}
//推出while循環執行至此必定是i=j的情況
//i(或j)指向的即是樞軸的位置定位該趟排序的樞軸並將該位置返回
_pnArray[i] = nPivot;
return i;
}
private static void QuickSort(int[] _pnArray int _pnLow int _pnHigh)
{
if (_pnLow >= _pnHigh) return;
int _nPivotIndex = QuickSort_Once(_pnArray _pnLow _pnHigh);
//對樞軸的左端進行排序
QuickSort(_pnArray _pnLow _nPivotIndex);
//對樞軸的右端進行排序
QuickSort(_pnArray _nPivotIndex + _pnHigh);
}
public static void Main()
{
ConsoleWriteLine(請輸入待排序數列(以分割):);
string _s = ConsoleReadLine();
string[] _sArray = _sSplit(ToCharArray());
int _nLength = _sArrayLength;
int[] _nArray = new int[_nLength];
for (int i = ; i < _nLength; i++)
{
_nArray[i] = ConvertToInt(_sArray[i]);
}
QuickSort(_nArray _nLength);
ConsoleWriteLine(排序後的數列為:);
foreach (int _n in _nArray)
{
ConsoleWriteLine(_nToString());
}
}
}
}
From:http://tw.wingwit.com/Article/program/net/201311/15634.html
