目錄

快速排序基礎(chǔ)

優(yōu)化1：隨機(jī)取樣

優(yōu)化2：三數(shù)取中

優(yōu)化3：插入排序

總結(jié)：

---

快速排序（Quick Sort）是一種高效的排序算法，它的平均時(shí)間復(fù)雜度為O(n log n)。然而，在某些情況下，快速排序可能表現(xiàn)不佳，特別是在輸入數(shù)據(jù)近乎有序或包含大量重復(fù)元素時(shí)。為了解決這些問(wèn)題，我們可以對(duì)快速排序進(jìn)行一些優(yōu)化。本文將介紹Java語(yǔ)言中如何使用隨機(jī)取樣、三數(shù)取中和插入排序等優(yōu)化技巧來(lái)提高快速排序的性能。

快速排序基礎(chǔ)

快速排序的基本思想是選擇一個(gè)基準(zhǔn)元素（pivot），將數(shù)組分成兩個(gè)子數(shù)組，小于基準(zhǔn)的元素放在左邊，大于基準(zhǔn)的元素放在右邊，然后對(duì)這兩個(gè)子數(shù)組遞歸地進(jìn)行排序。

public static void quickSort(int[] arr){quick(arr,0,arr.length-1);
}private static void quick(int[] arr,int start,int end){if (start>=end){return;}int pivot=partition(arr,start,end);quick(arr,start,pivot-1);quick(arr,pivot+1,end);
}private static int partition(int[] arr,int left,int right ){int tmp=arr[left];while (left<right){while (left<right&&arr[right]>=tmp){right--;}arr[left]=arr[right];while (left<right&&arr[left]<=tmp){left++;}arr[right]=arr[left];}arr[left]=tmp;return left;
}

優(yōu)化1：隨機(jī)取樣

在快速排序中，如果每次選擇的基準(zhǔn)元素都是數(shù)組的最左邊或最右邊，那么在輸入數(shù)據(jù)接近有序時(shí)，性能會(huì)下降。為了解決這個(gè)問(wèn)題，我們可以隨機(jī)選擇基準(zhǔn)元素。

private static void quick(int[] arr,int start,int end){if (start>=end){return;}int randomIndex = getRandomIndex(start, end);swap(arr, start, randomIndex);int pivot=partition(arr,start,end);quick(arr,start,pivot-1);quick(arr,pivot+1,end);
}
public int getRandomIndex(int low, int high) {Random rand = new Random();return rand.nextInt(high - low + 1) + low;
}

隨機(jī)選擇基準(zhǔn)元素可以減小快速排序在特定輸入下的性能波動(dòng)。

優(yōu)化2：三數(shù)取中

另一個(gè)性能優(yōu)化的方法是選擇中位數(shù)作為基準(zhǔn)元素。這可以避免最壞情況下的快速排序性能下降。

private static void quick(int[] arr,int start,int end){if (start>=end){return;}//三數(shù)取中法int index=midThree(arr,start,end);int tmp=arr[start];arr[start]=arr[index];arr[index]=tmp;int pivot=partition1(arr,start,end);quick(arr,start,pivot-1);quick(arr,pivot+1,end);
}
private static int midThree(int[] arr,int left,int right){int mid=(left+right)/2;if (arr[left]<right){if (arr[mid]<arr[left]){return left;}else if (arr[mid]>arr[right]){return right;}else {return mid;}}else {//arr[left]>rightif (arr[mid]<arr[right]){return right;}else if (arr[mid]>arr[left]){return left;}else {return mid;}}
}

三數(shù)取中的方法可以有效地避免快速排序的最壞情況，提高了算法的穩(wěn)定性。

優(yōu)化3：插入排序

對(duì)于小規(guī)模的數(shù)組，快速排序的遞歸開(kāi)銷可能會(huì)變得顯著。在這種情況下，使用插入排序可以提高性能。

private static void quick(int[] arr,int start,int end){if (start>=end){return;}if(end-start+1<=14){//插入排序insertSort2(arr, start, end);return;}//三數(shù)取中法int index=midThree(arr,start,end);int tmp=arr[start];arr[start]=arr[index];arr[index]=tmp;int pivot=partition(arr,start,end);quick(arr,start,pivot-1);quick(arr,pivot+1,end);}public static void insertSort2(int[] arr,int start,int end){for (int i = start; i <= end; i++) {int temp=arr[i];int j=i-1;while (j>=0&&arr[j]>temp){arr[j+1]=arr[j];j--;}arr[j+1]=temp;}}private static int midThree(int[] arr,int left,int right){int mid=(left+right)/2;if (arr[left]<right){if (arr[mid]<arr[left]){return left;}else if (arr[mid]>arr[right]){return right;}else {return mid;}}else {//arr[left]>rightif (arr[mid]<arr[right]){return right;}else if (arr[mid]>arr[left]){return left;}else {return mid;}}}private static int partition(int[] arr,int left,int right ){int tmp=arr[left];while (left<right){while (left<right&&arr[right]>=tmp){right--;}arr[left]=arr[right];while (left<right&&arr[left]<=tmp){left++;}arr[right]=arr[left];}arr[left]=tmp;return left;}

注意：代碼里的小于14長(zhǎng)度是我自己規(guī)定的，各位友友可以自己定義小數(shù)組的長(zhǎng)度~~

插入排序在小規(guī)模數(shù)組上的性能通常比快速排序更好~~

總結(jié)：

在Java中，優(yōu)化快速排序的方法包括隨機(jī)取樣、三數(shù)取中和插入排序。這些優(yōu)化可以改善快速排序在各種輸入情況下的性能表現(xiàn)，使其成為一種強(qiáng)大而高效的排序算法。通過(guò)合理地選擇這些優(yōu)化技巧，可以根據(jù)實(shí)際需求來(lái)提高算法的性能。喜歡的友友可以關(guān)注一下博主噢🤩