说明
对一序列对象根据某个关键字进行排序。
稳定 :如果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
完整的代码依旧放在了微信公众号,后台回复堆排序即可获取源代码。或者可以直接看下面的源代码把。
本文分享自 Python与MySQL 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!