m********g
发帖数: 272 | 1 虽然worst－case quicksort是O(n^2), 但是on avarage, quicksort 为什么会比
heapsort 快呢？ | c*********7
发帖数: 19373 | | P****a
发帖数: 864 | 3 实战中和cache结合得好
【在 m********g 的大作中提到】
: 虽然worst－case quicksort是O(n^2), 但是on avarage, quicksort 为什么会比
: heapsort 快呢？
| h**********d
发帖数: 4313 | | m********g
发帖数: 272 | 5 指的是哪一个inner loop?
【在 h**********d 的大作中提到】
: 因为inner loop效率高
| h***o
发帖数: 30 | 6 Expected complexity是O(nlogn), partition很精简常数小， in-place, 每次逐个扫
数据
(cache miss少)
【在 m********g 的大作中提到】
: 虽然worst－case quicksort是O(n^2), 但是on avarage, quicksort 为什么会比
: heapsort 快呢？
| s********x
发帖数: 914 | 7 // MaxHeap: heapArray starts from index 0
public static void heapSort(int[] a){
// Trickling Down in Place: start at node n/2-1, the rightmost node
with children
// O(n/2*log(n))
for (int i=(a.length/2-1) ; i>=0 ; i--)
trickleDown(a,i, a.length);
// remove max from heap and insert it at the end
// O(n*log(n))
for (int i= a.length - 1; i> 0; i--){
int max = a[0];
a[0] = a[i];
trickleDown(a,0, i);
a[i] = max;
}
}
// the number of levels L in a binary tree equals log2(n+1), where n is the
number of nodes.
// trickleUp() takes time proportional to log2(n), and trickleDown()
takes
// somewhat more it needs two comparisons
private static void trickleUp(int[] heapArray, int i){
if (i>=heapArray.length)
System.err.println("index exceeding the size of the heap");
int parent = (i - 1)/2;
while( i > 0 && heapArray[parent]< heapArray[i]) {
swap(heapArray, parent, i);
i = parent;
parent = (parent - 1)/2;
}
}
private static void trickleDown(int[] a, int i, int size){
// size = a.length
// the last element is a[size-1] and its parent is a[size/2-1]
while( i < size/2 ){
int leftChild = 2*i + 1;
int rightChild = leftChild + 1;
int largerChild;
if (rightChild < size // rightChild exists?
&& a[leftChild]
largerChild = rightChild;
else
largerChild = leftChild;
if (a[i]>=a[largerChild])
break;
swap(a, i, largerChild);
i = largerChild;
}
}
【在 m********g 的大作中提到】
: 指的是哪一个inner loop?
| s********x
发帖数: 914 | 8 heapSort is n/2*log(1.5n)+n*log(1.5n)
quickSort is nlog(n)
node
【在 s********x 的大作中提到】
: // MaxHeap: heapArray starts from index 0
: public static void heapSort(int[] a){
: // Trickling Down in Place: start at node n/2-1, the rightmost node
: with children
: // O(n/2*log(n))
: for (int i=(a.length/2-1) ; i>=0 ; i--)
: trickleDown(a,i, a.length);
: // remove max from heap and insert it at the end
: // O(n*log(n))
: for (int i= a.length - 1; i> 0; i--){
|
|
