排序算法-快速排序-EW帮帮网

算法排序-快速排序

简介

快速排序（Quick Sort）是由英国计算机科学家托尼·霍尔（Tony Hoare）在1960年开发的一种高效的排序算法。它使用分治法（Divide and Conquer）策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。

快速排序在平均情况下的时间复杂度为O(n log n)，是实际应用中最常用的排序算法之一。

算法原理

快速排序的基本思想是：

选择基准值（Pivot）: 从数组中选择一个元素作为基准值
分区操作（Partition）: 重新排列数组，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面
递归排序: 递归地对基准值前后的两个子数组进行快速排序

Go语言实现

基础版本

package main

import "fmt"

// QuickSort 快速排序主函数
func QuickSort(arr []int, low, high int) {
    if low < high {
        // 获取分区点
        pi := partition(arr, low, high)
        
        // 递归排序分区点左边的元素
        QuickSort(arr, low, pi-1)
        // 递归排序分区点右边的元素
        QuickSort(arr, pi+1, high)
    }
}

// partition 分区函数，返回基准值的最终位置
func partition(arr []int, low, high int) int {
    // 选择最后一个元素作为基准值
    pivot := arr[high]
    
    // 较小元素的索引
    i := low - 1
    
    for j := low; j < high; j++ {
        // 如果当前元素小于或等于基准值
        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    
    // 将基准值放到正确位置
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

// QuickSortWrapper 快速排序包装函数
func QuickSortWrapper(arr []int) {
    if len(arr) > 1 {
        QuickSort(arr, 0, len(arr)-1)
    }
}

func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("排序前:", arr)
    
    QuickSortWrapper(arr)
    fmt.Println("排序后:", arr)
}

优化版本

package main

import (
    "fmt"
    "math/rand"
    "time"
)

// QuickSortOptimized 优化的快速排序
func QuickSortOptimized(arr []int, low, high int) {
    // 对于小数组使用插入排序
    if high-low+1 < 10 {
        insertionSort(arr, low, high)
        return
    }
    
    if low < high {
        // 随机选择基准值以避免最坏情况
        randomizePivot(arr, low, high)
        
        // 三路分区优化，处理重复元素
        lt, gt := threeWayPartition(arr, low, high)
        
        // 递归排序
        QuickSortOptimized(arr, low, lt-1)
        QuickSortOptimized(arr, gt+1, high)
    }
}

// randomizePivot 随机选择基准值
func randomizePivot(arr []int, low, high int) {
    rand.Seed(time.Now().UnixNano())
    randomIndex := low + rand.Intn(high-low+1)
    arr[randomIndex], arr[high] = arr[high], arr[randomIndex]
}

// threeWayPartition 三路分区，返回等于基准值的区间
func threeWayPartition(arr []int, low, high int) (int, int) {
    pivot := arr[high]
    lt := low      // arr[low...lt-1] < pivot
    i := low       // arr[lt...i-1] == pivot
    gt := high     // arr[gt+1...high] > pivot
    
    for i <= gt {
        if arr[i] < pivot {
            arr[lt], arr[i] = arr[i], arr[lt]
            lt++
            i++
        } else if arr[i] > pivot {
            arr[i], arr[gt] = arr[gt], arr[i]
            gt--
        } else {
            i++
        }
    }
    
    return lt, gt
}

// insertionSort 插入排序，用于小数组优化
func insertionSort(arr []int, low, high int) {
    for i := low + 1; i <= high; i++ {
        key := arr[i]
        j := i - 1
        
        for j >= low && arr[j] > key {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}

// QuickSortOptimizedWrapper 优化快速排序包装函数
func QuickSortOptimizedWrapper(arr []int) {
    if len(arr) > 1 {
        QuickSortOptimized(arr, 0, len(arr)-1)
    }
}

带步骤显示的版本

package main

import "fmt"

var step int

// QuickSortWithSteps 带步骤显示的快速排序
func QuickSortWithSteps(arr []int, low, high int, depth int) {
    if low < high {
        step++
        indent := ""
        for i := 0; i < depth; i++ {
            indent += "  "
        }
        
        fmt.Printf("%s步骤 %d: 排序区间 [%d, %d], 数组: %v\n", 
                   indent, step, low, high, arr[low:high+1])
        
        // 分区操作
        pi := partitionWithSteps(arr, low, high, depth)
        
        fmt.Printf("%s分区完成，基准值 %d 位于索引 %d\n", 
                   indent, arr[pi], pi)
        
        // 递归排序左半部分
        if pi-1 > low {
            fmt.Printf("%s递归排序左半部分 [%d, %d]\n", 
                       indent, low, pi-1)
            QuickSortWithSteps(arr, low, pi-1, depth+1)
        }
        
        // 递归排序右半部分
        if pi+1 < high {
            fmt.Printf("%s递归排序右半部分 [%d, %d]\n", 
                       indent, pi+1, high)
            QuickSortWithSteps(arr, pi+1, high, depth+1)
        }
    }
}

// partitionWithSteps 带步骤显示的分区函数
func partitionWithSteps(arr []int, low, high int, depth int) int {
    pivot := arr[high]
    indent := ""
    for i := 0; i <= depth; i++ {
        indent += "  "
    }
    
    fmt.Printf("%s选择基准值: %d\n", indent, pivot)
    
    i := low - 1
    
    for j := low; j < high; j++ {
        if arr[j] <= pivot {
            i++
            if i != j {
                fmt.Printf("%s交换 %d 和 %d\n", indent, arr[i], arr[j])
                arr[i], arr[j] = arr[j], arr[i]
            }
        }
    }
    
    arr[i+1], arr[high] = arr[high], arr[i+1]
    fmt.Printf("%s将基准值 %d 放到位置 %d\n", indent, pivot, i+1)
    
    return i + 1
}

func main() {
    // 测试基础版本
    arr1 := []int{64, 34, 25, 12, 22, 11, 90}
    fmt.Println("=== 基础快速排序 ===")
    fmt.Println("排序前:", arr1)
    QuickSortWrapper(arr1)
    fmt.Println("排序后:", arr1)
    
    // 测试优化版本
    arr2 := []int{5, 2, 8, 1, 9, 3}
    fmt.Println("\n=== 优化快速排序 ===")
    fmt.Println("排序前:", arr2)
    QuickSortOptimizedWrapper(arr2)
    fmt.Println("排序后:", arr2)
    
    // 测试带步骤显示的版本
    arr3 := []int{5, 2, 8, 1}
    fmt.Println("\n=== 带步骤显示的快速排序 ===")
    fmt.Printf("初始数组: %v\n", arr3)
    step = 0
    QuickSortWithSteps(arr3, 0, len(arr3)-1, 0)
    fmt.Printf("最终结果: %v\n", arr3)
}

复杂度分析

时间复杂度

最好情况: O(n log n) - 每次分区都能将数组平均分割
平均情况: O(n log n) - 随机数据的期望性能
最坏情况: O(n²) - 每次选择的基准值都是最大或最小值

空间复杂度

空间复杂度: O(log n) - 递归调用栈的深度

算法特点

优点

高效性: 平均时间复杂度为O(n log n)
原地排序: 只需要O(log n)的额外空间
实用性: 在实际应用中表现优秀
缓存友好: 具有良好的局部性

缺点

不稳定: 相等元素的相对位置可能改变
最坏情况: 在某些输入下性能退化到O(n²)
递归开销: 深度递归可能导致栈溢出

优化策略

1. 基准值选择优化

// 三数取中法选择基准值
func medianOfThree(arr []int, low, high int) {
    mid := (low + high) / 2
    
    if arr[mid] < arr[low] {
        arr[low], arr[mid] = arr[mid], arr[low]
    }
    if arr[high] < arr[low] {
        arr[low], arr[high] = arr[high], arr[low]
    }
    if arr[high] < arr[mid] {
        arr[mid], arr[high] = arr[high], arr[mid]
    }
    
    // 将中位数放到末尾作为基准值
    arr[mid], arr[high] = arr[high], arr[mid]
}

2. 小数组优化

对于小数组（通常小于10个元素），使用插入排序比快速排序更高效。

3. 三路分区

处理大量重复元素时，三路分区可以显著提高性能。

实际应用场景

快速排序广泛应用于：

通用排序: 大多数编程语言的标准库排序实现
数据库系统: 内存中的数据排序
搜索算法: 作为其他算法的预处理步骤
大数据处理: 分布式排序的基础算法

性能测试

package main

import (
    "fmt"
    "math/rand"
    "time"
)

// 性能测试函数
func benchmarkQuickSort(size int) {
    // 生成随机数组
    arr := make([]int, size)
    for i := 0; i < size; i++ {
        arr[i] = rand.Intn(10000)
    }
    
    start := time.Now()
    QuickSortOptimizedWrapper(arr)
    duration := time.Since(start)
    
    fmt.Printf("数组大小: %d, 排序时间: %v\n", size, duration)
}

func main() {
    fmt.Println("=== 快速排序性能测试 ===")
    sizes := []int{1000, 10000, 100000, 1000000}
    
    for _, size := range sizes {
        benchmarkQuickSort(size)
    }
}

总结

快速排序是一个非常重要和实用的排序算法，其分治思想和优秀的平均性能使其成为最受欢迎的排序算法之一。虽然在最坏情况下性能会退化，但通过合适的优化策略，可以在实际应用中获得优秀的性能。

关键要点:

使用分治法，通过分区操作递归排序
平均时间复杂度O(n log n)，空间复杂度O(log n)
不稳定排序，但可以通过优化提高实际性能
是大多数标准库排序算法的基础
适合大数据集的高效排序

排序算法-快速排序