Python|希尔排序[6]

说明

• 排序的定义

对一序列对象根据某个关键字进行排序。

• 术语说明

稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

内排序 ：所有排序操作都在内存中完成；

外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

时间复杂度 ：一个算法执行所耗费的时间。

空间复杂度 ：运行完一个程序所需内存的大小。

n: 数据规模

In-place: 占用常数内存，不占用额外内存

希尔排序是希尔于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

具体算法描述如下：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

• 步骤1：选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
• 步骤2：按增量序列个数k，对序列进行k 趟排序；
• 步骤3：每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

def shellSort(todoList):
    length=len(todoList)
    gap=int(length/2)
    while gap>1:
        for i in range(0,gap):
            for j in range(gap,length,gap):
                if todoList[j]<todoList[j-gap]:
                    todoList[j],todoList[j-gap]=todoList[j-gap],todoList[j]
        gap=int(gap/2)
    return todoList

现在对10000个随机生成的数据进行排序，然后比较两者消耗的时间。

t1 = time.time()
new1 = RSort.quickSort(randomList)
# print(new1)
t2 = time.time()
print("快速排序：{}".format(RSort.isRight(randomList,new1)))
print("快速排序耗时：{}".format(t2 - t1))


t11 = time.time()
new6 = RSort.shellSort(randomList)
t12 = time.time()
print('希尔排序：{}'.format(RSort.isRight(randomList,new6)))
print("希尔排序耗时：{}".format(t12 - t11))

快速排序耗时：0.03191852569580078

冒泡排序耗时：16.95561718940735

插入排序耗时：6.9783196449279785

选择排序耗时：6.4557578563690186

堆排序耗时：18.616276741027832

希尔排序耗时：0.03789877891540527

完整的代码依旧放在了微信公众号，后台回复希尔排序即可获取源代码。或者可以直接看上面的源代码把。

内排序告一段落，接下来是外排序。