Java編程實(shí)現(xiàn)快速排序及優(yōu)化代碼詳解
更新時(shí)間：2017年12月05日 15:17:56 作者：GoldArowana
這篇文章主要介紹了Java編程實(shí)現(xiàn)快速排序及優(yōu)化代碼詳解，具有一定借鑒價(jià)值，需要的朋友可以了解下。
普通快速排序
找一個(gè)基準(zhǔn)值base，然后一趟排序后讓base左邊的數(shù)都小于base，base右邊的數(shù)都大于等于base。再分為兩個(gè)子數(shù)組的排序。如此遞歸下去。
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;
//返回一躺排序后基準(zhǔn)值的下角標(biāo)
}
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 6
sort(arr);
printArr(arr);
//0 1 2 3 4 5 6 7 8 9
}
}
快速排序優(yōu)化：隨機(jī)選取基準(zhǔn)值base
在數(shù)組幾乎有序時(shí)，快排性能不好（因?yàn)槊刻伺判蚝?，左右兩個(gè)子遞歸規(guī)模相差懸殊，大的那部分最后很可能會(huì)達(dá)到O(n^2)）。
解決：基準(zhǔn)值隨機(jī)地選取，而不是每次都取第一個(gè)數(shù)。這樣就不會(huì)受“幾乎有序的數(shù)組”的干擾了。但是對(duì)“幾乎亂序的數(shù)組”的排序性能可能會(huì)稍微下降，至少多了排序前交換的那部分，亂序時(shí)這個(gè)交換沒有意義...有很多“運(yùn)氣”成分..
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) {
//排序前，先讓基準(zhǔn)值和隨機(jī)的一個(gè)數(shù)進(jìn)行交換。這樣，基準(zhǔn)值就有隨機(jī)性。
//就不至于在數(shù)組相對(duì)有序時(shí)，導(dǎo)致左右兩邊的遞歸規(guī)模不一致，產(chǎn)生最壞時(shí)間復(fù)雜度
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;
//返回一躺排序后，基準(zhǔn)值的下角標(biāo)
}
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 6
sort(arr);
printArr(arr);
//0 1 2 3 4 5 6 7 8 9
}
}
快速排序繼續(xù)優(yōu)化：配合著使用插入排序
快排是不斷減小問題規(guī)模來解決子問題的，需要不斷遞歸。但是遞歸到規(guī)模足夠小時(shí)，如果繼續(xù)采用這種 不穩(wěn)定+遞歸 的方式執(zhí)行下去，效率不見得會(huì)很好。
所以當(dāng)問題規(guī)模較小時(shí)，近乎有序時(shí)，插入排序表現(xiàn)的很好。Java自帶的Arrays.sort()里經(jīng)常能看到這樣的注釋：“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 待排序的數(shù)組
* @param left 左閉
* @param right 右閉
* @param k 當(dāng)快排遞歸到子問題的規(guī)模 <= k 時(shí)，采用插入排序優(yōu)化
* @param <T> 泛型，待排序可比較類型
*/
public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
// 規(guī)模小時(shí)采用插入排序
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) {
//排序前，先讓基準(zhǔn)值和隨機(jī)的一個(gè)數(shù)進(jìn)行交換。這樣，基準(zhǔn)值就有隨機(jī)性。
//就不至于在數(shù)組相對(duì)有序時(shí)，導(dǎo)致左右兩邊的遞歸規(guī)模不一致，產(chǎn)生最壞時(shí)間復(fù)雜度
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;
//返回一躺排序后，基準(zhǔn)值的下角標(biāo)
}
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 6
sort(arr);
printArr(arr);
//0 1 2 3 4 5 6 7 8 9
}
}
快速排序繼續(xù)優(yōu)化：兩路快排
在最開始的普通快速排序說過，讓基準(zhǔn)值base左邊的都比base小，而base右邊的都大于等于base。等于base的這些會(huì)聚集到右側(cè)(或者稍微改改大小關(guān)系就會(huì)聚集到左側(cè))?？傊蜁?huì)聚集到一邊。這樣在數(shù)組中重復(fù)數(shù)字很多的時(shí)候，就又會(huì)導(dǎo)致兩邊子遞歸規(guī)模差距懸殊的情況。這時(shí)想把等于base的那些數(shù)分派到base兩邊，而不是讓他們聚集到一起。
（注：測(cè)試代碼的時(shí)候，最好把插入排序那部分注視掉，向我下面代碼中那樣...不然數(shù)據(jù)量小于k=16的時(shí)候執(zhí)行的是插入排序.....）
public class QuickSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1, 16);
}
/**
* @param arr 待排序的數(shù)組
* @param left 左閉
* @param right 右閉
* @param k 當(dāng)快排遞歸到子問題的規(guī)模 <= k 時(shí)，采用插入排序優(yōu)化
* @param <T> 泛型，待排序可比較類型
*/
public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
// 規(guī)模小時(shí)采用插入排序
// 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) {
//排序前，先讓基準(zhǔn)值和隨機(jī)的一個(gè)數(shù)進(jìn)行交換。這樣，基準(zhǔn)值就有隨機(jī)性。
//就不至于在數(shù)組相對(duì)有序時(shí)，導(dǎo)致左右兩邊的遞歸規(guī)模不一致，產(chǎn)生最壞時(shí)間復(fù)雜度
swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
T base = arr[left];
//基準(zhǔn)值，每次都把這個(gè)基準(zhǔn)值拋出去，看成[left+1.....right]左閉右閉區(qū)間的排序
int i = left + 1;
//對(duì)于上一行提到的[left+1.....right]區(qū)間，i表示 [left+1......i)左閉右開區(qū)間的值都小于等于base。
int j = right;
//對(duì)于上二行提到的[left+1.....right]區(qū)間，j表示 (j......right]左開右閉區(qū)間的值都大于等于base。
while (true) {
//從左到右掃描，掃描出第一個(gè)比base大的元素，然后i停在那里。
while (i <= right && arr[i].compareTo(base) < 0) i++;
//從右到左掃描，掃描出第一個(gè)比base小的元素，然后j停在那里。
while (j >= left && arr[j].compareTo(base) > 0) j--;
if (i > j) {
//雖說是i>j，但其實(shí)都是以j=i-1為條件結(jié)束的
break;
}
swap(arr, i++, j--);
}
swap(arr, left, j);
return j;
//返回一躺排序后，基準(zhǔn)值的下角標(biāo)
}
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 6
sort(arr);
printArr(arr);
//0 1 2 3 4 5 6 7 8 9
}
}
快速排序繼續(xù)優(yōu)化：兩路快排 不用swap,用交換
上面的兩路在找到大于base的值和小于base的值時(shí)，用的是swap()方法來進(jìn)行交換。兩數(shù)交換涉及到第三個(gè)變量temp的操作，多了讀寫操作。接下來用直接賦值的方法，把小于的放到右邊，大于的放到左邊，當(dāng)i和j相遇時(shí)，那個(gè)位置就是base該放的地方。至此一趟完成。遞歸即可。
public class QuickSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1, 16);
}
/**
* @param arr 待排序的數(shù)組
* @param left 左閉
* @param right 右閉
* @param k 當(dāng)快排遞歸到子問題的規(guī)模 <= k 時(shí)，采用插入排序優(yōu)化
* @param <T> 泛型，待排序可比較類型
*/
public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
// 規(guī)模小時(shí)采用插入排序
// 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) {
//排序前，先讓基準(zhǔn)值和隨機(jī)的一個(gè)數(shù)進(jìn)行交換。這樣，基準(zhǔn)值就有隨機(jī)性。
//就不至于在數(shù)組相對(duì)有序時(shí)，導(dǎo)致左右兩邊的遞歸規(guī)模不一致，產(chǎn)生最壞時(shí)間復(fù)雜度
swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
T base = arr[left];
//基準(zhǔn)值，每次都把這個(gè)基準(zhǔn)值拋出去，看成[left+1.....right]左閉右閉區(qū)間的排序
int i = left;
//對(duì)于上一行提到的[left+1.....right]區(qū)間，i表示 [left+1......i)左閉右開區(qū)間的值都小于等于base。
int j = right;
//對(duì)于上二行提到的[left+1.....right]區(qū)間，j表示 (j......right]左開右閉區(qū)間的值都大于等于base。
while (i < j) {
//從右到左掃描，掃描出第一個(gè)比base小的元素，然后j停在那里。
while (j > i && arr[j].compareTo(base) > 0) j--;
arr[i] = arr[j];
//從左到右掃描，掃描出第一個(gè)比base大的元素，然后i停在那里。
while (i < j && arr[i].compareTo(base) < 0) i++;
arr[j] = arr[i];
}
arr[j] = base;
return j;
//返回一躺排序后，基準(zhǔn)值的下角標(biāo)
}
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 6
sort(arr);
printArr(arr);
//0 1 2 3 4 5 6 7 8 9
}
}
快速排序繼續(xù)優(yōu)化：當(dāng)大量數(shù)據(jù)，且重復(fù)數(shù)多時(shí)，用三路快排
把數(shù)組分為三路，第一路都比base小，第二路都等于base，第三路都大于base。
用指針從前到后掃描，如果：
1.cur指向的數(shù)小于base，那么：交換arr[cur]和arr[i]的值，然后i++,cur++。
2.cur指向的數(shù)等于base,那么：cur++
3.cur指向的數(shù)大于base，那么：交換arr[cur]和arr[j]的值，然后j--。
當(dāng)cur>j的時(shí)候說明三路都已經(jīng)完成。
public class QuickSort {
public static <T extends Comparable<? super T>> void sort(T[] arr) {
sort(arr, 0, arr.length - 1, 16);
}
/**
* @param arr 待排序的數(shù)組
* @param left 左閉
* @param right 右閉
* @param k 當(dāng)快排遞歸到子問題的規(guī)模 <= k 時(shí)，采用插入排序優(yōu)化
* @param <T> 泛型，待排序可比較類型
*/
public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
// 規(guī)模小時(shí)采用插入排序
// 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 待排序的數(shù)組
* @param left 待排序數(shù)組的左邊界
* @param right 待排序數(shù)組的右邊界
* @param <T> 泛型
* @return
*/
private static <T extends Comparable<? super T>> int[] partition(T[] arr, int left, int right) {
//排序前，先讓基準(zhǔn)值和隨機(jī)的一個(gè)數(shù)進(jìn)行交換。這樣，基準(zhǔn)值就有隨機(jī)性。
//就不至于在數(shù)組相對(duì)有序時(shí)，導(dǎo)致左右兩邊的遞歸規(guī)模不一致，產(chǎn)生最壞時(shí)間復(fù)雜度
swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
T base = arr[left];
//基準(zhǔn)值，每次都把這個(gè)基準(zhǔn)值拋出去，看成[left+1.....right]左閉右閉區(qū)間的排序
//三路快排分為下面這三個(gè)路(區(qū)間)
int i = left;
// left表示，[lleft...left) 左閉右開區(qū)間里的數(shù)都比base小
int j = right;
// left表示，(rright...right] 左開右閉區(qū)間里的數(shù)都比base大
int cur = i;
//用cur來遍歷數(shù)組。[left...cur)左閉右開區(qū)間里的數(shù)都等于base
while (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 6
sort(arr);
printArr(arr);
//0 1 2 3 4 5 6 7 8 9
}
}
總結(jié)
以上就是本文關(guān)于Java編程實(shí)現(xiàn)快速排序及優(yōu)化代碼詳解的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于java中拼接字符串的5種方法效率對(duì)比的相關(guān)資料，文中通過示例代碼和圖片介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2018-01-01
這篇文章主要介紹了深入理解Java編程線程池的實(shí)現(xiàn)原理，涉及ThreadPoolExecutor類，線程池實(shí)現(xiàn)原理及示例等相關(guān)內(nèi)容，具有一定參考價(jià)值，需要的朋友可以了解下。2017-11-11
Java如何取掉json數(shù)據(jù)中值為null的屬性字段
這篇文章主要介紹了Java如何取掉json數(shù)據(jù)中值為null的屬性字段，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-03-03
SpringBoot配置log4j2的實(shí)現(xiàn)示例
SpringBoot中默認(rèn)使用Logback作為日志框架,本文主要介紹了SpringBoot配置log4j2的實(shí)現(xiàn)示例,具有一定的參考價(jià)值,感興趣的可以了解一下2023-12-12
SpringBoot調(diào)用service層的三種方法
在Spring?Boot中,我們可以通過注入Service層對(duì)象來調(diào)用Service層的方法,Service層是業(yè)務(wù)邏輯的處理層,它通常包含了對(duì)數(shù)據(jù)的增刪改查操作,本文給大家介紹了SpringBoot調(diào)用service層的三種方法,需要的朋友可以參考下2024-05-05
這篇文章主要介紹了java金錢處理方法實(shí)例詳解的相關(guān)資料,這里提供實(shí)現(xiàn)方法分轉(zhuǎn)化成元的實(shí)現(xiàn)方法，需要的朋友可以參考下2017-08-08
Mybatis之Select Count(*)的獲取返回int的值操作
這篇文章主要介紹了Mybatis之Select Count(*)的獲取返回int的值操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-11-11
springboot實(shí)現(xiàn)攔截器的3種方式及異步執(zhí)行的思考
實(shí)際項(xiàng)目中，我們經(jīng)常需要輸出請(qǐng)求參數(shù)，響應(yīng)結(jié)果，方法耗時(shí)，統(tǒng)一的權(quán)限校驗(yàn)等。本文首先為大家介紹 HTTP 請(qǐng)求中三種常見的攔截實(shí)現(xiàn)，并且比較一下其中的差異。感興趣的可以了解一下2021-07-07
Redis是一個(gè)非常強(qiáng)大的工具,它可以用來實(shí)現(xiàn)很多有趣的應(yīng)用,還可以使用Redis來實(shí)現(xiàn)分布式鎖,這樣你就可以在多線程或多進(jìn)程的環(huán)境下同步代碼,這篇文章主要介紹了Java中的Redis是什么意思,需要的朋友可以參考下2023-08-08
SpringBoot 內(nèi)嵌 camunda的配置方法
Camunda是一個(gè)基于Java的框架,支持用于工作流和流程自動(dòng)化的BPMN、用于案例管理的CMMN和用于業(yè)務(wù)決策管理的DMN,這篇文章主要介紹了SpringBoot 內(nèi)嵌 camunda,需要的朋友可以參考下2024-06-06