我在比较快速排序(正常,递归)和线程快速排序(使用线程)。而且我知道Normal-QuickSort比Threaded-QuickSort更快。这是正确的吗?感觉自己做错了什么。
这是代码:
public class QuickSort implements SortAlgorithm {
public void Sort(Integer[] array) {
Sort(array, 0, array.length-1);
}
private void Sort(Integer[] array, Integer low, Integer high) {
if (low < high) {
Integer pivot = partition(array, low, high);
Sort(array, low, pivot-1);
Sort(array, pivot+1, high);
}
}
private Integer partition(Integer[] array, Integer low, Integer high) {
Integer pivot = array[high];
Integer i = (low-1);
for (Integer j=low; j<high; j++)
if (array[j] < pivot) {
i++;
Integer temp = array[i];
array[i] = array[j];
array[j] = temp;
}
Integer temp = array[i+1];
array[i+1] = array[high];
array[high] = temp;
return i+1;
}
}
public class ThreadsQuickSort extends Thread implements SortAlgorithm {
private Integer low, high;
private Integer[] array;
public ThreadsQuickSort() {
;
}
public ThreadsQuickSort(Integer[] array, Integer low, Integer high) {
this.array = array;
this.low = low;
this.high = high;
}
public void run() {
Sort(array, low, high);
}
public void Sort(Integer[] array) {
Sort(array, 0, array.length - 1);
}
private void Sort(Integer[] array, Integer low, Integer high) {
if (low < high) {
Integer pivot = partition(array, low, high);
ThreadsQuickSort lowQSort = new ThreadsQuickSort(array, low, pivot - 1);
lowQSort.start();
ThreadsQuickSort highQSort = new ThreadsQuickSort(array, pivot + 1, high);
highQSort.start();
try {
lowQSort.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
try {
highQSort.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
private Integer partition(Integer[] array, Integer low, Integer high) {
Integer pivot = array[high];
Integer i = (low-1);
for (Integer j=low; j<high; j++)
if (array[j] < pivot) {
i++;
Integer temp = array[i];
array[i] = array[j];
array[j] = temp;
}
Integer temp = array[i+1];
array[i+1] = array[high];
array[high] = temp;
return i+1;
}
}
main函数使用两种算法对10,000个项目的数组进行排序,并获取它们的执行时间。得到以下输出:
Single array sorted in 11 ms
The array was successfully sorted
Threaded array sorted in 6378 ms
The array was successfully sorted
我的问题是,如果编码正确,并且预期得到输出。这与Threaded-QuickSort的实现无关。
约70个微创建和每个线程切换。
线程总和应在20000-1左右,这将使20000 * 70us = 1400000us = 1400ms = 1.4s
因此,这几乎是预期的。
为什么理论值为1400ms时会期望6378ms?
@AndréKuljis创建多个线程时,创建/切换时间可能会增加。