快速排序

快速排序（Quick Sort）是一种高效的排序算法，广泛应用于实际场景中，因其平均时间复杂度较低而备受青睐。它采用分治法，通过选择一个“基准”元素将数组分为两部分，递归地对子数组进行排序。本文将详细讲解快速排序的原理、步骤，并提供C语言和Go语言的代码示例，帮助初学者快速上手。

原理

快速排序的核心思想是：

选择一个基准元素（通常是数组的第一个、最后一个或随机元素）。
将数组分为两部分：小于基准的元素放在左边，大于基准的元素放在右边（分区过程）。
对左右两个子数组递归应用快速排序。
当子数组长度为1或0时，停止递归。

它的平均时间复杂度是 O(n log n)，其中 n 是数组的长度，最坏情况下为 O(n²)（例如数组已排序或逆序）。尽管存在最坏情况，快速排序在实际应用中通常比插入排序或冒泡排序更快。

步骤

假设我们要对一个整数数组进行升序排序，以下是快速排序的详细步骤：

选择基准：从数组中选择一个元素作为基准（pivot），例如最后一个元素。
分区：重新排列数组，使小于基准的元素在左边，大于基准的元素在右边，基准元素位于中间。
递归：对基准左侧和右侧的子数组分别递归调用快速排序。
终止：当子数组长度小于等于1时，排序完成。

实现

下面是用C语言实现快速排序的代码，包含详细注释以帮助理解。

main.c
#include <stdio.h>

// 交换两个元素
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数：选择最后一个元素作为基准
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = low - 1;      // 小于基准的区域边界
    
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++; // 扩展小于基准的区域
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]); // 将基准放到正确位置
    return i + 1; // 返回基准的索引
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 获取分区后的基准索引
        int pi = partition(arr, low, high);
        
        // 递归排序左半部分
        quickSort(arr, low, pi - 1);
        // 递归排序右半部分
        quickSort(arr, pi + 1, high);
    }
}

// 打印数组的辅助函数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主函数：测试快速排序
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组：");
    printArray(arr, n);
    
    quickSort(arr, 0, n - 1);
    
    printf("排序后的数组：");
    printArray(arr, n);
    
    return 0;
}

编译 & 运行
$ gcc -o bin/quick-sort main.c
$ bin/quick-sort 
原始数组：64 34 25 12 22 11 90 
排序后的数组：11 12 22 25 34 64 90 
$ 

下面是用Go语言实现快速排序的代码，包含详细注释以帮助理解。

main.go
package main

import "fmt"

// 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 // 返回基准的索引
}

// 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)
    }
}

// printArray 打印数组内容
func printArray(arr []int) {
    for _, val := range arr {
        fmt.Printf("%d ", val)
    }
    fmt.Println()
}

func main() {
    // 示例数组
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    
    fmt.Print("原始数组：")
    printArray(arr)
    
    quickSort(arr, 0, len(arr)-1)
    
    fmt.Print("排序后的数组：")
    printArray(arr)
}

$ gsk build -v
create quick-sort/bin/quick-sort-linux-amd64
$ ./bin/quick-sort-linux-amd64 
原始数组：64 34 25 12 22 11 90 
排序后的数组：11 12 22 25 34 64 90

总结

快速排序的核心是通过选择基准元素进行分区，将数组分为两部分并递归排序，从而实现高效的排序。

作者：afxcn

来源：https://zh.gostartkit.com/docs/algo/quick-sort

发表日期：2025年6月28日

原理​

步骤​

实现​

总结​

原理

步骤

实现

总结