为什么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 };
答
基本上,你的冒泡排序被打破以某种方式 - 用达伦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,并且不止一次地访问数组的部分。
快速排序对于小数据集可能看起来较慢,因为您的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