[数据结构与算法]排序算法:快排

快速排序

基本想法为将数组按照一个中间基准值分为两段，大于基准值的放在基准值的右侧，小于的反之(大的小的比较基准值然后swap)，然后再让基准值两边的数组在进行以上操作直到数组不能再分出基准值并swap

quicksort

排序arr数组中left,right之间的元素(right得-1,数组越界)

public static void quickSortImplements01(int[] arr, int left, int right) {
    if (!(left >= right || left < 0 || arr == null || arr.length == 0 || right > arr.length - 1)) {
      int p = arr[left + ((right - left) >> 1)], l = left, r = right;
      while (l <= r) {
        while (l <= r && ((arr[l] < p && ++l != -100) || (arr[r] > p && --r != -100))) {
        }
        if (l <= r) {
          swap(arr, l++, r--);//swap自己实现
        }
      }
      quickSortImplements01(arr, left, r);
      quickSortImplements01(arr, l, right);
    }
  }

选取数组中间值进行基准元素，从left向右遍历，从right向左遍历，当正好有一组元素arr[left]大于基准值并且arr[right]小于基准时，交换他们，当遍历到left>=right(left坐标永远在基准值左边，right在右边，一旦越界跳出循环)，之后在进行递归式的在整个数组中不断分裂并重复上述操作，最终生成有序数组，如下图,

灵魂画手jpg

上面这个是基于交换实现看起来非常简单，还有一种基于partition的快速排序稍微麻烦一些，

算法思想为只有当前索引位元素小于基准值时交换辅助索引位与当前索引位元素并将辅助索引位+1，辅助索引位报存比基准值小的值的最左边界因为比基准值大的全部被换走了，最后基准值在与辅助索引位交换，也能得到大于基准值的放在基准值的右侧，小于的反之，总结来说就是使用一个辅助位存储遍历过的所有值中比基准值小的个数最后再让基准值与辅助位交换，形成左边全比自己小右边全比自己大

灵魂画手.jpeg

代码(right=arr.length-1)

  public static void quickSortImplementsOfPartition(int[] arr, int p, int r) {
    if (p >= r) {
      return;
    }
    int q = partition(arr, p, r);
    quickSortImplementsOfPartition(arr, p, q - 1);
    quickSortImplementsOfPartition(arr, q + 1, r);
  }

  //partition用的基准值为数组最后一个元素，有需求的自己改成别的
  public static int partition(int[] arr, int p, int r) {
    if (arr == null || p < 0 || r < 0 || p > r) {
      return -1;
    }
    if (arr.length == 0) {
      return 0;
    }
    int pivot = arr[r];
    int i = p;
    for (int j = p; j < r; j++) {
      if (arr[j] < pivot) {
        swap(arr, i++, j);//swap自己实现吧
      }
    }
    swap(arr, i, r);
    return i;
  }

抖机灵写法

  public static void quickSortImplementsOfPartition(int[] arr, int p, int r) {
    if (p < r) {
      int q = partition(arr, p, r);
      quickSortImplementsOfPartition(arr, p, q - 1);
      quickSortImplementsOfPartition(arr, q + 1, r);
    }
  }

  public static int partition(int[] arr, int p, int r) {
    if (!(arr == null || p < 0 || r < 0 || p > r)) {
      int pivot = arr[r], i = p, k = 0;
      for (int j = p; j < r && (k == (arr[j] < pivot ? swap(arr, i++, j) : 0)); j++) {}
      return i + swap(arr, i, r);
    }
    return (arr != null && arr.length == 0) ? 0 : -1;
  }

  private static int swap(int[] arr, int l, int r) {
    int t = arr[l];arr[l] = arr[r];arr[r] = t;return 0;
  }

?为什么快排比其他的快呢

归并：我复制操作太多了

堆排：我上移下移的时候无效交换太多了

计数，基数，桶排序：他们都是非比较排序

其他的：都不是O(nlogn)