Java实现快速排序_快速排序以中间数作为基准值java

算法简介
快速排序(Quicksort）是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
基本思想
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

代码是以中间值为基值进行快速排序：

 /**
     *
     * @param array 待排序的数组，有可能是左右子数组
     * @param left 待排序的数组左边下标
     * @param right 待排序的数组右边下标
     */
    public static void quickSort(int[] array,int left,int right){
        int l = left;//左下标
        int r = right;//右下标
        int pivot = array[(left+right)/2];//数组的中轴值
        int temp=0;
        //while循环的目的是让比 pivot值小放到左边l
        //比 pivot值大放到右边
        while (l<r){//当左边的下标大于等于右边的下标结束排序

           //在pivot的左边一直找,找到大于等于pivot值,才退出
            while (array[l]<pivot){
                l++;//l=2
            }
            //在pivot的右边一直找,找到大小于等于pivot值,才退出
            while (array[r]>pivot){
                r--;//r=6
            }
            //这两个值找到了，最坏情况左右两边移动到pivot所在的下标
            //如果l>=r说明pivot的左石两的值，已经按照左边全部是小于等于pivot值，
            // 右边全部是大于等于pivot值完成了排序
            if (l>=r){
                break;
            }
            //交换左右两边的值
            temp = array[l];
            array[l] = array[r];
            array[r] = temp;
            //如果交换完后，发现这个arr[l] ==pivot值相等r--，前移
            //防止交换的两个数都等于pivot,之后出现死循环。两个数一直交换。
            if (array[l]==pivot){
                r--;
            }
            //如果交换完后，发现这个arr[r]== pivot值相等l++，后移
            if (array[r]==pivot){
                l++;
            }
        }
        //如果l==r，必须l++, r--，否则为出现栈溢出，
        // 且r减一作为左子数组的结束下标，l++作为右边子数组的开始下标
        if (l==r){
            l++;
            r--;
        }
        //向左递归
        if (left<r){
            quickSort(array,left,r);
        }
        //向右递归
        if (right>l){
            quickSort(array,l,right);
        }
    }
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

测试代码：

 int[] array = {-9,78,12,0,6,23,-567,70,2};
        QuickSort.quickSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
1
2
3