当前位置: > python教程 > python高级教程 >

python实现堆排序代码
栏目分类:python高级教程   发布日期:2019年03月14日 16:01:15   浏览次数:

        在python的排序算法的系列文章中介绍过了选择排序,冒泡排序,插入排序,快速排序。接下来我将展示python中堆排序的实现。
                                               

1.堆排序
堆是一种完全二叉树的结构,可以分为大根堆和小根堆。
大根堆中每个结点的值都大于或等于左右孩子结点,小根堆中每个结点的值都小于或等于左右孩子结点。接下来将展示python中用堆实现的排序,代码如下:
def heap_sort(lis):
   def heap_adjust(input_list, parent, length):
      temp = input_list[parent]
      child = 2 * parent + 1
      while child < length:
         if child + 1 < length and input_list[child] < input_list[child + 1]:
            child += 1

         if temp > input_list[child]:
            break
         input_list[parent] = input_list[child]
         parent = child
         child = 2 * child + 1
      input_list[parent] = temp

   if lis == []:
      return []
   lis = lis.copy()
   length = len(lis)
   for i in range(0, length // 2 + 1)[::-1]:
      heap_adjust(lis, i, length)

   for j in range(1, length)[::-1]:
      temp = lis[j]
      lis[j] = lis[0]
      lis[0] = temp

      heap_adjust(lis, 0, j)
   return lis
测试代码如下:
li = [20, 17, 31, 55, 44, 77, 45, 93, 100, 9, 226,-1,-2,45]
lis = [20.09, 20.08, 1,0,11]
print(heap_sort(li))
print(heap_sort(lis))
'''
[-2, -1, 9, 17, 20, 31, 44, 45, 45, 55, 77, 93, 100, 226]
[0, 1, 11, 20.08, 20.09]
'''
结语
    好了,这就是python中的堆排序算法的实现,你学到了么?

相关热词:

热门关键词
python字符串
     
python教程 python爬虫 python人工智能 Python+大数据 python问答