排序算法之希尔排序的python实现

希尔排序(Shell’s Sort)是插入排序的一种，是直接插入排序算法的一种更高版本的改进版本。

希尔排序的工作原理

如下：

(1)把记录按步长gap分组，对每组记录采用直接插入排序方法进行排序；

(2)随着步长逐渐减小，所分成的组包含的记录越来越多；

(3)当步长值减小到1时，整个数据合成一组，构成一组有序记录，完成排序；

代码实现如下：

#!/usr/bin/env python

# -*- coding:utf-8 -*-

__author__ = "hsz"

def shell_sort(alist):

    step = len(alist) // 2

    while step > 0:

        for i in range(step, len(alist)):

            # 在索引为step到len（L）上，比较L[i]和L[i-step]的大小

            while i >= step and alist[i] < alist[i - step]:

                # 这里可以调整step从小到大或者从大到小排列

                alist[i], alist[i - step] = alist[i - step], alist[i]

                i -= step

        step //= 2

if __name__ == "__main__":

    li = [1, 3, 2, 32, 5, 4]

    print(li)

    shell_sort(li)

    print(li)

巴特西

排序算法之希尔排序的python实现

最新文章

热门文章