【QuickSort】单边快排思路及实现

思路：

        （1）首先定义一个递归函数：qucikSort(int [ ] arr,int l,int r)。函数的定义：给定一个数组arr，对它在[l,r]这个区间内的元素进行排序，从而使得整个数组在[l,r]这个区间内有序。

        （2）每次排序后得到一个索引p，索引p左边的元素都小于它，索引p右边的元素都大于它；此时我们就可以到[l,p - 1]、[p+1,r]这两个区间上继续排序，直至l>=r，区间内没有元素可排序为止。

        （3）对区间[l,r]排序时，首先确定基准元素pv（选择区间内最右的元素arr[r]），随后维护两个指针i、j，j指针用于寻找在[l,r - 1]区间内比pv小的元素，i指针用于在j指针找到比pv小的元素时，交换i、j两个指针指向元素的位置，同时i指针向右移动，为下一次位置交换做准备。

        （4）退出循环后，区间[0,i - 1]区间的所有元素都小于pv，[i,r - 1]区间的所有元素都大于pv。此时再交换i、r两个索引处的元素位置，基准元素被交换到了索引i处，基准元素的位置固定，后续不再参与排序。

Code：

        （1）generate方法，随机生成一个需要排序的数组：

//生成一个长度为n，元素值在1-v之间的整型数组private static int [] generate(int n,int v){int [] result = new int[n];for (int i = 0; i < n; i++) {result[i] = (int) ((Math.random() * v) + 1);}return result;}

        （2）递归函数quickSort：

//递归函数定义:对数组arr在[l,r]区间上的元素进行排序private static void quickSort(int [] arr,int l,int r){//l == r:区间内只有一个元素，不用排序//l > r:区间内没有元素，不用排序if(l >= r)return;//p:排好序的元素的索引，在arr[p]左边都是小于它的元素，右边都是大于它的元素int p = partition(arr,l,r);quickSort(arr,p + 1,r);quickSort(arr,l,p - 1);}

        （3）swap方法，交换两个元素arr[a]、arr[b]的位置：

//交换arr[a]、arr[b]两个元素的为止private static void swap(int [] arr,int a,int b){int temp = arr[a];arr[a] = arr[b];arr[b] = temp;}

        （4）关键的排序方法：
 

private static int partition(int [] arr,int l,int r){//选取[l,r]这个区间内，最右边的元素:arr[r]作为基准元素pvint pv = arr[r];//i:在[l,r]这个区间内，如果元素比基准元素小，那么这个元素就会被交换到i索引处int i = l;//从索引l开始遍历整个区间for(int j = l;j < r;j ++){//碰到比基准元素pv小的元素时if(arr[j] < pv) {//交换arr[i]、arr[j]两个元素的位置swap(arr, i, j);//i++是为了下一次交换位置做准备i++;}}//循环结束时，[l,r - 1]这个区间内，所有比基准元素小的元素都在[0,i - 1]这个区间上//此时交换arr[i]、arr[r]两个元素的位置，基准元素此时就是arr[i]//在arr[i]左边都是小于它的元素，在arr[i]右边都是大于它的元素swap(arr,i,r);//返回索引i，索引i上的元素位置不再发生变动return i;}

        （5）测试：

public static void main(String[] args) {//生成一个长度为10，元素值在1-10之间的数组int[] test = generate(10, 10);System.out.println("排序前："+Arrays.toString(test));quickSort(test,0,test.length - 1);System.out.println("排序后：" + Arrays.toString(test));}

        （6）输出结果：

总结：

        （1）首先明确base case：当l >= r时，数组不需要进行排序。

        （2）每次排序确定一个索引位置p，p左边都是小于它的元素，p右边都是大于它的元素，它不再参与排序。

        （3）索引位置p确定后，需要排序就只剩下区间：[l,p - 1]、[p + 1,r]，不断递归，直至l >= r时，排序结束。