快速排序算法原理及Go语言实现详解

快速排序的核心原理

不同于归并排序依据元素位置进行划分，快速排序是依据元素的值对数组进行分区。其核心操作在于选择一个基准元素（pivot），将数组重新排列，使得基准元素左侧的所有元素都小于或等于它，而右侧的所有元素都大于或等于它。此时，该基准元素即处于其在最终有序数组中的确切位置。

一旦分区建立，算法便递归地对基准元素左侧和右侧的子数组执行相同的排序操作，直至子数组长度为0或1。初始调用通常对整个数组范围进行操作，例如对数组A从索引1到长度N进行快速排序。

分区过程详解

快速排序的效率关键在于分区（Partition）操作。以下伪代码展示了经典的Lomuto分区方案逻辑：以数组最后一个元素作为基准值，通过遍历数组交换元素，确保基准值最终位于正确位置。

PARTITION(A, p, r)
    x = A[r]        // 选择基准值（通常为末尾元素）
    i = p - 1       // 初始化边界索引
    for j = p to r - 1 do
        if A[j] ≤ x then
            i = i + 1
            exchange A[i] with A[j]
    exchange A[i+1] with A[r]
    return i + 1

算法效率与复杂度分析

快速排序的时间复杂度取决于分区操作的平衡程度，主要分为以下三种情况：

1. 最优情况：Θ(n log n)

当每次分区都能将数组均匀地分为两半时，达到最优性能。比较次数满足递推式：
C_best(n) = 2C_best(n/2) + n
根据主定理，时间复杂度为 Θ(n log n)。这意味着在处理随机数据时，快速排序具有极高的效率。

2. 最差情况：Θ(n²)

最坏情况发生在每次分区点都趋于极端，即一个子数组为空，另一个仅少一个元素。这通常出现在已排序的升序数组中，若始终选择末尾元素为基准。此时比较次数接近求和公式：
C_worst(n) ≈ n²/2
时间复杂度降为 **Θ(n²)**，这与冒泡排序相当，因此在实际应用中需避免这种退化情况（如采用随机基准或三数取中法）。

3. 平均情况：≈1.38 n log n

对于随机排列的数组，假设每个分裂点出现的概率相等，平均比较次数约为 **1.38 n log n**。虽然常数系数略高于最优情况，但由于其内层循环简单高效，处理随机数据时，快速排序的实际速度通常快于归并排序。

Go语言代码实现

以下是使用Go语言实现的快速排序算法。该实现采用了双指针法进行分区，相较于伪代码的Lomuto分区，Hoare或双向扫描变体通常在交换操作上更为高效。

func QuickSort(slice_arg []int, iLeft int, iRight int) {
    if iLeft < iRight {
        var iTmpVal = slice_arg[iLeft] // 选择第一个元素作为基准
        var i, j = iLeft, iRight
        
        for i < j {
            fmt.Println("i,j = ", i, j)
            
            // 从右向左寻找小于基准的元素
            for i < j && slice_arg[j] > iTmpVal {
                j--
            }
            if i < j {
                slice_arg[i] = slice_arg[j]
                i++
            }
            
            // 从左向右寻找大于基准的元素
            for i < j && slice_arg[i] < iTmpVal {
                i++
            }
            if i < j {
                slice_arg[j] = slice_arg[i]
                j--
            }
        }
        
        // 将基准值放入最终位置
        slice_arg[i] = iTmpVal
        
        // 递归排序左右子数组
        QuickSort(slice_arg, iLeft, i-1)
        QuickSort(slice_arg, j+1, iRight)
    }
}

上述代码首先检查子数组是否有效，然后通过移动指针 `i` 和 `j` 将较小值移至左侧、较大值移至右侧，最后将基准值归位，并递归处理剩余部分。

以上就是快速排序算法的原理及其Go语言实现的详细内容，更多关于算法基础与Go编程的资料请关注本站其它相关文章！