为什么QuickSort比BubbleSort慢得多？

我想知道为什么我的quickSort太慢了。需要10-20秒对以下数组进行排序。 Bubblesort（如下所示）自动执行。为什么QuickSort比BubbleSort慢得多？

public static void quickSort(int[] tab, int lowIndex, int highIndex) { 
if (tab == null || tab.length == 0) { 
    return; 
} 

int i = lowIndex; 
int j = highIndex; 

int pivot = tab[lowIndex + (highIndex - lowIndex)/2]; 

while (i <= j) { 
    while (tab[i] < pivot) { 
    i++; 
    } 
    while (tab[j] > pivot) { 
    j--; 
    } 

    if (i <= j) { 
    int c = tab[i]; 
    tab[i] = tab[j]; 
    tab[j] = c; 
    i++; 
    j--; 
    } 

    if (lowIndex < j) { 
    quickSort(tab, lowIndex, j); 
    } 
    if (i < highIndex) { 
    quickSort(tab, i, highIndex); 
    } 
} 

} 

public static void bubbleSort(int[] arr) { 
int n = arr.length - 1; 
while (n >= 1) { 
    for (int i = 0; i < n; i++) { 
    if (arr[i] > arr[i + 1]) { 
     int c = arr[i]; 
     arr[i] = arr[i + 1]; 
     arr[i + 1] = c; 
    } 
    } 
    n--; 
} 
} 

public static void main(String[] args) { 
int[] t = new int[] { 5, 1, 33, 13, 21, 2, 12, 4, 
    2, 3, 53, 2, 125, 23, 53, 523, 5, 235, 235, 235, 23, 523, 1, 
    2, 41, 2412, 412, 4, 124, 1, 241, 24, 1, 43, 6, 346, 457, 56, 
    74, 5, 3, 5, 1, 33, 13, 21, 2, 12, 4, 
    2, 3, 53, 2, 125, 23, 53, 523, 5, 235, 235, 235, 23, 523, 1, 
    2, 41, 2412, 412, 4, 124, 1, 241, 24, 1, 43, 6, 346, 457, 56, 
    74, 5, 3, 74, 5, 3, 5, 1, 33, 13, 21, 2, 12, 4, 
    2, 3, 53, 2, 125, 23, 53, 523, 5, 235, 235, 235, 23, 523, 1, 
    2, 41, 2412, 412, 4, 124, 1, 241, 24, 1, 43, 6, 346, 457, 56, 
    74, 5, 3 };

来源

2013-02-16 Stuart

快速排序对于小数据集可能看起来较慢，因为您的quicksort实现包含递归调用。 – wns349 2013-02-16 13:00:40

bubblesort的最坏情况是n^2。 quicksort的wortcase复杂度是n * ln（n）。这是最糟糕的情况，它对个别情况没有任何规定。你的数据有多大，有多大？ “自动”是什么意思？ – 2013-02-16 13:06:01

对于我的代码中的数组，快速排序时间约为15秒，并且小于1秒。 – Stuart 2013-02-16 13:11:58

基本上，你的冒泡排序被打破以某种方式 - 用达伦Engwirda挂在他的评论在http://www.mycstutorials.com/articles/sorting/quicksort实施，并与新建的数组，每次运行的种种，我得到以下时间：

bash-3.1$ time java -cp bin Sort none 

real 0m0.079s 
user 0m0.000s 
sys  0m0.015s 
bash-3.1$ time java -cp bin Sort quick 

real 0m0.084s 
user 0m0.015s 
sys  0m0.015s 
bash-3.1$ time java -cp bin Sort bubble 

real 0m0.115s 
user 0m0.000s 
sys  0m0.000s

，其中基础设施运行三个测试是：

private static int[] data() { 
    return new int[] { ... the same data as in the OP ... }; 
} 

public static void main(String[] args) { 
    if (args.length == 0 || args [ 0 ].equals ("bubble")) { 
     for (int i = 0; i < 1000; ++i) { 
      int[] data = data(); 
      bubbleSort (data); 
     } 
    } else if (args [ 0 ].equals ("none")) { 
     for (int i = 0; i < 1000; ++i) { 
      int[] data = data(); 
     } 
    } else if (args [ 0 ].equals ("quick")) { 
     for (int i = 0; i < 1000; ++i) { 
      int[] data = data(); 
      quickSort(data, 0, data.length-1); 
     } 
    } else if (args [ 0 ].equals ("quick_op")) { 
     for (int i = 0; i < 1000; ++i) { 
      int[] data = data(); 
      quickSort_op(data, 0, data.length-1); 
     } 
    } 
}

所以一个正确实现快速排序取〜5μs的排序的DA ta，你的冒泡排序需要36μs来排序数据。对于这些数据，快速排序算法比气泡排序更好。

移动外循环的递归调用意味着你的代码排序阵列（不过，如果存在任何其他瑕疵我没有检查），结果如下：

bash-3.1$ time java -cp bin Sort op_quick 

real 0m0.108s 
user 0m0.015s 
sys  0m0.015s

这仍然是更快而不是像其他实现那样快 - 我认为你可能会重叠j和i，并且不止一次地访问数组的部分。

来源

2013-02-16 21:38:44

为什么QuickSort比BubbleSort慢得多？

回答

相关问题