快速排序

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤为：

从数列中挑出一个元素，称为 "基准"（pivot），
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

import java.util.Scanner;
public class quickSort {

	/**
	 * @param args
	 */
	public static void  quick(int sort[],int i,int j){
		int temp = sort[i];
		int middle = i;
		int low = i;
		int high = j;
		while(low < high){
			while((low < high)&&(sort[high] >= temp)){
				high = high - 1;
			}
			sort[middle] = sort[high];
			middle = high;
			while((low < high)&&(sort[low] <= temp)){
				low = low + 1;
			}
			sort[middle] = sort[low];
			middle = low;
		}
		sort[middle] = temp;
        if((middle - 1) > i)
		    quick(sort,i,middle-1);
        if((middle + 1) < j)
		    quick(sort,middle+1,j);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n;
		Scanner in = new Scanner(System.in);
		System.out.print("请输入排序的数字个数：");
		n = in.nextInt();
		int[] sort = new int[n];
		System.out.print("请输入" + n + "个整数：");
		for(int i = 0;i < n;i++)
		{
			sort[i] = in.nextInt();
		}
		quick(sort,0,n-1);
		System.out.println("快速排序后的结果为：");
        for(int k = 0;k < n;k++)
        	System.out.print(sort[k] + "  ");
	}
}