quicksort.java

《算法设计与分析》王晓东编著

import java.util.Scanner;


public class QuickSort {

	public static void qSort(int[] array,int p,int r){
		if(p<r){
			int q = partition(array,p,r);
			qSort(array,p,q-1);
			qSort(array,q+1,r);
		}
		 
	}
	public static int partition(int[] array,int p,int r){
		int i=p;int j=r+1;
		int x = array[p];
		while(true){
			while(array[++i]<x && i<r);
			while(array[--j]>x);
			if(i>=j) break;
			int temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
		array[p] = array[j];
		array[j] = x;
		return j;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		System.out.print("Please input the length of the array:");
		int n = in.nextInt();
		int[] array = new int[n];
		for(int i=0;i<n;i++){
			System.out.print("array["+i+"] = ");
			array[i] = in.nextInt();
		}
		qSort(array,0,n-1);
		System.out.println("The result of mergeSort:");
		for(int i=0;i<n;i++){
			System.out.print(array[i]+"\t");
		}
	}

	

}