SortAlgosKt(3) - 插入排序

这期来讲讲插入排序。

算法思想

插入排序的基本思想，就是对所有元素进行遍历，每一次把当前遍历的元素插入到前面已经排序好的有序队列的相应位置上。这个过程就很像打扑克时候的理牌，每抽一张牌就把那张牌给放到手牌里的对应位置，~~如果你喜欢打牌应该很好理解~~（其实在下并不怎么打牌，只是《算法导论》里举得的这个例子给俺留下了很深刻的印象）。

算法实现

实现上使用双循环，外层对所有元素进行遍历（不包括第一个元素，因为第一个元素已经有序）,内层从当前元素往前遍历前面的有序队列，通过每次和前面的一个元素比较交换，查找合适的插入位置。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
fun insertionSort(nums: IntArray) {
    if (nums.size < 2) return
    //i表示第几趟排序
    for (i in 1..nums.lastIndex) {
        //j表示当前元素每次和有序队列的元素进行比较后的索引
        for (j in i downTo 1) {
            if (nums[j] < nums[j - 1]) {
                swap(nums, j, j - 1)
            } else {
                break
            }
        }
    }
}

时间复杂度：O(n^2)

空间复杂度：O(1)

文章目录

算法思想

算法实现