HeapSort的实现

Question

下面的代码是数组上堆排序的实现

public static void heapSort(int[] inputArray){
    /* Creates an array A which will contain the heap */
    /* A has size n+1 to allow 1-based indexing */
    int n = inputArray.length;
    int[] A = new int[n+1];
    int temp = 0;

    /* Copies the array inputArray into A, with inputArray[i] being stored in A[i+1] */

    for(int i=0; i<n; i++){
        A[i+1] = inputArray[i];
    }
    constructHeap(A, n, 1);
    removeMax(A, n);
    copyBack(A, inputArray);
}

    /* Transforms A into a max-heap using a 'bottom-up' algorithm. */
public static void constructHeap(int[] A, int n, int i){
    if(2*i>n) return;
    constructHeap(A, n, 2*i);
    constructHeap(A, n, 2*i+1);
    bubbleDown(A, n, i);
}
/*recursively swaps parent/child relationships until the max-heap property is satisfied. */
public static void bubbleDown(int[] A, int n, int i){
    if(2*i>n) return;
    int leftChild = 2*i;
    int rightChild = 2*i+1;
    int max = leftChild;
    if(rightChild<=n && A[max]<A[rightChild]){
        max = rightChild;
    }
    if(A[i]<A[max]){
        int temp = A[i];
        A[i] = A[max];
        A[max] = temp;
        bubbleDown(A, n, max);
    }
}

    /* Performs a sequence of n 'remove-maximum' operations, storing the removed element at
       each step in successively smaller indices of A */

public static void removeMax(int[] A, int i){
    for(int i=n; i>0; i--){
        int temp = A[1];
        A[1] = A[i];
        bubbleDown(A, i, 1);
        A[i] = temp;
}

    /* Copies the sorted values in A back into inputArray, with inputArray[i] getting
       the value from A[i+1] */

public static void copyBack(int[] A, int[] inputArray){
    for(int i=0; i<inputArray.length; i++){
        inputArray[i] = A[i+1];
    }
}

Answer 1

constructHeap方法在O(n)中工作，从removeMax方法调用O(n)次，所以代码在O(n^2)中工作，所以它不是Heapsort的正确实现。

评论：

public static void heapSort(int[] inputArray) {

你为什么需要另一个数组？赫普索德已经到位了。

  /* Creates an array A which will contain the heap */

为什么你需要基于1的索引？你似乎没有在任何地方使用它，基于0的更方便。

  /* A has size n+1 to allow 1-based indexing */
  int n = inputArray.length;


  int[] A = new int[n + 1];

你不用这个变量。

  int temp = 0;

  /* Copies the array inputArray into A, with inputArray[i] being stored in A[i+1] */

应该用System.arraycopy(.)替换这个循环。打电话

  for (int i = 0; i < n; i++) {
    A[i + 1] = inputArray[i];
  }
  constructHeap(A, n, 1);
  removeMax(A, n);
  copyBack(A, inputArray);
}

考虑将这些注释转换为有效的javadoc。

/* Transforms A into a max-heap using a 'bottom-up' algorithm. */
public static void constructHeap(int[] A, int n, int i) {
  if (2 * i > n) {
    return;
  }
  constructHeap(A, n, 2 * i);
  constructHeap(A, n, 2 * i + 1);
  bubbleDown(A, n, i);
}

评论？

public static void bubbleDown(int[] A, int n, int i) {
  if (2 * i > n) {
    return;
  }
  int leftChild = 2 * i;
  int rightChild = 2 * i + 1;
  int max = leftChild;
  if (rightChild <= n && A[max] < A[rightChild]) {
    max = rightChild;
  }
  if (A[i] < A[max]) {
    int temp = A[i];
    A[i] = A[max];
    A[max] = temp;
    bubbleDown(A, n, max);
  }
}

  /* Performs a sequence of n 'remove-maximum' operations, storing the removed element at
     each step in successively smaller indices of A */

public static void removeMax(int[] A, int i) {
  if (i == 0) {
    return;
  }
  int temp = A[1];
  A[1] = A[i];
  constructHeap(A, i, 1);
  A[i] = temp;

所以你做O(n)递归调用？这会导致大n的StackOverflowException并损害您的运行时间。考虑将此尾递归转换为循环。

  removeMax(A, i - 1);
}

  /* Copies the sorted values in A back into inputArray, with inputArray[i] getting
     the value from A[i+1] */

public static void copyBack(int[] A, int[] inputArray) {

同上

  for (int i = 0; i < inputArray.length; i++) {
    inputArray[i] = A[i + 1];
  }
}