基于泛型的快速排序工具类的一些想法

快速排序是排序算法中最基本的一种方法，《算法导论》一书在第七章就介绍了这种排序，基本算法实现的伪代码如下：

QUICKSORT(A,p,r)
  if p<r
    then q←PARTITION(A,p,r)
      QUICKSORT(A,p,q-1);
      QUICKSORT(A,p,q+1);

PARTITION(A,p,r)
  x←A[r]
  i←p-1
  for j←p to r←1
    do if A[j]<=x
      then i←i+1
        exchange A[i]←→A[j]
  exchange A[i+1]←→A[r]

算法本身没说什么好说的，这里主要是想说一下如何做一个快速排序的工具类。
----------------------------------------------------------------------
实际coder中需要排序的对象可能并不是一个固定的类型或者也不一定是基本类型，所以我们考虑用泛型的思路，给出一种实现

    public static <T> void quickSort(T[] a, int low, int high) {
        int pivot = position(a, low, high);
        if (pivot > low + 1)
            quickSort(a, low, pivot - 1);
        if (pivot < high - 1)
            quickSort(a, pivot + 1, high);
    }

    private static <T> int position(T[] a, int low, int high) {
        while (low < high) {
            while (low < high
                    && a[high].toString().compareTo(a[low].toString()) > 0) {
                high--;
            }
            if (a[high].toString().compareTo(a[low].toString()) <= 0) {
                T temp = a[low];
                a[low] = a[high];
                a[high] = temp;
            }
            while (low < high
                    && a[high].toString().compareTo(a[low].toString()) > 0) {
                low++;
            }
            if (a[high].toString().compareTo(a[low].toString()) <= 0) {
                T temp = a[low];
                a[low] = a[high];
                a[high] = temp;
            }
        }
        return low;
    }

这是升序的快速排序，如果需要降序，无外乎“大于”变“小于”一番。

这个工具类本身还是有不少缺点，例如强制需要排序对象类T中需要实现object中的tostring方法，并在这个方法中返回排序关键词的内容，比如这样

class Id_Content {
    private int id;

    private String content;

    private float rate = 0;

    public Id_Content() {
        // TODO Auto-generated constructor stub
    }

    public Id_Content(int counter, String line) {
        // TODO Auto-generated constructor stub
        this.setId(counter);
        this.setContent(line);
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getContent() {
        return content;
    }

    public void setContent(String content) {
        this.content = content;
    }

    public float getRate() {
        return rate;
    }

    public void setRate(float rate) {
        this.rate = rate;
    }

    @Override
    public String toString() {
        // TODO Auto-generated method stub
        return rate + "";
    }

}

这点确实很不“工具类”，只是笔者暂时也没有想到什么解决思路。


另外，快速排序是一个很耗空间的排序方式，具体在java中很可能出现堆栈溢出的问题（最坏情况，原序列初始排列混乱，导致划分为两部分是严重不平衡，结果就是递归的次数增加），vm对于每个线程的堆栈设置为1m，建议利用-xss堆栈设置将这个默认值扩大。