Kotlin 中的插入排序 | Baeldung中文网

1. 概述

本文将使用 Kotlin 实现插入排序（Insertion Sort）算法。插入排序是一种简单且高效的排序方法，其核心思想是：将数组分为已排序和未排序两部分，逐个从后者取出元素，插入到前者正确的位置中。

整个过程就像我们手动整理扑克牌——每次拿到一张新牌，就把它插进手中已排好序的牌中的合适位置。

✅ 特点总结：

原地排序（in-place）
稳定排序（相同值相对顺序不变）
对小规模数据表现良好
最佳情况下时间复杂度为线性

2. 插入排序的工作原理

假设初始数组为 [5, 2, 9, 3]，我们来一步步看它是如何被排序的：

第一轮（i=1）：取第二个元素 2，与前面的 5 比较 → 2 < 5，所以把 5 右移，插入 2，得到 [2, 5, 9, 3]
第二轮（i=2）：取第三个元素 9，与前一个 5 比较 → 9 > 5，无需移动，保持 [2, 5, 9, 3]
第三轮（i=3）：取第四个元素 3
- 先与 9 比较 → 3 < 9，右移 9
- 再与 5 比较 → 3 < 5，右移 5
- 最后与 2 比较 → 3 > 2，停止移动
- 将 3 插入当前位置，结果为 [2, 3, 5, 9]

⚠️ 关键理解点：
不是“交换”，而是“腾位置”——通过向右平移比当前元素大的项，空出正确插入位。

3. Kotlin 中的插入排序实现

下面是标准的插入排序实现：

fun insertionSort(arr: IntArray) {
    val n = arr.size
    for (i in 1 until n) {
        val key = arr[i]      // 当前要插入的元素
        var j = i - 1         // 已排序部分的最后一个索引
        
        // 向左扫描，找到插入位置，同时腾出空间
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = key  // 插入到正确位置
    }
}

class SortIntArrayTest {
    @Test
    fun testInsertionSort() {
        val myArray = intArrayOf(5, 2, 9, 3, 6)
        insertionSort(myArray)
        val expectedSortedArray = intArrayOf(2, 3, 5, 6, 9)
        assertArrayEquals(expectedSortedArray, myArray)
    }
}

📌 几个关键细节：

使用 key 缓存当前值，避免在移动过程中丢失
while 条件中 j >= 0 防止越界
arr[j + 1] = key 是最终落点，别写成 arr[j]

踩坑提醒 ❌：
容易把 arr[j + 1] = key 错写成 arr[j] = key，导致少移动一位！

4. 使用 Comparable 接口进行泛型排序

上面的例子只适用于整数。如果想对自定义对象排序，可以借助 Comparable 接口。

data class Person(val name: String, val age: Int) : Comparable<Person> {
    override fun compareTo(other: Person): Int {
        return age.compareTo(other.age)
    }
}

fun insertionSortByAge(people: Array<Person>) {
    val n = people.size
    for (i in 1 until n) {
        val key = people[i]
        var j = i - 1
        while (j >= 0 && people[j] > key) {  // 直接使用 > 操作符
            people[j + 1] = people[j]
            j--
        }
        people[j + 1] = key
    }
}

class SortingTests {
    @Test
    fun testInsertionSortByAge() {
        val people = arrayOf(
            Person("Alice", 30),
            Person("Bob", 25),
            Person("Charlie", 35),
            Person("David", 20)
        )
        insertionSortByAge(people)
        val expected = arrayOf(
            Person("David", 20),
            Person("Bob", 25),
            Person("Alice", 30),
            Person("Charlie", 35)
        )
        for (i in people.indices) {
            assertEquals(expected[i], people[i])
        }
    }
}

✅ 技术亮点：

Person 实现了 Comparable<Person>，支持自然排序
Kotlin 支持操作符重载，可以直接用 > 进行比较
算法逻辑完全复用，只需更换数据类型

💡 扩展建议：
若需按多个字段排序（如先按年龄再按姓名），可改用 Comparator 或在 compareTo() 中组合判断。

5. 时间与空间复杂度分析

场景	比较次数	交换/移动次数	时间复杂度
最好情况	已排序 → $n-1$ 次	0 次	O(n)
平均情况	~$n^2/4$	~$n^2/4$	O(n²)
最坏情况	$n(n-1)/2$	$n(n-1)/2$	O(n²)

📌 空间复杂度：
✅ O(1) —— 仅使用常量级额外空间，属于原地排序算法。

📌 稳定性：
✅ 是稳定排序 —— 相同元素不会因排序改变相对顺序，适合需要保持原有顺序的场景。

📌 适用场景推荐：

数据量较小（一般 < 50）
数组基本有序（此时接近 O(n)）
作为复杂排序算法（如 TimSort）的子过程
教学演示或面试手撕代码

❌ 不适用于：

大数据集（n > 1000）
实时系统中频繁调用排序

6. 总结

本文深入剖析了插入排序的核心机制，并通过 Kotlin 实现了针对基础类型和自定义对象的版本。虽然它的最坏时间复杂度为 O(n²)，但在特定场景下依然有不可替代的优势：

✅ 实现简洁，易于理解和调试
✅ 原地排序，内存开销极小
✅ 在近乎有序的数据上性能优异
✅ 稳定排序，满足业务一致性需求

对于 Java/Kotlin 开发者来说，理解这类基础算法不仅能提升编码能力，也有助于更好地掌握 JDK 中 Arrays.sort() 背后的优化策略（例如小数组使用插入排序）。

完整示例代码已托管至 GitHub：
👉 https://github.com/baeldung/kotlin-tutorials/tree/master/core-kotlin-modules/core-kotlin-datastructures

Persistence

REST

Security