用 python 实现各种排序算法(4)

当前位置:

首页 > Python基础教程 >

用 python 实现各种排序算法(4)

不稳定，时间复杂度平均时间 O(nlogn) 最差时间O(n^s)1<s<2

堆排序 ( Heap Sort )

"堆”的定义：在起始索引为 0 的“堆”中：

节点 i 的右子节点在位置 2 * i + 24) 节点 i 的父节点在位置 floor( (i - 1) / 2 ) : 注 floor 表示“取整”操作

堆的特性：

每个节点的键值一定总是大于（或小于）它的父节点

“最大堆”：

“堆”的根节点保存的是键值最大的节点。即“堆”中每个节点的键值都总是大于它的子节点。

上移，下移：

当某节点的键值大于它的父节点时，这时我们就要进行“上移”操作，即我们把该节点移动到它的父节点的位置，

而让它的父节点到它的位置上，然后我们继续判断该节点，直到该节点不再大于它的父节点为止才停止“上移”。

现在我们再来了解一下“下移”操作。当我们把某节点的键值改小了之后，我们就要对其进行“下移”操作。

方法：

我们首先建立一个最大堆(时间复杂度O(n))，然后每次我们只需要把根节点与最后一个位置的节点交换，然后把最后一个位置排除之外，然后把交换后根节点的堆进行调整(时间复杂度 O(lgn) )，即对根节点进行“下移”操作即可。堆排序的总的时间复杂度为O(nlgn).

代码如下：

						#!/usr/bin env python  

						# 数组编号从 0开始  

						def left(i):  

						    return 2*i +1  

						def right(i):  

						    return 2*i+2  

						#保持最大堆性质 使以i为根的子树成为最大堆  

						def max_heapify(A, i, heap_size):  

						    if heap_size <= 0:  

						        return   

						    l = left(i)  

						    r = right(i)  

						    largest = i # 选出子节点中较大的节点  

						    if l  A[largest]:  

						        largest = l  

						    if r  A[largest]:  

						        largest = r  

						    if i != largest :#说明当前节点不是最大的，下移  

						        A[i], A[largest] = A[largest], A[i] #交换  

						        max_heapify(A, largest, heap_size)#继续追踪下移的点  

						    #print A  

						# 建堆    

						def bulid_max_heap(A):  

						    heap_size = len(A)  

						    if heap_size >1:  

						        node = heap_size/2 -1  

						        while node >= 0:  

						           max_heapify(A, node, heap_size)  

						           node -=1  

						# 堆排序 下标从0开始  

						def heap_sort(A):  

						    bulid_max_heap(A)  

						    heap_size = len(A)  

						    i = heap_size - 1   

						    while i > 0 :  

						        A[0],A[i] = A[i], A[0] # 堆中的最大值存入数组适当的位置，并且进行交换  

						        heap_size -=1 # heap 大小 递减 1  

						        i -= 1 # 存放堆中最大值的下标递减 1  

						        max_heapify(A, 0, heap_size)  

						if __name__ == '__main__' :  

						    A = [10, -3, 5, 7, 1, 3, 7]  

						    print 'Before sort:',A  

						    heap_sort(A)  

						    print 'After sort:',A

栏目列表