我在做排序陣列問題，找到了一個非常快的快速排序解決方案，唯一的區別是函式1Partition中的兩行代碼。想知道為什么1Partition下面兩行代碼可以大大提高性能：
int mi = low (high-low)/2;
swap(arr,high,mi);
這是完整的源代碼：
class Solution {
public void swap(int[] arr, int i, int j){
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
public void qSort(int[] arr, int low, int high){
if(low<high){
int pi = lPartition(arr,low,high);
qSort(arr,low,pi-1);
qSort(arr,pi 1,high);
}
}
public Integer lPartition(int[] arr, int low, int high){
int mi = low (high-low)/2;
swap(arr,high,mi);
int pi = high;
int i = low-1;
for(int j=low;j<high;j ){
if(arr[j]<arr[pi]){
i ;
swap(arr,i,j);
}
}
swap(arr,pi,i 1);
return (i 1);
}
public int[] sortArray(int[] arr) {
qSort(arr,0,arr.length-1);
return arr;
}
}
uj5u.com熱心網友回復：
我猜你是在一個類似于 leetcode 的網站上做這個問題的。
如果他們的測驗用例包含一個已排序的陣列（通常他們會），如果不添加這兩行，您的快速排序時間復雜度將退化為 o(n^2)。（您將始終選擇最大的數字作為pivot）。
您也可以選擇一個隨機值作為 ，而不是選擇中值pivot：
swap(arr,high,randomIndex in range);
我在我的電腦上做了一個簡單的測驗，對一個長度為 100,000 的有序陣列進行排序。沒有這兩行代碼，需要2700ms（加上這兩行只需要40ms）
uj5u.com熱心網友回復：
您的問題表明您需要 oop 的基礎知識。嘗試使用 oop 使其更好。創建參考型別變數并在主函式中使用它。盡可能減少變數的數量。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/368465.html
下一篇：R使用自定義比較功能排序或排序