快排其实很简单

作者: Pober_Wong | 来源:发表于2018-09-09 22:36 被阅读42次

快排其实很简单
快排
快排
快排
快排
快排
快排
快排
快排
快排

大学时期，老师只讲了课本上快排的一种实现方式，当时学的云里雾里，最近调研一下知乎上的一些实现方式，总结归纳了一下，发现还是非常简单的，只要清晰了具体概念，实现方式就可以随意发挥了（至于可读性，简易性当然各有千秋）。

什么是快排

从数列中挑出一个元素，称为“基准”（pivot），

重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

换种说法

随意找个对比基准

将所有小于基准的元素放到它前面，大于它的放到后面，这样该基准的位置即为它的最终位置（不然呢？）

递归地切分基准左右两侧的子列表，重复 1

有木有感觉清晰了很多~
再看一下执行中递归的结构树：

quickSort.png

从图中可以看出，排序是自上而下的，快排的排序操作应当是在递进的过程中, 整个过程中，除了叶子每一个元素都是基准元素。

Code Time

错误的示例

这里只要写好最核心的一步（对树单层中基准位置的调整）函数，再配合基本的递归结构，就 OK 了。在知乎上找了一个比较清晰的一种实现方式：

/**
 * 作为递归的入口
 * @left 当前函数帧中输入数组的起始点
 * @right 当前函数帧中输入数组的终点
 */
function quickSort(arr, left, right) {
  const i = correctPivot(arr, left, right)
  if(curPivot > i) quickSort(arr, left, i)
  if(curPivot < i) quickSort(arr, i + 1, right)
}

function correctPivot(arr, i, j) {
  let mid = arr[Math.floor((i + j)/2)]
  while(i < j) {
    while(arr[i] < mid) i++
    while(arr[j] > mid) j--
    if(i<=j) {
      swap(arr, i, j) // 交换 i 和 j 位置上的元素，很简单，用辅助变量 tmp
      i++, j--
    }
  }
  return i
}

将原代码拆分为了如上函数，经过模拟分析，发现这个核心函数就是错的，它以 i 和 j 最终汇合的地点为新的切分点，而不是当前基准点的位置，因此基准很可能依旧在待排序的子数组中，这样在接下来的层级中，依旧还需要对老的基准进行对比（移动不会，因为已经是到最终的位置了），这样无形间增加了时间复杂度，完全违背了利用分治来分解问题的初衷，而且还可能因为条件判断异常导致栈溢出。

《数据结构》课本上的解法

因为我是计科科班出身，因此有必要晒一下被教育部认可的排序算法：

function quickSort(arr, first, end) {
  if(first >= end) return // 递归到叶子节点
   
  const pivot = correctPivot(arr, first, end)
  quickSort(arr, first, pivot - 1)
  quickSort(arr, pivot + 1, end)  
}

function correctPivot(arr, first, end) {
  while(first < end) {
    while(first < end && arr[first] <= arr[end]) end-- // 右侧扫描
    if(first < end) {
      swap(arr, fist, end)
      first++
    }

    while(first < end && arr[first] <= arr[end]) first++ // 左侧扫描
    if(first < end) {
      swap(arr, fist, end)
      end--
    }
  }
  return first
}

在已知 corretPivot 函数返回的是基准最终的位置，因此我们只需要不断操作最终得到它的 index 即可。

解析 correctPivot

由于在移动 first 和 end 的时候，二者重合之际即是基准的最终位置
这里我们是默认以第一个元素为基准，扫描基准右侧，让 end 向左一直移动到比基准小的元素的位置，然后交换基准与该元素的位置，此时该元素已经确定在基准左侧，所以不再处于对比范围（因为我们只是在找基准的位置，无需关心基准以外元素的状态，只需记住小于基准的一定都要在左侧，大于之的在另一侧），故 first 后移
开始扫描（基准的）左侧，一直移动到比基准大的位置（表示该数应处于基准的右侧），交换之，end 前移。
重复 2、3 步骤

其实在每次扫描时，都能够让基准处于 first 或者 end 的位置上，比如扫描完右侧，那么基准必然是会在 end 的位置，反之依然。这里对一侧可以简单的理解为基准的另一侧。在交换之前，每次在移动游标（first 或者 end）的时候，都是在顺序地排除比基准都大（小）的元素，缩小对比范围，每次的比较范围都是 first~end，直到 first === end 时，表示它两侧都是比它小或大的元素。

《算法导论》

function correctPivot(arr, l, r) {
  let m = l - 1
  for (let i = l; i <= r; i++) {
    if (arr[i] < arr[r]) {
      swap(++m, i)
    }
  }
  swap(m+1, r)
  return m + 1
}

有木有太简单了，只用了一次循环就搞定了基准的位置。

解析
先确定一件事，就是 m + 1 才是基准的最终位置，而我们每一次执行函数都是以最后一个元素为基准的。