快速排序

什么是快速排序呢？

同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。
不同的是，冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。
该方法的基本思想是：是分冶，再通过递归将元素不停的分组（重复上述步骤），直至剩下一个元素返回；

1．先从数列中取出一个数作为基准数
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它
的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

import java.util.Arrays;

public class 快速 {

public static void quickSort(int[] arr, int L, int R) {
    if(L<R) {
        swap(arr, L + (int)(Math.random() * (R - L +1)), R);
        int[] p = partition(arr, L, R);
        quickSort(arr, L, p[0]-1);
        quickSort(arr, p[1] + 1, R);
    }
}

public  static int[] partition(int[] arr, int L, int R) {
    int start = L - 1;
    int end = R;
    while(L < end) {
        if(arr[L] < arr[R]) {
            swap(arr, ++start, L++);
        }
        else if(arr[L] > arr[R]) {
            swap(arr, --end, L);
        }
        else {
            L++;
        }
    }
    swap(arr, end, R);
    return new int[] {start + 1 ,end};
}

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

public static void main(String[] args) {
    int [] arr = {6,9,8,5,4,7,2,6,12,3,65};
    quickSort(arr, 0, arr.length-1);
    System.out.println(Arrays.toString(arr));
}

}