图解算法基础：快速排序，用Go语言代码实现

terry 2年前 (2023-09-27) 阅读数 85 #数据结构与算法

来源丨叨bi叨网络经理（ID：kevin_tech）

很多面试题的答案都是基于排序。如果我们写 O() 的算法，很大概率会挂掉。今天写一篇关于快速排序的基础文章。稍后我会根据情况写组合和堆叠排序。至于排序选项和排序气泡，时间复杂度很高，我就不写了。好吧，如果你有兴趣的话，你可以找到这本书，自己读一读。

文中算法的实现是用Go写的比较简单的快速序列，比较容易让大家理解（配音：其实他已经好几年没有接受采访了，写得很好。它）。

关于更好的代码实现，可以在评论区发帖，一起学习。我相信读者里应该有卧虎藏龙，大拿有很多算法。

快速排序思想

快速排序算法会在序列中随机选择一个主元值，然后将除主元值以外的数字分为“小于主元值的数字”和“小于主元值的数字”这两类中“数值较大的数”，然后整理成下面的表格。

【比基准值小的数】 基准值 【比基准值大的数】

然后继续按照两个顺序“[]”对数据进行排序后，整个排序就完成了。当将顺序排序到基值的左侧和右侧时，也会使用快速排序。

快速排序是一种“分治法”，将原问题分解为两个子问题——小于基线值的数字和大于基线值的数字，然后分别求解这两个子问题。解决子问题时会再次使用快速排序。仅当子问题中只有一个数字时才进行排序。

快速排序过程

让我们通过示意图来更好地理解快速排序过程。

图例来自-《我的第一本算法书》

假设要排序如下序列要排序的序列

首先在序列中随机选择基准值，这里选择4。选择基准值枢轴

将其他数字与基准值进行比较。如果数字小于基准值，则向左移动，如果大于基准值，则向右移动。

首先将第一个元素3与基值4进行比较，因为3 先将3与基值4进行比较，因为3 接下来将5与基值进行比较，因为5 > 4，然后将5放在基值左侧左边。从正确的基值开始。 5 > 4，将5放在基值的右侧

对整个序列执行相同的操作后，所有小于基值的数字都放置在基值的左侧，所有大于基值的数字比基值放置在右侧。一轮排序后的结果将基准值排序

现在排序分为两个子问题，对基准值左右的数据进行排序。分解为两个子问题排序操作与之前相同。他们还使用快速排序算法，选择基准值，并将小于左侧的数字放在右侧，将较大的数字放在右侧。使用快速排序来排序

子问题可以分解为子问题。直到子问题中只有一个数字并且子问题无法进一步分解时，整个序列的排序才算完成。排序完成

由于快速排序算法在排序顺序的过程中会再次使用该算法，所以快速排序算法在实现时必须使用“递归”。

Go快速排序代码实现

下面是Go版快速排序算法的简单实现


func quickSort(sequence []int, low int, high int) {
 if high <= low {
  return
 }
 j := partition(sequence, low, high)
 quickSort(sequence, low, j-1)
 quickSort(sequence, j+1, high)
}

// 进行快速排序中的一轮排序
func partition(sequence []int, low int, high int) int {
 i, j := low+1, high
 for {
  // 把头元素作为基准值 pivot
  for sequence[i] < sequence[low] {
   // i 坐标从前往后访问序列，如果位置上的值大于基准值，停下来。
   // 准备和 j 坐标访问到的小于基准值的值交换位置
   i++
   if i >= high {
    break
   }
  }
  for sequence[j] > sequence[low] {
   // j 坐标从后往前访问序列，如果位置上的值小于基准值，停下来。
   // 和 i 坐标指向的大于基准值的值交换位置
   j--
   if j <= low {
    break
   }
  }
  if i >= j {
   break
  }
  sequence[i], sequence[j] = sequence[j], sequence[i]
 }
 sequence[low], sequence[j] = sequence[j], sequence[low]

 return j
}

每一轮快速排序都会经过以下步骤：

设置两个变量i,j ，当排序开始时：i = 0，j = 排序序列的长度 - 1。
使用数组的第一个元素作为主元值（可以是最后一个元素，也可以是随机元素）。
i坐标从头开始逆序访问元素，即i++，找到第一个大于该轴的位置，将该位置替换为小于该轴值的j坐标访问的值。
j坐标从尾部向前看，即j--，找到第一个比轴小的位置，改变坐标i和j中的值。
重复步骤3和4，直到i=j，然后改变轴坐标和j中的值，完成排序回合。小于主元的值放在左边，大于主元的值放在右边。。

重复以上过程，直至排序完成。最后，我们可以生成一个随机数序列来测试上面的快速排序功能：

func main() {
 rand.Seed(time.Now().Unix())
 sequence := rand.Perm(34)
 fmt.Printf("sequence before sort: %v", sequence)
 quickSort(sequence, 0, len(sequence) - 1)
 fmt.Printf("sequence after sort: %v", sequence)
}