快速排序---Hoare法

任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。

//有个数组arr
int[] arr={6,1,2,7,9,3,4,5,10,8};

最左边下标为left 最右边下标为right 

我们先取最左边的数为基准值  tem=arr[0];

right往左走 如果下标的值比tem大，则继续往左走   ，反之停止（相等也停止）

left往右走，如果遇到比tem大的值则停下，然后和right下标的值交换位置，然后right和left继续走；

当left和right下标相遇时，此时它俩的值和tem值交换位置，然后返回此时left或者right的位置下标。此时返回的下标为基准值 key。

我们以key下标为基准值向左和向右分割。左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

通过递归算法，相当于一棵二叉树的遍历；

public class Main {
    public static void quick(int[] array,int left,int right){
        if (left>=right)  return ;
        int key = partitionHoare(array,left,right);
        quick(array, left, key);
        quick(array,key+1,right);
    }
    private static int partitionHoare(int[] array, int left, int right) {
        int i=left;
        int tem=array[left];
        while(left<right){
            while(left<right && array[right]>=tem){
                right--;
            }

            while(left<right && array[left]<=tem){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,i,left);
        return left;
    }
    private  static void swap(int[] arr ,int a,int b){
        int tem=arr[a];
        arr[a]=arr[b];
        arr[b]=tem;
    }

    public static void main(String[] args) {
        int[] array={2,7,6,3,6,4,8,5};
        quick(array,0,array.length-1);
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }

    }
}

运行结果：