Python堆排序原理与实现方法详解-创新互联

本文实例讲述了Python堆排序原理与实现方法。分享给大家供大家参考，具体如下：

创新互联公司坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都网站设计、成都做网站、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的怀化网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

在这里要事先说明一下我也是新手，很多东西我了解不是很深入，写算法完全是锻炼自己逻辑能力同时顺带帮助读研的朋友么解决一些实际问题。所以很多时候考虑的东西不是很全面能请各位看到博文的大牛们指正。对于排序算法说实在的我觉得已经写烂了，但是为什么还是要过一遍呢？还是为了能够打牢基础。说一下自己的看法，对于已经的玩烂的算法因该怎么学。首先最重要的还是了解算法的基本模型和算法思想，我觉得这是非常重要的。其次的话首先先尝试自己实现算法每个步骤的功能，当遇到瓶颈的时候回去看算法思想。当你写出来的时候就应该去网上找找有没有更好的实现方法。编程大的魅力在于每个人都有每个人的套路。然后去思考自己还有哪些地方写的不够好。写算法实际上目标只有两个，对基础语法的巩固和对算法思想的理解。

堆排序

堆

在这里首先要先解释一下什么是堆，堆栈是计算机的两种最基本的数据结构。堆的特点就是FIFO(first in first out)先进先出，这里的话我觉得可以理解成树的结构。堆在接收数据的时候先接收的数据会被先弹出。

栈的特性正好与堆相反，是属于FILO(first in/last out)先进后出的类型。栈处于一级缓存而堆处于二级缓存中。这个不是本文重点所以不做过多展开。

堆排序节点访问和操作定义

堆节点的访问

在这里我们借用wiki的定义来说明：

通常堆是通过一维数组来实现的。在阵列起始位置为0的情况中

(1)父节点i的左子节点在位置(2*i+1);
(2)父节点i的右子节点在位置(2*i+2);
(3)子节点i的父节点在位置floor((i-1)/2);

堆操作

堆可以分为大根堆和小根堆，这里用大堆的情况来定义操作:

(1)大堆调整(MAX_Heapify):将堆的末端子节点作调整，使得子节点永远小于父节点。这是核心步骤，在建堆和堆排序都会用到。比较i的根节点和与其所对应i的孩子节点的值。当i根节点的值比左孩子节点的值要小的时候，就把i根节点和左孩子节点所对应的值交换，当i根节点的值比右孩子的节点所对应的值要小的时候，就把i根节点和右孩子节点所对应的值交换。然后再调用堆调整这个过程，可见这是一个递归的过程。

(2)建立大堆(Build_Max_Heap):将堆所有数据重新排序。建堆的过程其实就是不断做大堆调整的过程，从len/2出开始调整，一直比到第一个节点。

(3)堆排序(HeapSort):移除位在第一个数据的根节点，并做大堆调整的递归运算。堆排序是利用建堆和堆调整来进行的。首先先建堆，然后将堆的根节点选出与最后一个节点进行交换，然后将前面len-1个节点继续做堆调整的过程。直到将所有的节点取出，对于n个数我们只需要做n-1次操作。

这里用网上的一张直观图来感受一下

代码：

# -*- coding: utf-8 -*-
#! python2
import random
def MAX_Heapify(heap,HeapSize,root):#在堆中做结构调整使得父节点的值大于子节点
  left = 2*root + 1
  right = left + 1
  larger = root
  if left < HeapSize and heap[larger] < heap[left]:
    larger = left
  if right < HeapSize and heap[larger] < heap[right]:
    larger = right
  if larger != root:#如果做了堆调整则larger的值等于左节点或者右节点的，这个时候做对调值操作
    heap[larger],heap[root] = heap[root],heap[larger]
    MAX_Heapify(heap, HeapSize, larger)
def Build_MAX_Heap(heap):#构造一个堆，将堆中所有数据重新排序
  HeapSize = len(heap)#将堆的长度当独拿出来方便
  for i in xrange((HeapSize -2)//2,-1,-1):#从后往前出数
    MAX_Heapify(heap,HeapSize,i)
def HeapSort(heap):#将根节点取出与最后一位做对调，对前面len-1个节点继续进行对调整过程。
  Build_MAX_Heap(heap)
  for i in range(len(heap)-1,-1,-1):
    heap[0],heap[i] = heap[i],heap[0]
    MAX_Heapify(heap, i, 0)
  return heap
if __name__ == '__main__':
  a = [30,50,57,77,62,78,94,80,84]
  print a
  HeapSort(a)
  print a
  b = [random.randint(1,1000) for i in range(1000)]
  print b
  HeapSort(b)
  print b

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

当前文章：Python堆排序原理与实现方法详解-创新互联
文章起源：http://cxhlcq.cn/article/ddhgeh.html