可以按这种方式来递规吧:
int parttion(int low,int high)
{
return low;
}
void QSort(int low,int high)
{
p=parttion(low,high);
QSort(low,p-1);
QSort(p+1,higt);
}
main()
{
QSort(1,array.length);
}
int parttion(int low,int high)
{
return low;
}
void QSort(int low,int high)
{
p=parttion(low,high);
QSort(low,p-1);
QSort(p+1,higt);
}
main()
{
QSort(1,array.length);
}
{
return low;
}
void QSort(int low,int high)
{
if(low<high){
p=parttion(low,high);
QSort(low,p-1);
QSort(p+1,higt);
}
}
main()
{
QSort(1,array.length);
}
if(i>j) {
System.out.println("break!!!!!!!");
break;
}
===
改为i>=j\\\\\\\\\\\\\
另外你写的程序的确让人看不懂 :(
//private int pivot;
private int[] a;
public QuickSort(int[] anArray) {
a = anArray;
} /**
Sorts the array managed by this sorter
*/
public void sort() {
sort(0, a.length - 1);
} public void sort(int first, int last) {
if (first < last) { //<=======就在这里!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
int pivot = median(first, last);
// System.out.println("pivot is"+pivot);
//place pivot at position right
// swap( (first + last) / 2, last);
//Bigin partitioning
int i = first;
int j = last ;
while (true) {
while (a[i] < pivot && i<last) {
i++;
}
while (pivot < a[j] && j>first) {
j--;
}
System.out.println("i=" + i);
System.out.println("j=" + j);
if (i >= j) {
System.out.println("break!!!!!!!");
break;
}
swap(i, j);
System.out.println("after swap:");
System.out.println("i=" + i);
System.out.println("j=" + j);
for (int k = 0; k < a.length; k++)
System.out.print(a[k] + ",");
System.out.println("================");
}
// swap(i, last); //restore pivot
sort(first, (i - 1)); //sort samll elements
sort( (i + 1), last); //sort large elements
}
else
return;
} /**
* return median of left,center and right
* Order thest and hide the pivot
* @param left
* @param right
* @return
*/
public int median(int left, int right) {
int center = (left + right) / 2;
return a[center];
} /**
Swaps two entries of the array.
@param i the first position to swap
@param j the second position to swap
*/
private void swap(int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
} public static void main(String args[]) {
int size = 10;
int a[];
a = new int[] {
8,1,4,9,6,3,5,2,7,0};
//long begin=System.currentTimeMillis();
QuickSort b = new QuickSort(a);
b.sort();
//long end=System.currentTimeMillis();
//System.out.println("the runtime is "+(end-begin)+"ms");
for (int i = 0; i < b.a.length; i++)
System.out.print(b.a[i] + ","); }}
public static void main(String[] args){
int[] a = new int[] {8,1,4,9,6,3,5,2,7,0};
QSort(a,0,9);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+",");
}
}
static int Partition(int[] list, int low, int high) {
// 交换顺序表list中子序列list.r[low..high]的记录,使枢轴记录到位,
// 并返回其所在位置,此时,在它之前(后)的记录均不大(小)于它
int pivotkey;
int temp = list[low]; // 用子表的第一个记录作枢轴记录
pivotkey = list[low]; // 枢轴记录关键字
while (low<high) { // 从表的两端交替地向中间扫描
while (low<high && list[high]>=pivotkey) --high;
list[low] = list[high]; // 将比枢轴记录小的记录移到低端
while (low<high && list[low]<=pivotkey) ++low;
list[high] = list[low]; // 将比枢轴记录大的记录移到高端
}
list[low] = temp; // 枢轴记录到位
return low; // 返回枢轴位置
}
static void QSort(int[] list, int low, int high) {
// 对顺序表list中的子序列list.r[low..high]进行快速排序
int pivotloc;
if (low < high) { // 长度大于1
pivotloc = Partition(list, low, high); // 将list.r[low..high]一分为二
QSort(list, low, pivotloc-1); // 对低子表递归排序,pivotloc是枢轴位置
QSort(list, pivotloc+1, high); // 对高子表递归排序
}
} }