快速排序

设要排序的数组A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，

基本思想：从数组的末尾选择开始选择有比它小的数都放到它前面，从数组首部选择有比它大的数都放到它后面，直到所有的它将真个数组划分为左右两部分，其中左部小于它，右部大于它，这个过程称为一趟快速排序。

 

int a[] = { 45, 12, 11, 32, 56, 11, 8, 30, 3 };

一次排序之后：{3, 12, 11, 32, 30, 11, 8, 45, 56}

然后分别对两个数组进行递归的排序

package org.mino.sort;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 快速排序
 * @author DingJie
 */
public class QuickSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[] = { 45, 12, 11, 32, 56, 11, 8, 30, 3 };
		System.out.println("插入排序之前:");
		for(int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
		QuickSort qs = new QuickSort();
		qs.sort(a, 0, a.length-1);
		System.out.println("插入排序之后:");
		for(int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}
	/**
	 * 快速排序每次划分
s	 */
	private int partition(int sortArray[],int low,int hight)
    {
	        int key = sortArray[low];
	        while(low<hight)
	        {
	            while(low<hight && sortArray[hight]>=key)//从高往低
	                hight--;
	            sortArray[low] = sortArray[hight];
	            while(low<hight && sortArray[low]<=key)
	                low++;
	            sortArray[hight] = sortArray[low];
	        }
	        sortArray[low] = key;
	        System.out.println(Arrays.toString(sortArray));
	        return low;
	 }
	
	/**
	 * 快速排序
	 * @param data
	 * @param low
	 * @param hight
	 */
	public void sort(int []data, int low, int hight)
    {
	    if(low<hight)
		{
		   int result = partition(data,low,hight);
		   sort(data,low,result-1);
		   sort(data,result+1,hight);
		}
	}


}