package sort;

//快速排序

/**

* 快速排序的基本思想是，通过一轮的排序将序列分割成独立的两部分，

* 其中一部分序列的关键字（这里主要用值来表示）均比另一部分关键字小

*/

public class QuickSort {

public void sort(Comparable[] a, int lo, int hi) {

if (lo >= hi) return;

int j = partition(a, lo, hi);

sort(a, lo, j-1);

sort(a, j+1, hi);

}

private int partition(Comparable[] a, int lo, int hi) {

int i = lo, j = hi+1;

//int mid = lo + (lo + hi)/2;

Comparable re = a[lo];

//以下代码错误:

/*while (i < j) {

if (a[i].compareTo(re) < 0) {

i++;

} else if (a[j].compareTo(re) > 0) {

j--;

} else {

exch(a, i, j);

}

}*/

while (true) {

while (a[++i].compareTo(re) < 0 && i < hi) ;//&&后面代码不能省略

while (a[--j].compareTo(re) > 0 && j > lo) ;

if (i >= j) break;

exch(a, i, j);

}

exch(a, lo, j);

return j;

}

private void exch(Comparable[] a, int i, int j) {

Comparable temp = a[i];

a[i] = a[j];

a[j] = temp;

}

}