快速排序 (Quick Sort)

思路

1.先从数组里找出基准数。2.分治，将数组中比基准数小的放一边，比基准数大的放另外一边（这样的话就是以基准数为中心，将数组分成了两段了）。3.将分出的左右区间继续上面1，2的步骤，直到每个区间都有一个数字。
这里简单看看上面的思路就可以看得出，快排其实也是用了分治法的思维来排序，从而达到了O(nlogn)的时间复杂度。

接着我用图来一步一步解释一下快速排序的步骤

假设现在有一个待排序的数组

int[] arr = {7, 5, 6, 9, 3, 1, 4};

找基准数（这里假设我们把每次的最左边的数来作为基准数） 这里以7作为基准数，然后用双指针标记数组的左边和右边，依次往中间判断。

第一步是4比7小，将4赋值给左指针，紧接着往右移动被赋值好的指针。

第二步是5比7小，继续后移指针。

第三步是6比7小，继续后移指针。

第四步是9比7大，将9赋值给右指针，同时右指针向前移动。

第五步是1比7小，将1赋值给左指针，同时左指针向后移动。

第六步是3比7小，指针直接往后移动。

第七步发现指针重叠了（其实就是找到了基准数的位置了，把7放在重叠的位置）
这样第一轮的基准数就找到了，接下来只需要将数组按新的基准数分区，找到新的基准数，然后一直重复上面的步骤就可以完成快速排序了。

问题

快速排序的话如果一直按以最左边来作为基准数的话是有问题的，假如说数组本身就是倒序的

int[] arr = { 9, 8, 7, 6, 5, 4};

那么其实这么找的话，快速排序的时间复杂度就跟O(n2)没什么区别，所以这里的话是最好把每次选择的基准数作为随机数来选择。这里的话我简单就用了下中位数来作为基准数。

代码

public class QuickSort {

    public static void main(String[] args) {

        int[] arr = { 7, 5, 6, 9, 3, 1, 4 };

        quickSort(arr, 0, arr.length - 1);




        System.out.println("排序后:");

        for (int i : arr) {

            System.out.println(i);

        }

    }




    private static void quickSort(int[] arr, int left, int right) {

        // 在左右指针没有重合的时候继续分治的找

        if(left < right) {




            // 这里找到基准数

            int index = getIndex(arr, left, right);

            // 根据基准数继续分成左右两个区间找（分治法的思维）

            quickSort(arr, left, index-1);

            quickSort(arr, index+1, right);

        }

    }




    private static int getIndex(int[] arr, int left, int right) {




        swap(arr, left, left + (right-left)/2);




        int temp = arr[left];

        while (left<right) {

            while(left<right && arr[right] >= temp) {

                right--;

            }

            arr[left] = arr[right];

            while (left < right && arr[left] <= temp) {

                left++;

            }

            arr[right] = arr[left];

        }




        arr[left] = temp;




        return left;

    }

}

最后

其实还有别的基准数选择方式，这里需要大家去自行挖掘了！
掘金地址：https://juejin.im/post/5e63c2b7f265da57127e5480