简介

快速排序的名字就是他的特点 他的平均时间复杂度是 nlog(n)

原理

以数组某个元素（一般选取首元素）为 基准数 ，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。然后递归 对 左子数组 和 右子数组 递归执行 哨兵划分，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。
image.png
image.png

  1. public static void kuai(int[] ints, int left, int right) {
  2.         //递归终止条件
  3.         if (left >= right) {
  4.             return;
  5.         }
  6.         int i = left;
  7.         int j = right;
  8.         //基准值 让一个随机数和left位置的数字交换 避免数据倒序等极端情况导致的快排的时间复杂度为n方 这样时间复杂度达到n
  9.         int temp = left + (int) (Math.random()*(right-left+1));
  10.         swap(ints, left, temp);
  11.         int base = ints[left];
  12.         while (i < j) {
  13.             //这里的顺序不能反 必须是先-- 假设数组为 5 4 3 2 6 如果是++先 那么i就直接遍历到6才会停下 然后外层再和left交换 就不能正确的排序了
  14.             while (i < j && ints[j] >= base) {
  15.                 j--;
  16.             }
  17.             while (i < j && ints[i] <= base) {
  18.                 i++;
  19.             }
  20.             //交换i 第一个大于base的值 和j 第一个小于base的值
  21.             int tmp = ints[i];
  22.             ints[i] = ints[j];
  23.             ints[j] = tmp;
  24.         }
  25.         // 交换i和left  这样base的左边都是小于他的 右边都是大于他的
  26.         int tmp = ints[i];
  27.         ints[i] = ints[left];
  28.         ints[left] = tmp;
  29.         //递归调用左边和右边
  30.         kuai(ints, left, i - 1);
  31.         kuai(ints, i+1, right);
  32.     }