Kotlin 中的快速排序算法

1. 简介

排序是计算机科学中最基础的操作之一，有多种算法可用于实现排序。其中，快速排序（Quicksort） 是最流行的排序算法之一。它是一种高效的、递归的、基于比较的分治策略排序算法。

本文将深入讲解快速排序的核心思想，并以 Kotlin 语言为例，展示其多种实现方式以及对应的单元测试。

2. 快速排序算法简介

快速排序的核心思想是：

从数组中选择一个“基准”（pivot）元素，将其他元素划分为两个子数组：一个包含小于基准的元素，另一个包含大于基准的元素。然后对这两个子数组递归地进行快速排序。

这个过程体现了典型的“分治法”（Divide and Conquer）思想。

• 平均时间复杂度：O(n log n)
• **最坏情况时间复杂度：O(n²)**，但在实际应用中很少出现
• **空间复杂度：O(log n)**（递归栈）

基准的选择对性能影响较大，常见策略包括取中间、首元素、尾元素或随机选择。

3. Kotlin 中的快速排序实现

我们先实现一个基础版本的快速排序函数：

fun quickSort(arr: IntArray, left: Int = 0, right: Int = arr.size - 1): IntArray {
    var start = left
    var end = right
    val pivot = arr[(left + right) / 2]

    while (start <= end) {
        while (arr[start] < pivot) start++
        while (arr[end] > pivot) end--
        if (start <= end) {
            val temp = arr[start]
            arr[start] = arr[end]
            arr[end] = temp
            start++
            end--
        }
    }

    if (left < end) quickSort(arr, left, end)
    if (start < right) quickSort(arr, start, right)
    return arr
}

✅ 测试代码

@Test
fun `sorts an unsorted array`() {
    val arr = intArrayOf(5, 3, 9, 7, 1)
    val expected = intArrayOf(1, 3, 5, 7, 9)
    assertArrayEquals(expected, quickSort(arr))
}

@Test
fun `sorts a sorted array`() {
    val arr = intArrayOf(1, 2, 3, 4, 5)
    val expected = intArrayOf(1, 2, 3, 4, 5)
    assertArrayEquals(expected, quickSort(arr))
}

@Test
fun `sorts a reverse sorted array`() {
    val arr = intArrayOf(5, 4, 3, 2, 1)
    val expected = intArrayOf(1, 2, 3, 4, 5)
    assertArrayEquals(expected, quickSort(arr))
}

⚠️ 注意：该实现仅适用于 IntArray，但稍作修改即可支持任意 Comparable 类型的数组。

4. 快速排序的分区策略

快速排序的关键在于如何划分数组。常见的分区策略包括：

• Lomuto 分区
• Hoare 分区

这两种策略各有优劣，下面分别介绍。

4.1. Lomuto 分区

Lomuto 分区选取数组最后一个元素作为 pivot，通过一次遍历将数组划分为小于 pivot 和大于等于 pivot 的两部分。

fun quickSortLomuto(arr: IntArray, start: Int = 0, end: Int = arr.size - 1) {
    if (start < end) {
        val pivot = partitionLomuto(arr, start, end)
        quickSortLomuto(arr, start, pivot - 1)
        quickSortLomuto(arr, pivot + 1, end)
    }
}

fun partitionLomuto(arr: IntArray, start: Int, end: Int): Int {
    val pivot = arr[end]
    var i = start
    for (j in start until end) {
        if (arr[j] < pivot) {
            arr.swap(i, j)
            i++
        }
    }
    arr.swap(i, end)
    return i
}

private fun IntArray.swap(i: Int, j: Int) {
    val temp = this[i]
    this[i] = this[j]
    this[j] = temp
}

✅ 测试代码

@Test
fun `sorts an unsorted array using lomuto's scheme`() {
    val arr = intArrayOf(5, 3, 9, 7, 1)
    quickSortLomuto(arr)
    assert(arr.contentEquals(intArrayOf(1, 3, 5, 7, 9)))
}

⚠️ Lomuto 分区在处理重复元素时效率较低，且不稳定性略高。

4.2. Hoare 分区

Hoare 分区由 Tony Hoare 提出，使用两个指针从数组两端向中间扫描，交换不符合顺序的元素，直到相遇。

fun quickSortHoare(arr: IntArray, low: Int = 0, high: Int = arr.size - 1) {
    if (low < high) {
        val pivot = partitionHoare(arr, low, high)
        quickSortHoare(arr, low, pivot)
        quickSortHoare(arr, pivot + 1, high)
    }
}

fun partitionHoare(arr: IntArray, low: Int, high: Int): Int {
    val pivot = arr[low]
    var start = low - 1
    var end = high + 1
    while (true) {
        do start++ while (arr[start] < pivot)
        do end-- while (arr[end] > pivot)
        if (start >= end) return end
        arr.swap(start, end)
    }
}

✅ 测试代码

@Test
fun `sorts an unsorted array using hoare's scheme`() {
    val arr = intArrayOf(5, 3, 9, 7, 1)
    quickSortHoare(arr)
    assert(arr.contentEquals(intArrayOf(1, 3, 5, 7, 9)))
}

✅ Hoare 分区效率更高，但实现略复杂，是标准快速排序中更推荐的分区策略。

5. 小结

本文详细介绍了快速排序的基本原理，并展示了在 Kotlin 中三种不同的实现方式：

分区策略	实现复杂度	效率	适用场景
基础实现	简单直观	一般	初学者
Lomuto	中等	中等偏低	教学演示
Hoare	稍复杂	高效	实际应用

快速排序是算法学习中非常关键的一环，掌握其不同实现方式有助于我们更好地理解分治思想与性能优化。

完整代码可在 GitHub 上查看：Kotlin 快速排序实现示例

如需进一步优化，可尝试引入随机化 pivot 选择、三向切分、尾递归优化等技巧。