QuickSort of Comparable[]

Question

下面是我创建的QuickSort类的代码。

public class QuickSort {

        public static void sort(Comparable[] a) {
            quicksort(a, 0, a.length-1);
        }

        private static void quicksort(Comparable[] a, int lo, int hi) {
            if(lo >= hi) return;
            int pi = partition(a, lo, hi);
            quicksort(a, lo, pi-1);
            quicksort(a, pi+1, hi);
        }

        private static int partition(Comparable[] a, int lo, int hi) {
            int i = lo + 1;
            int j = hi;

            while(i <= j) {
                if(a[i].compareTo(a[lo]) <= 0) { 
                    i++; 
                }
                else if(a[j].compareTo(a[lo]) > 0) { 
                    j--;
                }
                else if(j < i) {
                    break;
                }
                else
                    exchange(a, i, j);
            }
            exchange(a, lo, j);
            return j;
        }

        private static void exchange(Object[] a, int i, int j) {
            Object tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
}

代码通过了一些简单的测试(包括重复的值)。我想知道我的代码中有什么bug吗？有什么地方可以改进吗？

Answer 1

每个方法的Javadoc都会很好。

将签名更改为<T extends Comparable<T>> void sort(T[] a)。

public static void sort(Comparable[] a) {

指定范围的标准方法从包含到排它。

  quicksort(a, 0, a.length - 1);
}

private static void quicksort(Comparable[] a, int lo, int hi) {

为什么不“高”和“低”呢？

  if (lo >= hi) {

您的代码从不使用lo > hi调用快速排序。在这种情况下，最好抛出一个IllegalArgument异常。

    return;
  }
  int pi = partition(a, lo, hi);
  quicksort(a, lo, pi - 1);
  quicksort(a, pi + 1, hi);
}

private static int partition(Comparable[] a, int lo, int hi) {
  int i = lo + 1;
  int j = hi;

您选择第一个元素作为关键。选择作为枢轴的元素在一个恒定的位置允许构造一个反测试，这是一个数组，您的排序工作在O(n^2)中。在特定情况下，反测试非常简单--按降序排列的数组，例如(5、4、3、2、1)。

  while (i <= j) {
    if (a[i].compareTo(a[lo]) <= 0) {
      i++;
    } else if (a[j].compareTo(a[lo]) > 0) {
      j--;
    } else if (j < i) {
      break;
    } else {
      exchange(a, i, j);
    }
  }
  exchange(a, lo, j);
  return j;
}

最好把它命名为交换。

private static void exchange(Object[] a, int i, int j) {
  Object tmp = a[i];
  a[i] = a[j];
  a[j] = tmp;
}

Answer 2

只有三个简短的注解：

1. 您可以使用以下方法声明来修正编译器警告:公共静态> void (T[] a)私有静态> void (T[] a，int，int )私有静态> int分区(T[] a，int lo，int hi)
2. 为了获得更好的可读性，我将a重命名为input或data。
3. exchange通常被称为swap。我认为更多的开发人员会对后者感到熟悉。