数组部分Java实现的HeapSort/IntrospectiveSort

Question

我目前正在研究排序算法，需要实现HeapSort和内省排序。

我认为我已经成功地实现了HeapSort (代码工作，在数以百万计随机大小的随机数组上试用，总是有效的)，下面是我的代码：

  public static <T extends Comparable<? super T>> void hsort(T[] a) {
    int n = a.length;
    if(n < 2) return;
    /* Heapify */
    for(int i = (n-2)/2; i >= 0; i--)
      moveDown(a, i, n);
    for(int i = n-1; i > 0; i--) {
      swap(a, 0, i);
      moveDown(a, 0, i);
    }
  }

moveDown代码是：

private static <T extends Comparable <? super T>> void moveDown(T[] a, int i, int max) {
    T e = a[i];
    int j;  /* Son index */
    while((j = (2*i)+1) < max) {
      if(j+1 < max && a[j+1].compareTo(a[j]) > 0) j++; /* Biggest son */
      if(e.compareTo(a[j]) >= 0) break;
      a[i] = a[j];
      i = j;
    }
    a[i] = e;
  }

这两种方法完全可以正常工作，我已经测试过它们好几次了，我从来没有遇到过任何问题。

我还试图从这两个方法开始并实现内省排序，我的代码如下所示：

public static <T extends Comparable<? super T>> void introSort(T[] a) {
    int size = a.length;
    if(size < 2) return;
    int log = Integer.SIZE - Integer.numberOfLeadingZeros(size);
    introSort(a, 0, size-1, 2*log);
  }

private static <T extends Comparable<? super T>> void introSort(T[] a, int min, int max, int lev) {
    if(max - min < ISORT_THRESHOLD) isort(a, min, max); // Small intervall
    else if(lev == 0) hsortAux(a, min, max); // HeapSort on Array Portion
    else {
      // QuickSort
      while (min < max) {
        lev--;
        /* Tukey approximation */
        int t = tukeyApproximation(a, min, max-1);
        //t = min; Ignore this for now and read below this code
        T p = a[t];
        int i = min, j = max;
        do {
          while(a[i].compareTo(p) < 0) i++;
          while(a[j].compareTo(p) > 0) j--;
          if(i <= j) {
            swap(a, i, j);
            i++; j--;
          }
        } while(i <= j);
        introSort(a, min, j, lev);
        min = i;
      }
    }
  }

我认为上面的代码也很好，假设方法是短的和hsortAux工作得很好。在我的测试中，我注意到只有当堆排序被调用时它才会失败。当我使用tukey近似来确定枢轴索引时，以及当我选择一个随机的枢轴(例如，总是数组的第一个元素)时，代码都应该工作(目标是使它工作)。使用QuickSort的分区应该是正确的，因为我已经尝试过许多快速排序实现，它们都可以工作，正如我已经说过的，当堆排序不被调用时，代码可以工作。分区实际上是来自另一种方法中的快速排序的复制，而后者工作非常完美。

我确信这些方法是短的和tukeyApproximation的，因为我已经单独测试了它们，并在快速排序实现上进行了测试，它们工作得很好。

但是，我似乎无法实现仅在min和max之间的数组部分执行其工作的堆排序(称为hsortAux)。我花了几个小时在这里和谷歌上寻找答案，我试图通过查看别人的代码来实现我自己的版本，但我多次失败了，在这里我在浪费你的时间:)。有一次，我成功地制作了一个工作的heapSort，但当枢轴没有被tukey近似所选择时(例如数组的第一个元素或部分中的一个随机元素)，它似乎不起作用。

下面是我当前的hsortAux代码，它来自于origianl hsortAux：

private static <T extends Comparable<? super T>> void hsortAux(T[] a, int min, int max) {
    for(int i = (min + max - 1)/2 ; i >= min; i--)
      moveDownAux(a, min, i, max+1);
    for(int i = max; i > min; i--) {
      swap(a, min, i);
      moveDownAux(a, min, min, i);
    }
  }

moveDownAux应该是只在数组部分工作的moveDown方法，但是我真的不知道如何实现它，我尝试使用以前的moveDown方法，但是它显然根本不起作用。在实现moveDownAux时，我甚至不确定是否需要名为min的变量。

下面是我当前的moveDownAux方法：

private static <T extends Comparable<? super T>> void moveDownAux(T[] a, int min, int i, int max) {
    T e = a[i];
    int j;  /* Son */
    while((j = (2*i)+1) < max-1) {
      if(j+1 < max && a[j+1].compareTo(a[j]) > 0) j++; /* Biggest Son */
      if(e.compareTo(a[j]) >= 0) break;
      a[i] = a[j];
      i = j;
    }
    a[i] = e;
  }

谢谢你的时间和答案

Answer 1

所以在经历了几周的痛苦之后，我终于明白了到底是怎么回事。下面的moveDownAux方法似乎一切都很好：

private static <T extends Comparable<? super T>> void moveDownAux(T[] a, int min, int i, int max) {
    T e = a[i];
    int j;
    while((j = (2*i)+1 - min) < max) {
      if(j+1 < max && a[j+1].compareTo(a[j]) > 0) j++; /* Biggest son */
      if(e.compareTo(a[j]) >= 0) break;
      a[i] = a[j];
      i = j;
    }
    a[i] = e;
  }

最后，我所做的只是改变了时间条件，我仍然在努力弄清楚为什么它现在起作用了，而在它没有起作用之前。

感谢每个人