电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 排序算法总结（python版）-6 [打印本页]

作者: look_w 时间: 2019-3-7 19:36 标题: 排序算法总结（python版）-6

堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
算法描述

将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

#简单选择排序的改进
#每次在选择最小记录的同时，并根据比较结果对其他记录做出相应调整
def HeapAdjust(ls,s,length):
      tmp = ls[s]
      j = 2 * s
      while(j < length):
         if j+1 < length and ls[j] < ls[j+1]:
            j += 1
         if tmp < ls[j]:
            ls[s] = ls[j]
            s = j
         j *= 2
      ls[s] = tmp

def HeapSort(ls):
      length = len(ls)
      ls.insert(0,0)
      #构造一个大顶堆
      for i in range(length//2,0,-1):
         #将每个非叶结点及其子节点构造大顶堆
         HeapAdjust(ls, i, length+1)
      print(ls)

      for i in range(length, 1, -1):
         ls[1], ls[i] = ls[i], ls[1]
         #将ls[1,2,...i-1]重新构造一个大顶堆
         HeapAdjust(ls, 1, i)
      return ls

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)