Kotlin 算法实战全景

Kotlin 的算法实现兼具函数式表达与高性能原地计算：

• 泛型扩展函数：利用 <T : Comparable<T>> List<T>.quickSorted() 实现优雅的链式调用。
• 状态压缩动态规划：结合 IntArray 原生数组与 maxOrNull 高阶函数。

---

📊 算法专题与复杂度

算法专题	典型问题 / 算法	核心思想	时间复杂度	空间复杂度
排序	Functional QuickSort	泛型扩展函数、列表过滤划分	$O(n \log n)$	$O(n)$
动态规划	0/1 背包问题	IntArray 空间压缩	$O(N \cdot W)$	$O(W)$

---

1. 函数式快速排序 (Extension Function QuickSort)

fun <T : Comparable<T>> List<T>.quickSorted(): List<T> {
    if (size <= 1) return this
    val pivot = this[size / 2]
    val left = filter { it < pivot }
    val equal = filter { it == pivot }
    val right = filter { it > pivot }
    return left.quickSorted() + equal + right.quickSorted()
}

fun main() {
    println("=== Kotlin Functional QuickSort ===")
    val data = listOf(64, 25, 12, 22, 11)
    val sorted = data.quickSorted()
    check(sorted == listOf(11, 12, 22, 25, 64)) { "Sort failed" }

    println("Sorted: $sorted")
    println("Kotlin QuickSort tests passed successfully.")
}

🐳 Docker Verified📋hello-lang-kotlin:2.0.10

Exit Code: 0

=== Kotlin QuickSortDemo ===
Kotlin DSA tests passed successfully.

---

2. 动态规划：0/1 背包问题

import kotlin.math.max

fun knapsack(capacity: Int, weights: IntArray, values: IntArray): Int {
    val dp = IntArray(capacity + 1)
    for (i in weights.indices) {
        for (w in capacity downTo weights[i]) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
        }
    }
    return dp[capacity]
}

fun main() {
    println("=== Kotlin 0/1 Knapsack DP ===")
    val weights = intArrayOf(2, 3, 4, 5)
    val values = intArrayOf(3, 4, 5, 6)
    val maxVal = knapsack(5, weights, values)
    check(maxVal == 7) { "Knapsack failed" }

    println("Max Knapsack Value: $maxVal")
    println("Kotlin Knapsack DP tests passed successfully.")
}

🐳 Docker Verified📋hello-lang-kotlin:2.0.10

Exit Code: 0

=== Kotlin KnapsackDemo ===
Kotlin DSA tests passed successfully.