Go數據結構和算法篇-快速排序

一、實現原理

快排的核心思想是這樣的：

如果要排序數據序列中下標從 p 到 r 之間的一組數據，我們選擇 p 到 r 之間的任意一個數據作爲 pivot（分區點），假設對應下標是 q。

遍歷 p 到 r 之間的數據，將小於 pivot 的放到左邊，將大於 pivot 的放到右邊，將 pivot 放到中間。經過這一步驟之後，數據序列 p 到 r 之間的數據就被分成了三個部分，前面 p 到 q-1 之間都是小於 pivot 的，中間是 pivot，後面的 q+1 到 r 之間是大於 pivot 的。

圖示如下：

快速排序圖示

根據分治、遞歸的處理思想，我們可以用遞歸排序下標從 p 到 q-1 之間的數據和下標從 q+1 到 r 之間的數據，直到區間縮小爲 1，就說明所有的數據都有序了，而且你可以看到我們不需要像歸併排序那樣做合併操作，也就不需要額外的內存空間，在時間複雜度和歸併排序一樣的情況下，有着更好的空間複雜度表現。

快速排序首先要找到分區點 pivot，一般我們會將數據序列最後一個元素或者第一個元素作爲 pivot。假設我們以最後一個元素作爲分區點，然後通過兩個變量 i 和 j 作爲下標來遍歷數據序列，當下標 j 對應數據小於 pivot 時，交換 i 和 j 對應的數據，並且將 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)
}

運行上述代碼，打印結果如下，表明快速排序成功：

三、性能分析

正如我們前面所說的，快速排序是原地排序算法，時間複雜度和歸併排序一樣，也是 O(nlogn)，這個時間複雜度數據量越大，越優於 O(n2)。

但是快速排序也有其缺點，因爲涉及到數據的交換，有可能破壞原來相等元素的位置排序，所以是不穩定的排序算法。

儘管如此，憑藉其良好的時間複雜度表現和空間複雜度的優勢，快速排序在工程實踐中應用較多。

關於線性表結構的排序算法我們就簡單介紹到這裏，下篇教程，我們來給大家介紹著名的線性表結構查找算法 —— 二分查找。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/dMwnzF_igNv_SeeaHoNlWA