插入排序有两种，一种是稳定的直接插入排序，一种是不稳定的希尔插入排序。下面就简单介绍一下两个排序算法以及代码实现。

一、直接插入排序

# coding: utf-8 # 直接插入排序：首先将第一个元素看成有序序列，从第二个开始，将当前元素 # 与前面的有序序列的最后一个元素进行比较，如果当前元素大，则直接i++判断下一个 # 否则插入到前面有序序列中的合适位置，若当前元素与有序序列中的某一元素相等，则 # 插入此元素的后面，所以排序算法是稳定的，时间复杂度是O(n^2) class DirectInsertSort: def __init__(self, data): self.data = data def sort(self): data = self.data n = len(data) for i in range(1, n): # 认为第一个元素是有序的，从第二个元素开始和前面的有序数组比较插入 if data[i]<data[i-1]: # 如果小于有序数组中最大的元素，则进入寻找带插入数字的合适位置 j = i-2 t = data[i] data[i] = data[i-1] while j>=0 and data[j]>t: # data[j]>t 表示稳定 data[j+1] = data[j] j-=1 data[j+1] = t return data def main(): try: data = [int(x) for x in input('请输入需要排序的数组，以空格分隔').strip().split(' ')] except: print('输入不合法') else: s = DirectInsertSort(data) print('排序前的数组：', end=' ') print(s.data) ans = s.sort() print('排序后的数组：', end=' ') print(ans) if __name__ == '__main__': main()

 

二、希尔插入排序

 希尔排序是根据直接插入排序提出来的，利用树的结构特性，在某些情况下可以提高排序的效率。

# coding: utf-8 # 希尔排序：取m个子长度{（一般是n/2,n/4,n/8...1)n为排序数组的长度}，每次比较当前元素和 # （当前元素下标+子长度）的元素，重复m次。希尔排序是不稳定的， class ShellInsertSort: def __int__(self, data): pass def shellSort(self,data): n = len(data) d = n//2 while d>=1: data = self.sort(data, d, n) d = d // 2 return data def sort(self, data, d, n): for i in range(d, n): if data[i]<data[i-d]: j = i - d - d t = data[i] data[i] = data[i - d] while j >= 0 and data[j] > t: # data[j]>t 表示稳定 data[j + d] = data[j] j -= d data[j + d] = t return data def main(): try: data = [int(x) for x in input('请输入需要排序的数组，以空格分隔').strip().split(' ')] except: print('输入不合法') else: s = ShellInsertSort() print('排序前的数组：', end=' ') print(data) ans = s.shellSort(data) print('排序后的数组：', end=' ') print(ans) if __name__ == '__main__': main()