一、希尔排序
1. 定义
- 希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。
- 它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。
2. 动画演示
3. 代码实现
def shell_sort(l):
n = len(l)
# 定义gap为排序间隔
gap = int(n/2)
# 最外层循环到gap=1为止
while gap > 0:
# 这层为循环的轮数
for i in range(0, gap):
# 插入排序
# j j+gap j+2*gap ....
for j in range(i+gap, n, gap):
for k in range(j, 0, -gap):
if l[k] < l[k-gap]:
l[k], l[k-gap] = l[k-gap], l[k]
else:
break
gap = int(gap/2)
l = [7,8,9,1,2,3,4,5,6]
shell_sort(l)
print(l)
4. 效率分析
- 时间复杂度：O(nlognlogn)
- 稳定性：不稳定
- 空间复杂度：O(1) 原地排序
二、归并排序
1. 定义
- 归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法(Divide and Conquer）的一个非常典型的应用。
- 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
2. 动画演示
3. 代码实现
def merge_sort(l, start, end):
if start + 1 >= end:
return
length = end-start+1
mid = start + int(length/2)
# 分
merge_sort(l, start, mid)
merge_sort(l, mid, end)
# 治
new = []
k = start
i = start
j = mid
while k < end:
while i < mid and (j >= end or l[i] <= l[j]):
new.append(l[i])
i += 1
k += 1
while j < end and (i >= mid or l[i] > l[j]):
new.append(l[j])
j += 1
k += 1
m = start
for item in new:
l[m] = item
m += 1
l = [8,7,6,6,5,4,3,3,1,2]
merge_sort(l, 0, len(l))
print(l)
4. 效率分析
- 时间复杂度：O(nlogn)
- 稳定性：稳定
- 空间复杂度：O(n) 每一层都需要申请和原数组一样大的空间
三、堆排序
1. 定义
1. 堆的定义
- 堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。堆满足下列性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值。（大根堆/小根堆）
- 堆总是一棵完全二叉树。
-
注：二叉堆是一颗完全二叉树，且堆中某个节点的值总是不大于其父节点的值，该完全二叉树的深度为 k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边。
- 图示：
2. 添加/删除元素
3. 堆排序
先通过shift up构造小根堆/大根堆，在通过shift down取出数据
2. 动画演示
3. 代码实现
# 小根堆
class min_heap():
def __init__(self):
# 使用线性表存储堆数据，第一个位置不使用，用0填充
self.__data = [0]
# 往堆中插入数据
def shift_up(self, l):
i = 1
while i <= len(l):
self.__data.append(l[i-1])
cur = i
# 依次与父节点比较
while cur > 1 and self.__data[cur] < self.__data[int(cur/2)]:
self.__data[cur], self.__data[int(cur/2)] = self.__data[int(cur/2)], self.__data[cur]
cur = int(cur/2)
i += 1
print(self.__data)
# 从堆中取出当前最小元素
def shift_down(self):
result = []
length = len(self.__data)
i = length-1
while i > 1:
result.append(self.__data[1])
self.__data[1] = self.__data[i]
self.__data.pop()
i -= 1
cur = 1
# 依次与左右子节点中较小的值比较
while cur <= i:
if 2*cur + 1 <= i:
# 左子节点 <= 右子节点
if self.__data[2*cur] <= self.__data[2*cur + 1]:
# cur > 左子节点时则交换，否则 break
if self.__data[cur] > self.__data[2 * cur]:
self.__data[cur], self.__data[2 * cur] = self.__data[2 * cur], self.__data[cur]
cur = 2 * cur
else:
break
# 左子节点 > 右子节点
else:
# cur > 右子节点时则交换，否则 break
if self.__data[cur] > self.__data[2 * cur + 1]:
self.__data[cur], self.__data[2 * cur + 1] = self.__data[2 * cur + 1], self.__data[cur]
cur = 2 * cur + 1
else:
break
elif 2*cur <= i:
# cur > 左子节点时则交换，否则 break
if self.__data[cur] > self.__data[2 * cur]:
self.__data[cur], self.__data[2 * cur] = self.__data[2 * cur], self.__data[cur]
cur = 2 * cur
else:
break
else:
break
return result
if __name__ == '__main__':
h = min_heap()
h.shift_up([3,2,4,5,8,7,3,6,1,3,4,6,4,3,2,1,0,9,8,5,6,7,8,9])
print(h.shift_down())
4. 效率分析
- 时间复杂度：
- shift up: O(logn)
- shift down: O(logn)
- 稳定性：不稳定
- 空间复杂度：O(n)
