Sorting 排序算法 输入：Java、Kotlin、Python 代码实现

输入排序

构造有序序列时，对于未排序的序列，从后向前扫描（对于单向链表，只能从后扫描到前面）来回），找到对应的位置，插入这个。实现中通常采用就地排序（需要O(1)额外空间）

算法思想

1. 从第一个元素开始，该元素可以认为已排序
2. 取出下一个元素，从按照已排序元素的顺序向后退
3. 如果某个元素（已排序）大于新元素，则将该元素移动到下一个位置
4. 重复步骤 3，直到找到小于或等于的已排序元素到新元素的位置
5. 在此位置插入新元素后
6. 重复步骤 2-5

来自 Visualgos 的图像

实现

KolinPython3

#!/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)

作者：骑摩托车的马斯
链接：https://juejin.im/post/5a448a209294fb9afb来源：掘金
版权所有属于作者。商业转载请联系作者授权。非商业转载请注明出处。