Q：堆排序
A：
1 堆排序算法（图解详细流程）
2 堆排序
Q：排序算法时间复杂度与稳定性
选择排序为什么不稳定：举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
Q：希尔排序
Q：基数排序和桶排序
Q：冒泡排序
# 冒泡排序
a = list(map(int, input().strip().split()))
le = len(a)
# 外层循环是遍历次数
for k in range(0, le - 1):
# 内层循环是遍历a[0:le-k-1]的元素
i = 0
while i < le - k - 1:
j = i + 1
# 只需要考虑这一种情况就行了
if a[j] < a[i]:
a[j], a[i] = a[i], a[j]
i += 1
print(a)
Q：堆排序
'''
堆排序思想：想要对堆排序，先得构造一个最大堆/最小堆
如何构造最大/最小堆呢？
让每个有子节点的节点都和它的子节点中的最大值比较大小，如果父节点的值大于子节点中的最大值，那就继续找前一个父节点，
否则的话，就把父节点和子节点中的最大节点交换位置，然后以这个子节点为父节点，循环更新堆
'''
def max_heapify(ary, start, end):
root = start
while True:
# 左子节点的索引
child = 2 * root + 1
if child > end:
break
# child+1是右子节点
if child + 1 <= end and ary[child] < ary[child + 1]:
child = child + 1
if ary[root] < ary[child]:
ary[root], ary[child] = ary[child], ary[root]
root = child
else:
break
def heap_sort(ary):
n = len(ary)
first = int(n / 2 - 1)
for i in range(first, -1, -1):
# 先构造一个最大堆
max_heapify(ary, i, n - 1)
for i in range(n - 1, 0, -1):
# 每次将堆顶元素与堆尾元素交换位置
ary[i], ary[0] = ary[0], ary[i]
# 对剩下的未排序的元素排序
max_heapify(ary, 0, i - 1)
return ary
if __name__ == '__main__':
a = [6, 5, 3, 1, 8, 7, 2, 4]
print(heap_sort(a))
