Python|堆排序
说明
- 排序的定义
对一序列对象根据某个关键字进行排序。
- 术语说明
稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序 ：所有排序操作都在内存中完成；
外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
时间复杂度 ：一个算法执行所耗费的时间。
空间复杂度 ：运行完一个程序所需内存的大小。
n: 数据规模
In-place: 占用常数内存，不占用额外内存
一般来说，堆排序可以采用in-place在数组上实现。具体算法描述如下：
算法描述
步骤1：将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
步骤2：将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
步骤3：由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
def heapSort(todoList):
length = len(todoList)
if length < 2:
return todoList
while True:
for i in range(int(length / 2) + 1, -1, -1):
left = 2 * i + 1
right = 2 * i + 2
if left < length and todoList[i] < todoList[left]:
todoList[i], todoList[left] = todoList[left], todoList[i]
if right < length and todoList[i] < todoList[right]:
todoList[i], todoList[right] = todoList[right], todoList[i]
todoList[0], todoList[length - 1] = todoList[length - 1], todoList[0]
if length == 1:
break
length -= 1
return todoList现在对10000个随机生成的数据进行排序，然后比较两者消耗的时间。
t1=time.time()
new1=quickSort(randomList)
t2=time.time()
print(t2-t1)
t3=time.time()
new2=heapSort(randomList)
t4=time.time()
print(t4-t3)快速排序耗时：0.06383633613586426
插入排序耗时：5.124305009841919
选择排序耗时：10.545299053192139
堆排序耗时：29.556565046310425
完整的代码依旧放在了微信公众号，后台回复堆排序即可获取源代码。或者可以直接看下面的源代码把。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-01-27，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读