一.經典快排思想
前提條件：給定一個無序數組arr
二.通過荷蘭國旗問題改進快排
什么是荷蘭國旗問題？
已知一個整形數組arr，和一個整數num，請把小于num的數放在數組的左邊，等于num的數放在數組的中間，大于num的數放在數組的右邊。
解決思路：
遍歷數組
附上代碼：
public static void NetherlandsFlag(int[] arr, int L, int R, int num) { int i = L; int p1 = L-1; int p2 = R+1; //終止條件：當前數的位置在大于區(qū)的前一個 while(i < p2) { if(arr[i] < num) { //當前數比num小，放左邊，i位置上的數和L上的數進行交換，并且i++，L++ swap(arr, i++, ++p1); } else if(arr[i] == num) { //當前數和num相等，i++ i++; } else { //當前數比num大，放右邊，i位置上的數和R上的數進行交換，并且i++，R-- swap(arr, i, --p2); } }}我們可以發(fā)現，荷蘭國旗問題和經典快排不同的就只是將<=num改為了< num和=num兩部分，借用這個思想使得原來每次只可以讓一個數找到正確的位置改進為了每次至少讓一個數找到位置。
三.在這基礎上將其改為隨機快排
隨機快排改進的地方只是在選取數的時候，將每次都選取最后位置的數改為選取隨機的一個數作為num，這樣做的好處是什么呢？
1.選取最后一個數：如果是一個已經排好序的數組，每次找到位置之后，左邊是要進行排序的部分，數組長度是原長度-1，它的時間復雜度就是O(N^2)；如果每次找到的數都是中間的位置，它的時間復雜度就只有O(logN)
2.然而以隨機數作為選取的標準num的時候，因為是隨機的，就只能通過數學期望去計算它的時間復雜度，時間復雜度是O(logN)
下面附上最終的快排代碼及注釋
/* * swap(int[] arr, int i, int j);是將arr數組的i和j位置上的數交換的方法 */public static void quickSort(int[] arr) { // 如果為空或長度為1不需要排序，直接返回 if(arr == null || arr.length < 2) return; else quickSort(arr, 0, arr.length - 1);}// 遞歸排序public static void quickSort(int[] arr, int L, int R) { if(L < R) { /* * 隨機快排的隨機就在這 * 是隨機選取了一個數，和 R 進行了交換，然后使用這個數作為num， * 所以每次選取的num是隨機的， * 在計算時間復雜度時，是沒有最優(yōu)最差情況的 * 而是通過一個長期的數學期望計算的，結果是O(N*logN) */ swap(arr, L + (int) (Math.random() * (R - L + 1)), R); int[] border = partition(arr, L, R); // 小于區(qū)和大于區(qū)進行遞歸 quickSort(arr, L, border[0] - 1); quickSort(arr, border[1] + 1, R); }}// 將給定數組劃分為小于區(qū)、等于區(qū)和大于區(qū)public static int[] partition(int[] arr, int L, int R) { int num = arr[R]; int less = L - 1; int more = R + 1; int curr = L; // 分為小于區(qū)等于區(qū)和大于區(qū) while(curr < more) { if(arr[curr] < num) { swap(arr, curr++, ++less); } else if(arr[curr] > num) { swap(arr, curr, --more); } else { curr++; } } //返回等于區(qū)的左右邊界的下標，通過下標確定小于區(qū)和大于區(qū)遞歸時的參數 return new int[] {less + 1, more - 1};}總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對VeVb武林網的支持。
新聞熱點
疑難解答
圖片精選
