快速排序的思想與歸并排序思想類似，都是采用分治法的思想。將一個數組A[l...r]使用快速排序可以分解為三個主要的步驟：

通過隨機算法獲得數組A中的一個下標k，將A[k]與A[r]交換。

將數組分解成左右兩個數組，左邊數組的值均小于A[r]，右邊數組的值均不小于A[r]。

分別對左右兩個數組進行排序，這兩個數組的大小均比A小。

　　通過上面的步驟，我們就可以得到快速排序的一個框架：

1 void QuickSortCore(int data[], int start, int end) 2 { 3 if (start < end) 4 { 5 int k = Partition(data, start, end); //分解成左右兩個數組 6 QuickSortCore(data, start, k - 1); //排序左邊的數組 7 QuickSortCore(data, k + 1, end); //排序右邊的數組 8 } 9 }

　　從上面的代碼中可以看出，分解A數組為左右兩個數組是快速排序算法的關鍵，這個問題本質上為：對數組A中的某個值A[k]（k為數組的下標），將小于A[k]的數存放在數組A的前面，將不小于A[k]的數存放在數組A的后面，分界線為x。

　　解決該問題的一種很直觀的方法就是先將A[k]與A[r]交換，然后用兩個下標i、j，i表示A[0~i]中的數都小于A[r]，j從0~r-1遍歷數組A。如果發現A[j]小于A[r]，則將A[i?+?1]與A[j]交換，并同時增加i和j，之所以可以這樣是因為A[i?+?1]要么不小于A[r]，要么與A[j]相同；如果A[j]不小于M，則只遞增j。最后將A[i?+?1]與A[r]交換，i+1為左右數組的分界線x。

?

1 int Partition(int data[], int start, int end) 2 { 3 int k, i, j; 4 5 k = GetRandom(start, end); //通過隨機函數獲得數組下標 6 Swap(data + k, data + end); //將作為分界線的數放到最后 7 i = start - 1; 8 for (j = start; j < end; j++) 9 if (data[j] < data[end]) //需要交換 10 { 11 i++; 12 Swap(data + i, data + j); 13 } 14 i++; 15 Swap(data + i, data + end); 16 return i; 17 }

?

?

　　解決問題的另一個方法是先將A[k]與A[l]交換，并用一個臨時變量p保存A[k]，也使用兩個下標i和j，分別初始化為l和r。開始用j從數組右邊遍歷，知道發現A[j]?<?p為止，將A[j]賦值給A[i]，并讓i加1，然后用i從數組的左邊遍歷，知道發現A[i]?>?p為止，將A[i]賦值給A[j]，并讓j減1，然后重新開始前面的遍歷，知道i?==?j為止。最后將p賦值給A[i]，此時i為左右數組的分界線x。

?

1 int Partition(int data[], int start, int end) 2 { 3 int k, i, j, temp; 4 5 k = GetRandom(start, end); 6 Swap(data + k, data + start); //將基準數放到最前面 7 temp = data[start]; //保存基準數副本 8 i = start; 9 j = end; 10 while (i < j) 11 { 12 //從右邊開始遍歷，知道遇到小于temp的 13 while (i < j && data[j] >= temp) 14 j--; 15 if (i < j) 16 data[i++] = data[j]; 17 //從左邊開始遍歷，知道遇到大于temp的 18 while (i < j && data[i] <= temp) 19 i++; 20 if (i < j) 21 data[j--] = data[i]; 22 } 23 data[i] = temp; 24 return i; 25 }

?

?

　　前面兩個方法中，第二個方法比第一個方法要好些，第二個方法用賦值替代了第一個方法中的交換。

　　代碼中的GetRandom函數是用來隨機獲得start到end之間的一個值，它可以用rand庫函數實現。

?

?

轉載于:https://www.cnblogs.com/chengxuyuancc/p/3546247.html

總結

以上是生活随笔為你收集整理的【重温经典算法之二】快速排序的全部內容，希望文章能夠幫你解決所遇到的問題。

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