黑馬程序員-快速排序

快速排序

　　快速排序時所有排序算法中最高效的一種。

　　它采用了分治的思想：先保證列表的前半部分都小于后半部分，然后分別對前半部分和后半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是它高效的原因。因為在排序算法中，算法的高效與否與列表中數字間的比較次數有直接的關系，而“保證列表的前半部分都小于后半部分”就使得前半部分的任何一個數從此以后都不再跟后半部分的數進行比較了，大大減少了數字間不必要的比較。

　　快速排序（QuickSort）是對冒泡排序的一種改進。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

　　設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用數組的第一個數）作為關鍵數據，然后將所有比它小的數都放到它前面，所有比它大的數都放到它后面，這個過程成為 一趟快速排序 。值得注意的是，快速排序不是一種穩定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結束時產生變動。

　　一趟快速排序的算法是：

　　1）設置兩個變量i、j，排序開始的時候：i=0，j=N-1；

　　2）以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；

　　3）從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個小于key的值A[j]，將A[j]賦給A[i]；

　　4）從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個大于key的值A[i]，將A[i]賦給A[j]；

　　5）重復地3、4步，知道i=j；（3,4步中，沒找到符合條件的值，即3中A[j]不小于key，4中A[j]不大于key的時候改變j、i的值，使得j=j-1，i=i+1，直到找到為止。找到符合條件的值，進行交換的時候i，j指針位置不變。另外，i==j 這一過程一定正好是 i+ 或 j- 完成的時候，此時令循環結束）。

　　如果i和j沒有碰頭的話，就遞加i找大的，還沒有，就再遞減j找小的，如此反復，不斷循環。注意判斷和尋找是同時進行的。

namespaceQuickSort

{

classPRogram

{

staticvoidMain(string[]args)

{

//

int[]array={49,38,65,97,76,13,27};

sort(array,0,array.Length-1);

Console.WriteLine(string.Join(",",array));

Console.ReadLine();

}

///<summary>

///一次排序單元，完成此方法，key左邊都比key小，key右邊都比key大。

///</summary>

///<paramname="array">排序數組</param>

///<paramname="low">排序起始位置</param>

///<paramname="high">排序結束位置</param>

///<returns>單元排序后的數組</returns>

privatestaticintsortUnit(int[]array,intlow,inthigh)

{

intkey=array[low];

while(low<high)

{//從后向前搜索比key小的值

while(array[high]>=key&&high>low)

--high;//比key小的放左邊

array[low]=array[high];//從前向后搜索比key大的值，比key大的放右邊

while(array[low]<=key&&high>low)

++low;//比key大的放右邊

array[high]=array[low];

}//左邊都比key小，右邊都比key大。//將key放在游標當前位置。//此時low等于high

array[low]=key;

//Console.WriteLine(string.Join(",",array));

returnhigh;

}

///<summary>

///快速排序

///</summary>

///<paramname="array"></param>

///<paramname="low"></param>

///<paramname="high"></param>

publicstaticvoidsort(int[]array,intlow,inthigh)

{

if(low>=high)

{

return;

}

else

{

intindex=sortUnit(array,low,high);//完成一次單元排序

sort(array,low,index-1);//對左邊單元進行排序

sort(array,index+1,high);//對右邊單元進行排序

}

}

}

}