快排

1.0定义

快速排序（Quicksort）是对冒泡排序的一种改进。基本思想****是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

2.个人理解

快排运用了分而治之的思想，先把数组分成两个区域，一个是小于value的区域，一个是大于value的区域，在对这两个区域里的进行分解，直到只有一个元素才停止，先用sort算法分成两个区域，并把value的下标取出，然后再分成左区域和右区域，再这里面进行找下标再区分，直到l>=r

3.图片讲解

eEcqte.md.png

4.0代码讲解

首先要两个代码，一个是不断进行分左区域和区域，另一个就是分大于value和小于value，最后的出下标返回来进行左右划分

4.1不断划分左右区域

条件终止是l》=r

1
2
3
4
5
6
7
8
9
public static void quickSort2(int[] arr,int left,int right){
        if (left>=right){
            return;
        }
        int v=qucik(arr,left,right);
        quickSort2(arr,left,v-1);
        quickSort2(arr,v+1,right);

    }

4.2获取下标，并同时对数组进行分区域

首先设置l=left+1，r=right，l往右移动，r往左移动，value先设置为arr【left】，当arr【l】>value时停止否则l++，r就是arr【r】<value时，停止，否则就是r–，当l与r都停止时候就把arr【l】yuarr【r】进行交换，如何l++，r–停止条件也是l>r。跳出循环时，把arr【r】与arr【left】进行交换，最后把r返回就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static int qucik(int[] arr,int left,int right){
        int l=left+1;
        int r=right;
        int val=arr[left];
        while (l<=r){
            while (l<=right&&arr[l]<val){
                l++;
            }
            while (r>=left+1&&arr[r]>val){
                r--;
            }
            if (l>r){
                //说明已经排好了
                break;
            }
            int tem=arr[l];
            arr[l]=arr[r];
            arr[r]=tem;
            l++;
            r--;

        }
        //跳出循环把，r与left交换，因为是以left威大小来分的
        int tem=arr[left];
        arr[left]=arr[r];
        arr[r]=tem;
        return r;



    }