Maison > Article > développement back-end > 使用python实现8大排序算法-希尔排序
希尔排序的基本思想:
希尔排序是基于插入排序的改进,由于插入排序对于已排好的数列操作时是高效的,但插入排序一般是比较低效的,因为一次只能移动一位。所以希尔排序先通过分组进行排序,直到分组增量为1 。
例:
arr = [49,38,04,97,76,13,27,49,55,65],分组增量为5时,红色数为一组,进行插入排序,依次循环遍历
arr = [13,38,04,97,76,49,27,49,55,65],遍历完成后,分组增量自减,
arr = [13,27,04,55,65,49,38,49,97,76],再继续对分组增量为2的组进行插入排序,直到分组增量为1
代码:
Python代码
def shell_sort(lists): #希尔排序 count = len(lists) step = 2 group = count / step while group > 0: #通过group增量分组循环 for i in range(0, group): j = i + group while j < count: #分组中key值的索引,通过增量自增 k = j - group key = lists[j] while k >= 0: #分组中进行插入排序 if lists[k] > key: lists[k + group], lists[k] = lists[k], key else: break k -= group j += group group /= step return lists