快速排序

快速排序采用分治策略，选一个基准数，比基准数小的放在基准数的左边，比基准数大的放在右边，在对两部分数据进行快速排序，采用递归的方法直至数据全部变成有序的序列。

1.选择一个基准数据，一般为第一个数据，
2.设置变量i = left,j = right
3.从右向左比较数据是否大于基准数，是则j--,否则a[i]=a[j]
4.从左向右比较判断数据是否小于基准数，是则i++，否则a[j]=a[i]
5.循环3.4步骤，直到i=j,将基准数填如a[i]

public static int partion(int[] arr, int left, int right) {
    int temp = arr[left];
    int i = left;
    int j = right;
    while(i<j) {
        while(temp<arr[j]&&i<j) {
            j--;
        }
        if(i<j) {
            arr[i] = arr[j];
            i++;
        }
        while(temp>arr[i]&&i<j) {
            i++;
        }
        if(i<j) {
            arr[j] = arr[i];
            j--;
        }   
    }
    arr[i] = temp;
    return i;   
}
public static void quicksort(int[] arr, int left, int right) {
    if(left < right) {
        int mid = QuickSort.partion(arr, left, right);
        quicksort(arr,left,mid);
        quicksort(arr,mid+1,right);
    }
}   
public static void main(String[] args) {
    int[] arr = {62,23,51,46,85,42,15};
    QuickSort.quicksort(arr, 0, arr.length-1);
    System.out.println(Arrays.toString(arr));
}

快速排序最好情况
每次分区时都恰好分成刚好分为几近相等的两个子序列