为什么这个heapsort代码和选择排序一样慢？

Question

我正在对不同的排序方法进行性能测试，而GeeksforGeeks的Heapsort代码比Selection排序慢。虽然它的时间复杂度为O(n*logn)，但它似乎增加了4倍，而不是2倍。

下表显示了每种排序方法的已用时间。 （从第一列到最后一行：选择排序，插入排序，合并排序，快速排序，堆排序）

elements  elapsed time
1,000     0.19   0.03   0.15    0.05    0.11
2,000     0.51   0.06   0.22    0.12    0.41
4,000     1.64   0.11   0.36    0.17    1.53
8,000     7.49   0.21   0.85    0.23    5.89
16,000    33.62  0.34   1.07    0.33    28.01
32,000    123.9  0.99   1.72    0.6    118.07

public class HeapSort 
{ 
    public void sort(int arr[]) 
    { 
        int n = arr.length; 

        for (int i = n / 2 - 1; i >= 0; i--) 
            heapify(arr, n, i); 
        for (int i=n-1; i>=0; i--) 
        { 
            int temp = arr[0]; 
            arr[0] = arr[i]; 
            arr[i] = temp; 
            heapify(arr, i, 0); 
        } 
    } 

    void heapify(int arr[], int n, int i) 
    { 
        int largest = i;
        int l = 2*i + 1; 
        int r = 2*i + 2; 
        if (l < n && arr[l] > arr[largest]) 
            largest = l;  
        if (r < n && arr[r] > arr[largest]) 
            largest = r; 
        if (largest != i) 
        { 
            int swap = arr[i]; 
            arr[i] = arr[largest]; 
            arr[largest] = swap;
            heapify(arr, n, largest); 
        } 
    }
}

public class SelectionSort_asc
{
    public static void sort(int[] a)
    {
        int n = a.length;

        for (int i = 0; i < n - 1; i++) // search all of the nums (except the last one)
        {
            int lowest = i; // index of the smallest number
            int lowkey = a[i]; // the smallest number

            for (int j = i + 1; j < n; j++)
            {
                if(a[j] < lowkey)
                {
                    lowest = j; // change the index of the smallest number
                    lowkey = a[j]; // value of the smallest number also changes
                }
            }
            int temp = a[i];
            a[i] = a[lowest];
            a[lowest] = temp; // swap a[i] and the smallest number found
        }
    }
}

为什么速度与预期不同？请给我一些帮助。

Answer 1

示例heapsort代码。在我的系统上，32,000个元素不够长，因为显示屏显示0毫秒。 10,000,000个元素大约需要2秒。使用您发布的选择排序，64,000个元素大约需要2.5秒;它慢得多。

package heapsort;
import java.util.Random;

public class heapsort {

    static void HeapSort(int[] a)
    {
    int end;
        Heapify(a);
        end = a.length-1;
        while(end > 0){
            int t = a[0];
            a[0] = a[end];
            a[end] = t;
            end--;
            SiftDown(a, 0, end);
        }
    }

    static void Heapify(int[] a)
    {
    int root;
        if(a.length < 2)
            return;
        root = (a.length - 2) / 2;
        while(true){
            SiftDown(a, root, a.length-1);
            if(root == 0)
                break;
            root--;
        }
    }

    static void SiftDown(int[] a, int root, int end){
    int parent;
    int child;
    int t;
        for(parent = root; (child = parent * 2 + 2) <= end; ){
            if(a[child-1] > a[child])
                child = child-1;
            if(a[child] > a[parent]){
                t = a[child];
                a[child] = a[parent];
                a[parent] = t;
                parent = child;
            } else {
                break;
            }
        }
        if((child = parent * 2 + 1) <= end){
            if(a[child] > a[parent]){
                t = a[child];
                a[child] = a[parent];
                a[parent] = t;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[32000];
        Random r = new Random();
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt();
        long bgn, end;
        bgn = System.currentTimeMillis();
        HeapSort(a);
        end = System.currentTimeMillis();
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }
}