Press "Enter" to skip to content

Go 数据结构和算法篇(八):快速排序

实现原理

归并排序算法虽好,但是不是原地排序算法,需要消耗额外的内存空间,今天我们要介绍的是常规排序里综合排名最高的排序算法:快速排序,江湖人称「快排」。

快排的核心思想是这样的:

如果要排序数据序列中下标从 pr 之间的一组数据,我们选择 pr 之间的任意一个数据作为 pivot(分区点),假设对应下标是 q

遍历 pr 之间的数据,将小于 pivot 的放到左边,将大于 pivot 的放到右边,将 pivot 放到中间。经过这一步骤之后,数据序列 pr 之间的数据就被分成了三个部分,前面 pq-1 之间都是小于 pivot 的,中间是 pivot,后面的 q+1r 之间是大于 pivot 的。

图示如下:

快速排序图示

根据分治、递归的处理思想,我们可以用递归排序下标从 pq-1 之间的数据和下标从 q+1r 之间的数据,直到区间缩小为 1,就说明所有的数据都有序了,而且你可以看到我们不需要像归并排序那样做合并操作,也就不需要额外的内存空间,在时间复杂度和归并排序一样的情况下,有着更好的空间复杂度表现。

快速排序首先要找到分区点 pivot,一般我们会将数据序列最后一个元素或者第一个元素作为 pivot。假设我们以最后一个元素作为分区点,然后通过两个变量 ij 作为下标来遍历数据序列,当下标 j 对应数据小于 pivot 时,交换 ij 对应的数据,并且将 i 的指针往后移动一位,否则 i 不动。下标 j 是始终往后移动的,j 到达终点后,将 pivot 与下标 i 对应数据交换,这样最终将 pivot 置于数据序列中间,[0...i-1] 区间的数据都比 pivot 小,[i+1...j] 之间的数据都比 pivot 大,我们以递归的方式处理该流程,最终整个数据序列都会变成有序的,对应的算法操作流程如下:

快速排序流程

示例代码

将上述流程转化为 Go 代码实现如下:

package main

import "fmt"

// 快速排序入口函数
func quickSort(nums []int, p int, r int) {
    // 递归终止条件
    if p >= r {
        return
    }
    // 获取分区位置
    q := partition(nums, p, r)
    // 递归分区(排序是在定位 pivot 的过程中实现的)
    quickSort(nums, p, q - 1)
    quickSort(nums, q + 1, r)
}

// 定位 pivot
func partition(nums []int, p int, r int) int {
    // 以当前数据序列最后一个元素作为初始 pivot
    pivot := nums[r]
    // 初始化 i、j 下标
    i := p
    // 后移 j 下标的遍历过程
    for j := p; j < r; j++ {
        // 将比 pivot 小的数丢到 [p...i-1] 中,剩下的 [i...j] 区间都是比 pivot 大的
        if nums[j] < pivot {
            // 互换 i、j 下标对应数据
            nums[i], nums[j] = nums[j], nums[i]
            // 将 i 下标后移一位
            i++
        }
    }

    // 最后将 pivot 与 i 下标对应数据值互换
    // 这样一来,pivot 就位于当前数据序列中间,i 也就是 pivot 值对应的下标
    nums[i], nums[r] = pivot, nums[i]
    // 返回 i 作为 pivot 分区位置
    return i
}

func main() {
    nums := []int{4, 5, 6, 7, 8, 3, 2, 1}
    quickSort(nums, 0, len(nums) - 1)
    fmt.Println(nums)
}

运行上述代码,打印结果如下,表明快速排序成功:

-w645

性能分析

正如我们前面所说的,快速排序是原地排序算法,时间复杂度和归并排序一样,也是 O(nlogn),这个时间复杂度数据量越大,越优于 O(n2)。

但是快速排序也有其缺点,因为涉及到数据的交换,有可能破坏原来相等元素的位置排序,所以是不稳定的排序算法。

尽管如此,凭借其良好的时间复杂度表现和空间复杂度的优势,快速排序在工程实践中应用较多。

关于线性表结构的排序算法我们就简单介绍到这里,下篇教程,我们来给大家介绍著名的线性表结构查找算法 —— 二分查找。

发表回复