Java編程實現快速排序及優化代碼詳解

普通快速排序

找一個基準值base，然後一趟排序後讓base左邊的數都小於base，base右邊的數都大於等於base。再分為兩個子數組的排序。如此遞歸下去。

 public class QuickSort {public static <T extends Comparable<? super T>> void sort(T[] arr) {sort(arr, 0, arr.length - 1);}public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {if (left >= right) return;int p = partition(arr, left, right);sort(arr, left, p - 1);sort(arr, p + 1, right);}private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {T base = arr[left];int j = left;for (int i = left + 1; i <= right; i++) {if (base.compareTo(arr[i]) > 0) {j++;swap(arr, j, i);}}swap(arr, left, j);return j;//返回一躺排序後基準值的下角標}public static void swap(Object[] arr, int i, int j) {if (i != j) {Object temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}private static void printArr(Object[] arr) {for (Object o : arr) {System.out.print(o);System.out.print("/t");}System.out.println();}public static void main(String args[]) {Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};printArr(arr);//3 5 1 7 2 9 8 0 4 6sort(arr);printArr(arr);//0 1 2 3 4 5 6 7 8 9}}

快速排序優化：隨機選取基準值base

在數組幾乎有序時，快排性能不好（因為每趟排序後，左右兩個子遞歸規模相差懸殊，大的那部分最後很可能會達到O(n^2)）。

解決：基準值隨機地選取，而不是每次都取第一個數。這樣就不會受“幾乎有序的數組”的干擾了。但是對“幾乎亂序的數組”的排序性能可能會稍微下降，至少多了排序前交換的那部分，亂序時這個交換沒有意義...有很多“運氣”成分..

 public class QuickSort {public static <T extends Comparable<? super T>> void sort(T[] arr) {sort(arr, 0, arr.length - 1);}public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {if (left >= right) return;int p = partition(arr, left, right);sort(arr, left, p - 1);sort(arr, p + 1, right);}private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {//排序前，先讓基準值和隨機的一個數進行交換。這樣，基準值就有隨機性。 //就不至於在數組相對有序時，導致左右兩邊的遞歸規模不一致，產生最壞時間複雜度swap(arr,left,(int)(Math.random()*(right - left + 1)+left));T base = arr[left];int j = left;for (int i = left + 1; i <= right; i++) {if (base.compareTo(arr[i]) > 0) {j++;swap(arr, j, i);}}swap(arr, left, j);return j;//返回一躺排序後，基準值的下角標}public static void swap(Object[] arr, int i, int j) {if (i != j) {Object temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}private static void printArr(Object[] arr) {for (Object o : arr) {System.out.print(o);System.out.print("/t");}System.out.println();}public static void main(String args[]) {Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};printArr(arr);//3 5 1 7 2 9 8 0 4 6sort(arr);printArr(arr);//0 1 2 3 4 5 6 7 8 9}}

快速排序繼續優化：配合著使用插入排序

快排是不斷減小問題規模來解決子問題的，需要不斷遞歸。但是遞歸到規模足夠小時，如果繼續採用這種不穩定+遞歸的方式執行下去，效率不見得會很好。

所以當問題規模較小時，近乎有序時，插入排序表現的很好。 Java自帶的Arrays.sort()裡經常能看到這樣的註釋：“Use insertion sort on tiny arrays”，“Insertion sort on smallest arrays”

 public class QuickSort {public static <T extends Comparable<? super T>> void sort(T[] arr) {sort(arr, 0, arr.length - 1, 16);}/** * @param arr 待排序的數組* @param left 左閉* @param right 右閉* @param k 當快排遞歸到子問題的規模<= k 時，採用插入排序優化* @param <T> 泛型，待排序可比較類型*/public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {// 規模小時採用插入排序if (right - left <= k) {insertionSort(arr, left, right);return;}int p = partition(arr, left, right);sort(arr, left, p - 1, k);sort(arr, p + 1, right, k);}public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {for (int i = l + 1; i <= r; i++) {T cur = arr[i];int j = i - 1;for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {arr[j + 1] = arr[j];}arr[j + 1] = cur;}}private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {//排序前，先讓基準值和隨機的一個數進行交換。這樣，基準值就有隨機性。 //就不至於在數組相對有序時，導致左右兩邊的遞歸規模不一致，產生最壞時間複雜度swap(arr, left, (int) (Math.random() * (right - left + 1) + left));T base = arr[left];int j = left;for (int i = left + 1; i <= right; i++) {if (base.compareTo(arr[i]) > 0) {j++;swap(arr, j, i);}}swap(arr, left, j);return j;//返回一躺排序後，基準值的下角標}public static void swap(Object[] arr, int i, int j) {if (i != j) {Object temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}private static void printArr(Object[] arr) {for (Object o : arr) {System.out.print(o);System.out.print("/t");}System.out.println();}public static void main(String args[]) {Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};printArr(arr);//3 5 1 7 2 9 8 0 4 6sort(arr);printArr(arr);//0 1 2 3 4 5 6 7 8 9}}

快速排序繼續優化：兩路快排

在最開始的普通快速排序說過，讓基準值base左邊的都比base小，而base右邊的都大於等於base。等於base的這些會聚集到右側(或者稍微改改大小關係就會聚集到左側)。總之就會聚集到一邊。這樣在數組中重複數字很多的時候，就又會導致兩邊子遞歸規模差距懸殊的情況。這時想把等於base的那些數分派到base兩邊，而不是讓他們聚集到一起。

（注：測試代碼的時候，最好把插入排序那部分注視掉，向我下面代碼中那樣...不然數據量小於k=16的時候執行的是插入排序.....）

 public class QuickSort {public static <T extends Comparable<? super T>> void sort(T[] arr) {sort(arr, 0, arr.length - 1, 16);}/** * @param arr 待排序的數組* @param left 左閉* @param right 右閉* @param k 當快排遞歸到子問題的規模<= k 時，採用插入排序優化* @param <T> 泛型，待排序可比較類型*/public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {// 規模小時採用插入排序// if (right - left <= k) {// insertionSort(arr, left, right);// return;// }if (left >= right) return;int p = partition(arr, left, right);sort(arr, left, p - 1, k);sort(arr, p + 1, right, k);}public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {for (int i = l + 1; i <= r; i++) {T cur = arr[i];int j = i - 1;for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {arr[j + 1] = arr[j];}arr[j + 1] = cur;}}private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {//排序前，先讓基準值和隨機的一個數進行交換。這樣，基準值就有隨機性。 //就不至於在數組相對有序時，導致左右兩邊的遞歸規模不一致，產生最壞時間複雜度swap(arr, left, (int) (Math.random() * (right - left + 1) + left));T base = arr[left];//基準值，每次都把這個基準值拋出去，看成[left+1.....right]左閉右閉區間的排序int i = left + 1;//對於上一行提到的[left+1.....right]區間，i表示[left+1......i)左閉右開區間的值都小於等於base。 int j = right;//對於上二行提到的[left+1.....right]區間，j表示(j......right]左開右閉區間的值都大於等於base。while (true) {//從左到右掃描，掃描出第一個比base大的元素，然後i停在那裡。while (i <= right && arr[i].compareTo(base) < 0) i++;//從右到左掃描，掃描出第一個比base小的元素，然後j停在那裡。while (j >= left && arr[j].compareTo(base) > 0) j--;if (i > j) {//雖說是i>j，但其實都是以j=i-1為條件結束的break;}swap(arr, i++, j--);}swap(arr, left, j);return j;//返回一躺排序後，基準值的下角標}public static void swap(Object[] arr, int i, int j) {if (i != j) {Object temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}private static void printArr(Object[] arr) {for (Object o : arr) {System.out.print(o);System.out.print("/t");}System.out.println();}public static void main(String args[]) {Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};printArr(arr);//3 5 1 7 2 9 8 0 4 6sort(arr);printArr(arr);//0 1 2 3 4 5 6 7 8 9}}

快速排序繼續優化：兩路快排不用swap,用交換

上面的兩路在找到大於base的值和小於base的值時，用的是swap()方法來進行交換。兩數交換涉及到第三個變量temp的操作，多了讀寫操作。接下來用直接賦值的方法，把小於的放到右邊，大於的放到左邊，當i和j相遇時，那個位置就是base該放的地方。至此一趟完成。遞歸即可。

 public class QuickSort {public static <T extends Comparable<? super T>> void sort(T[] arr) {sort(arr, 0, arr.length - 1, 16);}/** * @param arr 待排序的數組* @param left 左閉* @param right 右閉* @param k 當快排遞歸到子問題的規模<= k 時，採用插入排序優化* @param <T> 泛型，待排序可比較類型*/public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {// 規模小時採用插入排序// if (right - left <= k) {// insertionSort(arr, left, right);// return;// }if (left >= right) return;int p = partition(arr, left, right);sort(arr, left, p - 1, k);sort(arr, p + 1, right, k);}public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {for (int i = l + 1; i <= r; i++) {T cur = arr[i];int j = i - 1;for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {arr[j + 1] = arr[j];}arr[j + 1] = cur;}}private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {//排序前，先讓基準值和隨機的一個數進行交換。這樣，基準值就有隨機性。 //就不至於在數組相對有序時，導致左右兩邊的遞歸規模不一致，產生最壞時間複雜度swap(arr, left, (int) (Math.random() * (right - left + 1) + left));T base = arr[left];//基準值，每次都把這個基準值拋出去，看成[left+1.....right]左閉右閉區間的排序int i = left;//對於上一行提到的[left+1.....right]區間，i表示[left+1......i)左閉右開區間的值都小於等於base。 int j = right;//對於上二行提到的[left+1.....right]區間，j表示(j......right]左開右閉區間的值都大於等於base。while (i < j) {//從右到左掃描，掃描出第一個比base小的元素，然後j停在那裡。while (j > i && arr[j].compareTo(base) > 0) j--;arr[i] = arr[j];//從左到右掃描，掃描出第一個比base大的元素，然後i停在那裡。while (i < j && arr[i].compareTo(base) < 0) i++;arr[j] = arr[i];}arr[j] = base;return j;//返回一躺排序後，基準值的下角標}public static void swap(Object[] arr, int i, int j) {if (i != j) {Object temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}private static void printArr(Object[] arr) {for (Object o : arr) {System.out.print(o);System.out.print("/t");}System.out.println();}public static void main(String args[]) {Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};printArr(arr);//3 5 1 7 2 9 8 0 4 6sort(arr);printArr(arr);//0 1 2 3 4 5 6 7 8 9}}

快速排序繼續優化：當大量數據，且重複數多時，用三路快排

把數組分為三路，第一路都比base小，第二路都等於base，第三路都大於base。

用指針從前到後掃描，如果：

1.cur指向的數小於base，那麼：交換arr[cur]和arr[i]的值，然後i++,cur++。

2.cur指向的數等於base,那麼：cur++

3.cur指向的數大於base，那麼：交換arr[cur]和arr[j]的值，然後j--。

當cur>j的時候說明三路都已經完成。

 public class QuickSort {public static <T extends Comparable<? super T>> void sort(T[] arr) {sort(arr, 0, arr.length - 1, 16);}/** * @param arr 待排序的數組* @param left 左閉* @param right 右閉* @param k 當快排遞歸到子問題的規模<= k 時，採用插入排序優化* @param <T> 泛型，待排序可比較類型*/public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {// 規模小時採用插入排序// if (right - left <= k) {// insertionSort(arr, left, right);// return;// }if (left >= right) return;int[] ret = partition(arr, left, right);sort(arr, left, ret[0], k);sort(arr, ret[1], right, k);}public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {for (int i = l + 1; i <= r; i++) {T cur = arr[i];int j = i - 1;for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {arr[j + 1] = arr[j];}arr[j + 1] = cur;}}/** * @param arr 待排序的數組* @param left 待排序數組的左邊界* @param right 待排序數組的右邊界* @param <T> 泛型* @return */private static <T extends Comparable<? super T>> int[] partition(T[] arr, int left, int right) {//排序前，先讓基準值和隨機的一個數進行交換。這樣，基準值就有隨機性。 //就不至於在數組相對有序時，導致左右兩邊的遞歸規模不一致，產生最壞時間複雜度swap(arr, left, (int) (Math.random() * (right - left + 1) + left));T base = arr[left];//基準值，每次都把這個基準值拋出去，看成[left+1.....right]左閉右閉區間的排序//三路快排分為下面這三個路(區間)int i = left;// left表示，[lleft...left) 左閉右開區間裡的數都比base小int j = right;// left表示，(rright...right] 左開右閉區間裡的數都比base大int cur = i;//用cur來遍歷數組。[left...cur)左閉右開區間裡的數都等於basewhile (cur <= j) {if (arr[cur].compareTo(base) == 0) {cur++;} else if (arr[cur].compareTo(base) < 0) {swap(arr, cur++, i++);} else {swap(arr, cur, j--);}}return new int[]{i - 1, j + 1};//[i...j]都等於base,子問題就只需要解決i左邊和j右邊就行了}public static void swap(Object[] arr, int i, int j) {if (i != j) {Object temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}private static void printArr(Object[] arr) {for (Object o : arr) {System.out.print(o);System.out.print("/t");}System.out.println();}public static void main(String args[]) {Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};printArr(arr);//3 5 1 7 2 9 8 0 4 6sort(arr);printArr(arr);//0 1 2 3 4 5 6 7 8 9}}

總結

以上就是本文關於Java編程實現快速排序及優化代碼詳解的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！