堆排序
堆是具有下列性质的完全二叉树： 每个分支节点的值都大于或等于其左右孩子的值，称为大顶堆； 每个分支节点的值都小于或等于其做右孩子的值，称为小顶堆； 因此，其根节点一定是所有节点中最大（最小）的值。
如果按照层序遍历的方式（广度优先）给节点从1开始编号，则节点之间满足如下关系：
${k_i >= k_(2i) , k_i >= k_(2i+1)}$ 或${k_i <= k_(2i),k_i <= k_(2i+1)}$ , \({1 <= i <= [^n_2]}\)
堆排序（Heap Sort）就是利用大顶堆或小顶堆的性质进行排序的方法。堆排序的总体时间复杂度为O(nlogn)。（下面采用大顶堆的方式）
其核心思想是：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆的根节点。将它与堆数组的末尾元素交换，然后将剩余的n-1个序列重新构造成一个大顶堆。反复执行前面的操作，最后获得一个有序序列。
#!/usr/bin/env python
# -*- coding:utf-8 -*-
class SQList:
def __init__(self, lis=None):
self.r = lis
def shell_sort(self):
"""希尔排序"""
lis = self.r
length = len(lis)
increment = len(lis)
while increment > 1:
increment = int(increment/3)+1
for i in range(increment+1, length):
if lis[i] < lis[i - increment]:
temp = lis[i]
j = i - increment
while j >= 0 and temp < lis[j]:
lis[j+increment] = lis[j]
j -= increment
lis[j+increment] = temp
def __str__(self):
ret = ""
for i in self.r:
ret += " %s" % i
return ret
if __name__ == '__main__':
sqlist = SQList([4, 1, 7, 3, 8, 5, 9, 2, 6, 0,123,22])
sqlist.shell_sort()
print(sqlist)
参考资料
《大话数据结构》