排序算法----插入排序

插入排序

　　插入排序的主要思想是每次取一个列表元素与列表中已经排序好的列表段进行比较，然后插入从而得到新的排序好的列表段，最终获得排序好的列表。　　　

　　比如，待排序列表为[49,38,65,97,76,13,27,49]，则比较的步骤和得到的新列表如下：(带有背景颜色的列表段是已经排序好的，红色背景标记的是执行插入并且进行过交换的元素）

 1 """
 2 插入排序:选择列表中的未排序的子元素与前边已经排好顺序列表元素进行比较；
 3     （1）方式一：从前往后比较
 4         如果当前元素比前边排序元素值小，则从该位置将排好序的元素往后移动一位，再将当前元素插入！
 5         注意：向后移动时的从后往前！！！
 6     （2）方式二:从后往前
 7         如果当前元素比前边排序元素最后一个值小，则交换位置，然后继续与前一个比较，如果小则交换，直到最前边没有元素！
 8 """
 9 
10 
11 # 方式一：对已排好顺序的元素，从前往后比较
12 def insert_sort(int_list):
13     length = len(int_list)
14     if length <= 1: return int_list
15     for i in range(1, length):
16         item = int_list[i]
17         for j in range(i):
18             if item < int_list[j]:
19                 for k in range(i, j, -1):
20                     int_list[k] = int_list[k - 1]
21                 int_list[j] = item
22                 break
23     return int_list
24 
25 
26 # 方式二：对已排好顺序的元素，从后往前比较
27 def insert_sort2(int_list):
28     length = len(int_list)
29     if length <= 1: return int_list
30     for i in range(1, length):
31         while i > 0:
32             if int_list[i] < int_list[i - 1]:
33                 int_list[i], int_list[i - 1] = int_list[i - 1], int_list[i]
34                 i -= 1
35             else:
36                 break
37     return int_list
38 
39 
40 # print(insert_sort([11, 3, 5, 89, 1,23456,87678,2345,4567,0,3,5]))
41 # print(insert_sort2([11, 3, 5, 89, 1,23456,87678,2345,4567,0,3,5]))
42 if __name__ == '__main__':
43     int_str = input("请输入逗号分割的整数>>>").strip()
44     int_list = [int(i) for i in int_str.split(",")]
45     # print(insert_sort(int_list))
46     print(insert_sort2(int_list))