排序--快速排序

快速排序是一个分治和递归的一个思想。
快速排序思想是折半查找,从最右边开始查找，找到一个比k值小的然后对换，再从左边开始查找，找到一个比k值大的，然后对换。继续循环就完成第一次排序。拿到返回的位置后，左右两边开始递归。

package quicksort;

import java.util.Arrays;


/**
* @author liyu
*
*/
public class Sort {

public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = {11, 2, 6, 15 , 16 ,8 ,9 ,3, 19, 20};
//int arr[] = {11, 2, 6, 15 , 16 ,8,8 ,9 ,3, 19, 20};
QuickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}

private static void QuickSort(int[] arr, int i, int j) {
// TODO Auto-generated method stub
int p = 0;
if(i<j){
p = partion(arr,i,j);
QuickSort(arr, p+1, j);
QuickSort(arr, i, p-1);
}
}
public static int partion(int[] arr,int i, int j){
//11 2 6 15  16 8 9 3 19 20 --->11 |3  2 6 15  16 8 9 _ 19 20 ----> 11 |3  2 6 _  16 8 9 15 19 20-->11 |3 2 6 9 16 8 _ 15 19 20
//-->11 |3  2 6 9 _ 8 16 15 19 20-->11 |3  2 6 9 8 11 16 15 19 20
int k = arr[i];
while(i<j){
//从右边边开始寻找一个比k小的值
while (i<j&&arr[j]>=k) j--;
//找到比k小的值后替换位置
arr[i] = arr[j];
while(i<j&&arr[i]<k)  i++;
arr[j] = arr[i];
}
arr[i] = k;
return i;
}



}