快速排序

快速排序介绍

快速排序（Quicksort）是对冒泡排序的一种改进。

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

时间复杂度： O(nlogn)
稳定度：不稳定

代码实现

 /**
    * 思路：
    * 会先把数组中的一个数当作基准数（一般会拿数组中最左边的数）
    * 然后从两边进行检索，使用 j 先从右边检索比基准数小的数。
    * 再使用 i 从左边检索比基准数大的数。如果检索到了，就停下来，然后交换这两个元素。
    * 然后再继续检索，直到 i 和 j 相遇
    * 如果 i 和 j 相遇就停下来，基准数和相遇位置的数进行交换，交换基准数表示第一轮排序结束
    * 此时这个基准数已经归位，左边都比它小，右边都比他大
    * <p>
    * 使用递归，分左右进行第二轮（，）
    * 排基准数的左边 quickSort(int[] arr, int left, l - 1)
    * 排基准数的右边 quickSort(int[] arr, int r, right)
    *
    * @param arr   要排序的数组
    * @param left  左起点
    * @param right 右终点
    */
public static void quickSort2(int[] arr, int left, int right) {
       if (left > right) {
           return;
       }
       //定义变量保存基准数
       int base = arr[left];
       //定义变量r，指向最右边
       int r = right;
       //定义变量l，指向最左边
       int l = left;
       //临时变量，用作交换
       int temp;
       //当i和j不相遇的时候，在循环中进行检索
       while (l != r) {
           //由r从右向左检索，如果检索到比base小的数就停下来
           while (arr[r] >= base && l < r) {
               //j从右往左移动
               r--;
           }
           //l从右向左检索，如果检索到比base大的数就停下来
           while (arr[l] <= base && l < r) {
               l++;
           }
           //r和i都停下了,交换位置
           temp = arr[l];
           arr[l] = arr[r];
           arr[r] = temp;
       }
       //到这里说明l和r相遇了
       //如果l和r相遇了 就交换基准数和相遇位置的元素
       arr[left] = arr[l];
       arr[l] = base;
       //基准数在这里就归为了，左边的数字都比它小，右边的都比它大
       //排基准数的左边
       quickSort2(arr, left, l - 1);
       //排基准数的右边
       quickSort2(arr, r + 1, right);
   }