python排序算法-（3）插入排序

插入排序算法是一种简单直观的排序算法。工作原理如下：

在第一轮时，假定第一个元素为已排序的元素，

而其余元素都是未排序的。

接着，从未排序的元素中选出第一个元素，

并将它插入到已排序的合适的位置上，使之成为新的已排序的元素。

以此类推，直到所有元素都排序完毕。

import random

# 插入排序
def insertionSort(arr):
    n=len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # 将关键值与左侧的每个元素进行比较，直到找到一个比它小的元素为止
        # 如果要降序排列，请将 key<array[j] 改为 key>array[j]
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j = j - 1
        # 将 key 放到正确的位置。
        arr[j + 1] = key

# 测试
array=random.sample(range(0, 100), 50)
print("原始数组为:")
print(array)

insertionSort(array)

print('经插入排序后的数组为:')
print(array)

运行环境：python3.8

原始数组为:

[14, 86, 49, 66, 71, 16, 44, 40, 9, 97, 21, 2, 73, 46, 23, 82, 89, 27, 6, 32, 25, 69, 52, 88, 98, 5, 59, 8, 41, 60, 51, 57, 0, 55, 29, 53, 26, 35, 85, 76, 80, 63, 31, 22, 94, 99, 50, 17, 11, 79]

经插入排序后的数组为:

[0, 2, 5, 6, 8, 9, 11, 14, 16, 17, 21, 22, 23, 25, 26, 27, 29, 31, 32, 35, 40, 41, 44, 46, 49, 50, 51, 52, 53, 55, 57, 59, 60, 63, 66, 69, 71, 73, 76, 79, 80, 82, 85, 86, 88, 89, 94, 97, 98, 99]