快速排序---Hoare法

快速排序是Hoare于1962年提出的一种二叉树布局的交换排序方法，其根本头脑为：任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序聚集分割成两子序列，左子序列中全部元素均小于基准值，右子序列中全部元素均大于基准值，然后最左右子序列重复该过程，直到全部元素都分列在相应位置上为止。

2. //有个数组arr
3. 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下标为基准值向左和向右分割。左子序列中全部元素均小于基准值，右子序列中全部元素均大于基准值，然后最左右子序列重复该过程，直到全部元素都分列在相应位置上为止。
通过递归算法，相当于一棵二叉树的遍历；

2. public class Main {
3.     public static void quick(int[] array,int left,int right){
4.         if (left>=right)  return ;
5.         int key = partitionHoare(array,left,right);
6.         quick(array, left, key);
7.         quick(array,key+1,right);
8.     }
9.     private static int partitionHoare(int[] array, int left, int right) {
10.         int i=left;
11.         int tem=array[left];
12.         while(left<right){
13.             while(left<right && array[right]>=tem){
14.                 right--;
15.             }
17.             while(left<right && array[left]<=tem){
18.                 left++;
19.             }
20.             swap(array,left,right);
21.         }
22.         swap(array,i,left);
23.         return left;
24.     }
25.     private  static void swap(int[] arr ,int a,int b){
26.         int tem=arr[a];
27.         arr[a]=arr[b];
28.         arr[b]=tem;
29.     }
31.     public static void main(String[] args) {
32.         int[] array={2,7,6,3,6,4,8,5};
33.         quick(array,0,array.length-1);
34.         for (int i=0;i<array.length;i++){
35.             System.out.print(array[i]+" ");
36.         }
38.     }
39. }

复制代码

运行效果：