快速排序

public static int[] partition(int[] arr, int num) {
      if(arr == null || arr.length < 2){
          return arr;
      }
      //less从数组第一个元素的前一个元素开始
      int less = -1;
      //more从数组的最后一个元素的后一个元素开始
      int more = arr.length;
      //cur 当前比较的位置
      int cur = 0;
      while (cur < more) {
          if (arr[cur] < num) {
              //less的后一个位置和cur位置元素交换
              //交换之后，cur加一
              swap(arr, ++less, cur++);
          } else if (arr[cur] > num) {
              //cur和more位置的前一个交换
              swap(arr, --more, cur);
          }else {
              cur++;
          }
      }
      //返回等于num数据的位置
      return new int[] { less + 1, more - 1 };
  }

  private static void swap(int[] arr, int i, int j) {
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
  }

public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }
    public static void quickSort(int[] arr,int left,int right){
        if(left<right){
            //在经典快排中，一般取最后一个位置的点作为参考点，但是加入数据本来就是有序的时候，快排的时间复杂度会退化到O(N²)
            //所以，可以在数组中随机找一个数来作为参考点，使用这种方法来降低时间复杂度
            //在left到right的范围中随机取一个数，把它放到最后一个位置
            swap(arr,left + (int)(Math.random()*(right-left+1)),right);
            //选一个参考点，把数组分区，比如选数组的最后一个点
            //把比它小的放到它的左边，比它大的放到它右边，相等的不动
            //返回的p数组中包含两个元素，这两个元素就是跟参考点相等的数的左边界和右边界
            int []p = partition(arr,left,right);
            //递归分区
            quickSort(arr,left,p[0]-1);
            quickSort(arr,p[1]+1,right);
        }
    }

    private static int[] partition(int[] arr, int left, int right) {
        //左边指针 最开始在数组最左边的前一个位置 也就是 -1 位置
        int less = left-1;
        //右边指针，最开始在数组最右边的位置（所以最后位置的那个数不参与循环）
        int more = right;
        // left变量 作为当前指针的位置
        while (left<more){
            //以数组最右边的数值为参考点
            //如果当前指针的位置的数小于参考点的数
            if(arr[left]<arr[right]){
                //左边指针的下一个位置的数和当前指针位置的数交换，然后当前位置加一
                //比如第一次的时候其实是数组第一个元素和自己交换
                swap(arr,++less,left++);
            }
            //如果当前指针的位置的数大于参考点的数
            else if(arr[left]>arr[right]){
                //当前指针位置的元素和数组最后一个元素交换
                swap(arr,left,--more);
            }else {
                //如果相等，当前位置的指针加一
                left++;
            }
        }
        //因为数组最后位置的数是最为参考点来的，没有参与循环，最后需要把它交换到正确的位置
        swap(arr,more,right);
        return new int[]{less+1,more};
    }

    public static void swap(int[] arr,int left,int right){
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }