本文旨在对于个人知识的梳理以及知识的分享，如果有不足的地方，欢迎大家在评论区指出

核心思想

快速排序的核心思想主要有以下几步:

• 确定当前的关键值
• 将所有大于该关键值的数字放到右边，所有小于该关键值的放到左边
• 递归的处理左右两边

时间复杂度分析

对于快速排序，其平均时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)，最坏的情况是 O ( n 2 ) O(n^2) O(n2)，主要取决于关键值的选取，一般可以取中间的值作为关键值

模板代码

Go

package main

import (
    "fmt"
    )
    
func quick_sort(a []int, l int, r int) {
    if l >= r {
        return
    }
    
    key := a[(l+r)>>1] // 确定关键值
    i, j := l-1, r+1
    for i < j {
        i += 1
        for a[i] < key{
            i += 1
        }
        j -= 1
        for a[j] > key {
            j -= 1
        }
        if i < j {
            a[i], a[j] = a[j], a[i]
        }
    }
    quick_sort(a, l, j)
    quick_sort(a, j+1, r)
}    

func main() {
    var n int
    fmt.Scanf("%d", &n)
    a := make([]int, n)
    for i:=0; i<n; i++ {
        fmt.Scanf("%d", &a[i])
    }
    
    quick_sort(a, 0, n-1)
    for i:=0; i<n; i++ {
        fmt.Printf("%d ", a[i])
    }
}

例题扩展

• 第k个数