Java 快速排序性能

Question

我在做数组排序题，发现一种快速排序的解法非常快，唯一不同的是函数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;
}

}

Answer 1

我猜你是在类似leetcode的网站上做题的

如果他们的测试用例包含排序数组（通常他们会 ), 如果不添加这两行，您的快速排序时间复杂度将退化为 o(n^2)。（您将始终选择最大的数字作为 pivot）。

除了选择中值，您还可以选择一个随机值作为 pivot:

swap(arr,high,randomIndex in range);

我在电脑上做了一个简单的测试，对长度为100,000的有序数组进行排序。如果没有这两行代码，需要2700ms（加上这两行只需要40ms）

Java 快速排序性能

Java Quick Sort Performance

java

sorting

algorithm

performance

quicksort