快速排序的代码

package introductionToAlgorithms;

 

public class QuickSort {

 

static int[] a = {3,1,7,4,10,6,8,9,2,5};

static int findPivot(int low,int high) {

int i = low, j = high+1;

int pivotValue = a[low];

while( true ) {

while( a[--j] > pivotValue );

System.out.println(" j = " + j);

while( i < j && a[++i] < pivotValue ); 

System.out.println(" i = " + i);

 

if( i >= j ) break;

int temp = a[i]; 

a[i] = a[j];

a[j] = temp;

}

a[low] = a[j];

a[j] = pivotValue;

return j;

}

static void quickSort(int low, int high){

if( low < high ) {

int pivot = findPivot(low,high);

quickSort(low,pivot-1);

quickSort(pivot+1,high);

}

}

 

static void printArray() {

for(int value: a)

System.out.print(value + "  ");

System.out.println();

}

 

public static void main(String[] args) {

 

printArray();

quickSort(0,a.length-1);

printArray();

}

}

评论

1 楼 chriszeng87 2011-06-02  

晚上闲着没事，又写了一遍：

public class LongestArithmeticSequence {
	private static int[] array = {1,3,0,5,-1,6};
	
	private int findPivot(int begin, int end) {
		int pivotValue = array[begin];
		int i = begin , j = end;
		while(true) {
			while(array[++i] < pivotValue && i<=end);
			while(array[--j] > pivotValue);
			if(i>=j) break;
			int temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
		array[begin] = array[j];
		array[j] = pivotValue;
		return j;
	}
	
	
	
	private void quickSort(int begin, int end) {
		if( begin < end-1 ) {
			int pivot = findPivot(begin,end);
			quickSort(begin,pivot);
			quickSort(pivot+1,end);
		}
	}

	public static void main(String[] args) {
		LongestArithmeticSequence longestArithmeticSequence = new LongestArithmeticSequence();
		longestArithmeticSequence.quickSort(0, array.length);
		
		for(int value: array) {
			System.out.print(value+"  ");
		}

	}

}