阅读 1618

手写算法并记住它:快速排序(最易理解版)

对于经典算法,你是否也遇到这样的情形:学时觉得很清楚,可过阵子就忘了?

本系列文章就尝试解决这个问题。

研读那些排序算法,细品它们的名字,其实都很贴切。

比如快速排序,一个快字就能体现出其价值,因而它是用得最多的。

因为它相对难一些,本系列将分两篇文章讲解它。

上一篇是5行代码实现版本。而本篇是原地排序算法。

快速排序这个名字是针对其性能来起的,但很难让人做到见名知意。

所以,我给它重新起了个名字:归分排序。

与归并算法一样,归分算法也是分而治之算法,讲究分、归、并。归并的重头戏在于如何去合并,快排的重头戏在于如何去划分。

上图中,先把数组按最后一个元素4作为分界点,把数组一分为三。除了分界点之外,左子部分全是小于等于4的,右子部分全是大于4的,它们可以进一步递归排序。因为是原地排序(不需要额外空间),因此不需归并那种合并操作。

其中,归相对容易些,该算法的核心是:如何把数组按分界点一分为三

各个教程的实现方式不一,这里我介绍一个最容易理解的方式。

具体过程是这样的,选取最后一个元素为分界点,然后遍历数组找小于等于分界点的元素,然后往数组前面交换。比如:

上图中,我们按顺序找小于等于4的元素,共1、2、3、4。然后分别与数组的前4个元素交换即可,结果自然是一分为三。

是不是非常容易理解的思路?快排也不难学嘛。

我们用JS实现一遍:

let array = [7, 1, 6, 5, 3, 2, 4]
let j = 0
let pivot = array[array.length - 1]
for (let i = 0; i < array.length; i++) {
  if (array[i] <= pivot) {
    swap(array, i, j++)
  }
}
console.log(array) // [ 1, 3, 2, 4, 7, 6, 5 ]
复制代码

其中swap函数封装了两个元素如何交换:

function swap(array, i, j) {
  [array[i], array[j]] = [array[j], array[i]]
}
复制代码

进一步封装成函数:

function partition(array, start, end) {
  let j = start
  let pivot = array[end]
  for (let i = start; i <= end; i++) {
    if (array[i] <= pivot) {
      swap(array, i, j++)
    }
  }
  return j - 1
}
复制代码

start和end表示数组起止下标。最后返回的j-1是分界点的位置。

接下来就需要递归处理左子部分和右子部分了。

对于递归,虽然它不符合线性思维,但其实也没啥难的。

只要有递归步骤(递归公式),很容翻译成代码的。

我们再回忆一下快排算法的步骤:

  1. 数组分成三部分left、pivot、right,使left<=pivot,right>pivot。
  2. 递归处理left
  3. 递归处理right

轻松翻译成代码:

function quickSort(array, start = 0, end = array.length -1) {
  let pivotIndex = partition(array, start, end)
  quickSort(array, start, pivotIndex - 1)
  quickSort(array, pivotIndex + 1, end)
  return array
}
复制代码

递归是自身调用自身,不能无限次的调用下去,因此需要有递归出口(初始条件)。

它的递归出口是,当数组元素个数为小于2时,就是已经是排好序的,不需要再递归调用了。

因此需要在前面加入代码:

if (end - start < 1) return array
复制代码

至此,快速排序原理和实现已经说完了。

快排的算法主要在于partition函数的实现,不同教程的实现方式都不一样,这个需要注意一下。

其时间复杂度平均是O(nlogn)。最坏情形是,假如待排的数组已经是排好序的,该算法将退化成O(n^2)级的。此时可以通过合理的分区点选择来避免。常见策略有选中间、随机选、三选一等。假如这里我们随机选一个分区点,再与最后的元素交换,就能大概率避免最坏情形的出现。查看完整代码:codepen

这里总结一下,快速排序是原地算法,不需要额外空间,但递归是需要空间的的(相当于手动维护个调用栈),总体空间复杂度是O(logn)。相等元素可能会交换前后顺序,因而不是稳定排序(因为交换)。时间复杂度为O(nlogn)。

快速排序,要做到能分分钟手写出来,是需要掌握其排序原理的。关键在于,如何按照分界点把数组一分为三。至于递归,只要能说清楚递归步骤和出口,就能很容易写出来,不需要死记硬背的。

希望有所帮助,本文完。



本系列已经发表文章:

关注下面的标签,发现更多相似文章
评论