快速排序算法C#實現

最近想把幾大經典的排序算法系統的整理過一遍，寫下筆記，算是復習吧！！

1、快速排序。

　　快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列——來自百度百科。

　　假設我們要對數組Array 6 ?7 ?2 ?1 ?9 ?4 ?3? 10 ?5? 8排序，先在序列中找任意一個數（此例取第一個）作為基準數（就是一界限，大于此數放序列的右邊小于或等于放左邊）

下標	0	1	2	3	4	5	6	7	8	9
值	6	7	2	1	9	4	3	10	5	8

初始化:i=0,j=9,基準數 X=6

從j開始往前找一個小于或等于X的數，

當j=8時，Array [0] = Array[8]（i++），數組變為:

下標	0	1	2	3	4	5	6	7	8	9
值	5	7	2	1	9	4	3	10	5	8

從i開始往后找一個比X大的數，

當i=1時，Array[8]= Array[1](j--),數組變為:

下標	0	1	2	3	4	5	6	7	8	9
值	5	7	2	1	9	4	3	10	7	8

從j開始往前找一個小于或等于X的數，

當j=6時，Array[1]= Array[6](i++),數組變為:

下標	0	1	2	3	4	5	6	7	8	9
值	5	3	2	1	9	4	3	10	7	8

從i開始往后找一個大于X的數,

當i=4時，Array[6]= Array[4] (j--),數組變為:

下標	0	1	2	3	4	5	6	7	8	9
值	5	3	2	1	9	4	9	10	7	8

從j開始往前找一個小于或等于X的數,

當j=5時，Array[4]= Array [5] (i++),數組變為:

下標	0	1	2	3	4	5	6	7	8	9
值	5	3	2	1	4	4	9	10	7	8

當i==j==5時，停止循環，將基準數填入，Array[5]=X,數組變為:

下標	0	1	2	3	4	5	6	7	8	9
值	5	3	2	1	4	6	9	10	7	8

此次循環結束后，可以看出，Array[5]左邊的數據都比它小，右邊的數都比它大，因此再對Array [0…4] 和Array [6…9]重復上述步驟即可（遞歸調用）。

C#代碼實現:

1 static void Main(string[] args) 2 { 3 int[] array = new[] {6, 7, 2, 1, 9, 4, 3, 10, 5, 8}; 4 Sort(array, 0, array.Length - 1); 5 foreach (int item in array) 6 { 7 Console.Write(item + " "); 8 } 9 Console.ReadLine(); 10 } 　　　　 /// <summary>/// 排序/// </summary>/// <param name="array">要排序的數組</param>/// <param name="low">下標開始位置，向右查找</param>/// <param name="high">下標開始位置，向左查找</param>public static void Sort(int[] array, int low, int high){if (low >= high)return;//完成一次單元排序int index = SortUnit(array, low, high);//遞歸調用，對左邊部分的數組進行單元排序Sort(array, low, index - 1);//遞歸調用，對右邊部分的數組進行單元排序Sort(array, index + 1, high);}/// <summary>/// 單元排序/// </summary>/// <param name="array">要排序的數組</param>/// <param name="low">下標開始位置，向右查找</param>/// <param name="high">下標開始位置，向右查找</param>/// <returns>每次單元排序的停止下標</returns>public static int SortUnit(int[] array, int low, int high){int key = array[low];//基準數while (low < high){//從high往前找小于或等于key的值while (low < high && array[high] > key)high--;//比key小開等的放左邊array[low] = array[high];//從low往后找大于key的值while (low < high && array[low] <= key)low++;//比key大的放右邊array[high] = array[low];}//結束循環時，此時low等于high，左邊都小于或等于key，右邊都大于key。將key放在游標當前位置。 array[low] = key;return high;}

?

posted on 2017-01-11 09:42 我愛廣州小蠻腰 閱讀(...) 評論(...) 編輯 收藏

轉載于:https://www.cnblogs.com/homeforhzw/p/6272439.html

總結

以上是生活随笔為你收集整理的快速排序算法C#实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。