希尔排序算法

思路：希尔排序算法其实就是使用步长来抽离出子数组，子数组再用插入排序算法来排序，减少对比量。具体算法思路可以查看排序算法研究之希尔排序（shell sort）。

代码实现

Python实现

import math


class ShellSort:

    @staticmethod
    def sort(array):
        length = len(array)
        step = length
        while step != 0:
            step = math.floor(step / 2)
            print("step:%s" % step)
            for index in range(0, step, 1):
                # 根据步长，抽离出index，用于插入排序
                list_after_step = []
                i = index
                while i < length:
                    list_after_step.append(i)
                    i = i + step

                print("\t list_after_step:%s" % list_after_step)
                # 插入排序
                for i in range(1, len(list_after_step)):
                    # 从后往前依次插入
                    for j in range(i, 0, -1):
                        back = list_after_step[j]
                        front = list_after_step[j - 1]
                        if array[back] > array[front]:
                            continue
                        array[back], array[front] = array[front], array[back]

        return array


def main():
    array = [5, 3, 2, 1, 9, 8, 4, 0]
    print("希尔排序：%s" % ShellSort.sort(array))

输出结果

step:4（下面是根据步长抽离出来的用于插入排序的子数组，子数组由原数组的索引构成，用于映射数据）
	 list_after_step:[0, 4]
	 list_after_step:[1, 5]
	 list_after_step:[2, 6]
	 list_after_step:[3, 7]
step:2
	 list_after_step:[0, 2, 4, 6]
	 list_after_step:[1, 3, 5, 7]
step:1（最后一次的比较就是整个数组的“插入排序”过程）
	 list_after_step:[0, 1, 2, 3, 4, 5, 6, 7]
step:0
希尔排序：[0, 1, 2, 3, 4, 5, 8, 9]

附录

平均时间复杂度是：$O(n^{1.3})$
空间复杂度是：$O(1)$
稳定性：不稳定
复杂性：实现起来较为复杂

博文

各个排序算法的时间复杂度和稳定性，快排的原理