[原]10-Python3实用教程-排序算法-希尔排序

希尔排序

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
  • 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;

希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

算法步骤

  1. 设定一个增量,将列表分组,每组按照插入排序
  2. 将增量值减小,再分组,每组按照插入排序
  3. 当增量为1时,再执行插入排序,完成

代码实现:

def sort(list):
    import math
    gap = 1
    while gap < len(list)/3:
        gap = gap * 3 + 1
    print(gap)
    while gap > 1:
        for i in range(gap):
            print(i)
            for j in range(i, len(list), gap):
                preIndex = j - gap
                current = list[j]
                while preIndex >= 0 and list[preIndex] > current:
                    list[preIndex + gap] = list[preIndex]
                    preIndex -= gap
                list[preIndex + gap] = current

        gap = math.floor(gap / 3)
        print(gap)
    else:
        for i in range(len(list)):
            preIndex = i - 1
            current = list[i]
            while preIndex >= 0 and list[preIndex] > current:
                list[preIndex+1] = list[preIndex]
                preIndex-=1
            list[preIndex+1] = current
    return list

seq_list = [8, 6, 4, 9, 7, 3, 2, -4, 0, -100, 99]

print(sort(seq_list))
#[-100, -4, 0, 2, 3, 4, 6, 7, 8, 9, 99]
分享 提问
comments powered by Disqus