插入排序（insertion_sort）—

# 插入排序

# 作用：对给出的n个顺序不定的数进行排序

# 输入：任意数组A

# 输出：按顺序排列的数组A

# 时间复杂度 n(n-1) 至 (n(n-1))/2

# 插入排序过程

# 第一趟：选择第一个元素，之前没有其他元素可以比较，故放在第一位

# 第二趟：选择第二个元素，与前一个元素比较，若比之大，则不动；若比之小，则与之交换

# 第三趟：选择第三个元素，与前一个元素比较，若比之大，则不动；若比之小，则与之交换

# 直到该元素前面没有再比它小的数

# 每次循环确定一个数的相对位置，以此类推

 1 # 在此修改初始数据

 2 A = [12,56,92,-1,5,110,92,999,-39,21,76,33,56]

 3

 4 print('您的初始数据为：')

 5 print(A);print('\n'*1)

 6 n = len(A)          # 用n获取数组长度

 7 i = 0               # 外循环时数组的下标

 8 j = 0               # 内循环时数组的下标

 9

10 while i <= n-1:

11     x = A[i]

12     j = i - 1

13     while j > -1 and A[j] > x:

14         A[j+1] = A[j]

15         j = j - 1

16     A[j+1] = x

17     i = i + 1

18     print(A)

19

20 print('调整后的数据为：')

21 print(A)

运行结果：

您的初始数据为：

[12, 56, 92, -1, 5, 110, 92, 999, -39, 21, 76, 33, 56]

调整后的数据为：

[-39, -1, 5, 12, 21, 33, 56, 56, 76, 92, 92, 110, 999]

插入排序运行过程中数组A的变化情况：

 1 [12, 56, 92, -1, 5, 110, 92, 999, -39, 21, 76, 33, 56]

 2 [12, 56, 92, -1, 5, 110, 92, 999, -39, 21, 76, 33, 56]

 3 [12, 56, 92, -1, 5, 110, 92, 999, -39, 21, 76, 33, 56]

 4 [-1, 12, 56, 92, 5, 110, 92, 999, -39, 21, 76, 33, 56]

 5 [-1, 5, 12, 56, 92, 110, 92, 999, -39, 21, 76, 33, 56]

 6 [-1, 5, 12, 56, 92, 110, 92, 999, -39, 21, 76, 33, 56]

 7 [-1, 5, 12, 56, 92, 92, 110, 999, -39, 21, 76, 33, 56]

 8 [-1, 5, 12, 56, 92, 92, 110, 999, -39, 21, 76, 33, 56]

 9 [-39, -1, 5, 12, 56, 92, 92, 110, 999, 21, 76, 33, 56]

10 [-39, -1, 5, 12, 21, 56, 92, 92, 110, 999, 76, 33, 56]

11 [-39, -1, 5, 12, 21, 56, 76, 92, 92, 110, 999, 33, 56]

12 [-39, -1, 5, 12, 21, 33, 56, 76, 92, 92, 110, 999, 56]

13 [-39, -1, 5, 12, 21, 33, 56, 56, 76, 92, 92, 110, 999]

简而言之，插入排序算法类似于打牌时的排序，从左到右按顺序选牌，然后插入到合适的位置。

巴特西

插入排序（insertion_sort）——Python实现

最新文章

热门文章