java快速排序

快速排序的原理

选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素

一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。

package com.cn.test.quicksort;


public class QuickSort {
	
	//测试：
	public static void main(String[] args) {
		int[] numbers={5,2,6,4,7,9,10,5};
		System.out.print("排序前：");
		printArr(numbers);
		
		quick(numbers);
		System.out.print("快速排序后：");
        printArr(numbers);
	}
	
	//打印函数：
	public static void printArr(int[] numbers){
		for(int i=0;i0){
			quickSort(numbers, 0, numbers.length-1);
		}
	}
	
	/**
     * 
     * @param numbers 带排序数组
     * @param low  开始位置
     * @param high 结束位置
     */
    public static void quickSort(int[] numbers,int low,int high)
    {
        if(low < high){
	        int middle = getMiddle(numbers,low,high); //将numbers数组进行一分为二
	        quickSort(numbers, low, middle-1);   //对低字段表进行递归排序
	        quickSort(numbers, middle+1, high); //对高字段表进行递归排序
        }
    
    }
    
   /**
     * 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
     * 
     * @param numbers 带查找数组
     * @param low   开始位置
     * @param high  结束位置
     * @return  中轴所在位置
     */
    public static int getMiddle(int[] numbers, int low,int high){
        int temp = numbers[low]; //数组的第一个作为中轴
	    while(low < high){
	        while(low < high && numbers[high] >=temp){//从右向左找第一个小于等于基准值得index
	            high--;
	        }
	        numbers[low] = numbers[high];//比中轴小的记录移到低端
	        while(low < high && numbers[low]