排序算法之插入排序：java、Kotlin、python代码实现

插入排序(Insertion Sort)

通过构建有序序列，对于未排序序列，从后向前扫描(对于单向链表则只能从前往后遍历)，找到相应位置并插入。实现上通常使用 in-place 排序(需用到 O(1) 的额外空间)

算法思路

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤 2~5

图片源自Visualgo

实现

Java

public class InsertionSort {

    public static void main(String[] args) {
        int[] unsortedArray = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
        insertionSort(unsortedArray);
        System.out.println("After sorted: ");
        for (int number : unsortedArray) {
            System.out.print(" " + number);
        }
    }

    private static void insertionSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }

        int length = array.length;
        int i,j;
        for (i = 1; i < length; i ++) {

            int holder = array[i];

            for (j = i; j > 0 && array[j - 1] > holder; j--) {
                    array[j] = array[j - 1];
            }

            // 以下是错误的代码逻辑，因为必须是满足 array[j - 1] > holder 才应该 j--
            // 下面代码是每次都会执行 j--
//            for (j = i; j > 0; j--) {
//                if (array[j - 1] > holder) {
//                    array[j] = array[j - 1];
//                }
//            }

            array[j] = holder;
        }
    }
}
复制代码

Kotlin

object InsertionSortKt {

    fun insertionSort(array: IntArray) {
        if (array.isEmpty()) {
            return
        }

        val size = array.size
        for (i in 1 until size) {

            val holder = array[i]
            var j = i
            while (j > 0 && array[j - 1] > holder) {
                array[j] = array[j - 1]
                j--
            }

            array[j] = holder
        }
    }
}

fun main(args: Array<String>) {
    val unsortedArray = intArrayOf(6, 5, 3, 1, 8, 7, 2, 4)
    InsertionSortKt.insertionSort(unsortedArray)
    println("After sorted: ")
    unsortedArray.forEach {
        print(" $it")
    }
}
复制代码

Python3

#!/usr/bin/env python
# coding=utf-8


def insertion_sort(arrayList):
    length = len(arrayList)

    for i in range(1, length):
        holder = arrayList[i]
        j = i
        while(j > 0 and arrayList[j - 1] > holder):
            arrayList[j] = arrayList[j - 1]
            j -= 1

        arrayList[j] = holder


if __name__ == "__main__":
    arrayList = [6, 5, 3, 1, 8, 7, 2, 4]
    print("orgin array list: {0}".format(arrayList))
    insertion_sort(arrayList)
    print("after sorted list: {0}".format(arrayList))
复制代码

时间复杂度

最好的情况：正序有序(从小到大)，这样只需要比较 n 次，不需要移动。因此时间复杂度为 O(n)

最坏的情况：逆序有序,这样每一个元素就需要比较 n 次，共有 n 个元素，因此实际复杂度为 O(n^2)

平均情况：O(n^2)