HeapSort/IntrospectiveSort 数组部分 Java 实现

Question

目前正在研究排序算法，需要实现HeapSort和Introspective Sort

我想我已经成功实现了 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);
    }
  }

下移代码为：

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;
  }

这2个方法应该完全没问题，我已经测试了很多次，我从来没有遇到过任何问题。

我也在尝试从这2个方法入手实现Introspective Sort，我的代码是这样的：

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;
      }
    }
  }

我认为上面的代码也很好，假设方法 isort 和 hsortAux 工作正常。在我的测试中，我注意到只有在调用堆排序时它才会失败。当我使用 tukey 近似值来确定主元索引时，以及当我选择一个随机主元时，代码都应该工作（目标是让它工作），例如总是数组的第一个元素。使用 QuickSort 的分区应该是正确的，因为我已经尝试了许多快速排序实现并且它们都有效，而且正如我已经说过的那样，代码在未调用堆排序时有效。分区实际上是另一种完美方法中快速排序的复制粘贴。

我确信 isort 和 tukeyApproximation 方法按预期工作，因为我单独测试了它们并在快速排序实现上进行了测试，它们工作得很好。

但是我似乎无法实现堆排序（称为 hsortAux 的方法），该堆排序仅在最小值和最大值之间的数组部分上执行其工作。我花了几个小时在这里和 Google 上寻找答案，我试图通过查看其他人的代码来实现我自己的版本，但我失败了很多次，我在这里浪费你的时间:)。一旦我设法使一个工作 heapSort 但是当 tukey 近似没有选择枢轴时它似乎没有工作（例如数组的第一个元素或部分中的随机元素）。

这是我当前的 hsortAux 代码，源自原始的 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;
  }

最后我所做的只是更改 while 条件，我仍在尝试弄清楚为什么现在它可以工作而以前没有。

感谢大家

HeapSort/IntrospectiveSort 数组部分 Java 实现

HeapSort/IntrospectiveSort on Array Portion Java implementation

java

arrays

sorting

heapsort

introsort