现在的位置: 首页 > 综合 > 正文

《算法导论》第六章-堆排序(伪代码)

2018年05月01日 ⁄ 综合 ⁄ 共 862字 ⁄ 字号 评论关闭

堆排序

根据《算法导论》中的伪代码,改写如下,可能更好理解

伪代码:

//建堆,运行时间的界T(n) =O(N)

BuildHeap(A)

        n = length(A)

        for  i = n/2 downto 1  do   //从非叶子节点开始,自底往上,使A变成最大堆

               Max_Heapify(A, i, n)

end

//调整为最大堆 ,T(n) = O(lgn)

Max_Heapify(A,idx,max) //idx:数组开始的下标,max:最大的数组下标
    left = 2*idx
    right = 2*idx
    if(left<max and A[left]>A[idx]) then
        largest = left
    else
        largest = idx
    if(right < max and A[right]>A[largest]) then
        largest = ritht
    
    if(largest != idx) then
        exchange A[largest] with A[idx]
        Max_Heapify(A,largest,max) //交换位置后,还需要调整它的子树
end


HeapSort(A)

      BuildHeap(A)

      for i = length(A) downto 2   do 

             exchange  A[1] with A[i] //把最大堆根节点与最后一个互换

             Max_Heapify(A,1, i-1) //把交互后的排除在堆之外,重新从1到i-1,调整堆

end

性能分析:

时间复杂度:

堆是一个完全二叉树,设树高为k=log2n+1,从根到叶的调整,关键码比较的次数为2(k-1),交换的次数至多为k次。所以比较的次数不超过

2*(log2(n-1)+log2(n-2)+....+log22)<2nlog2n

而比较的次数不超过4n.所以堆排序的时间复杂度为O(nlogn).

空间复杂度:

需要一个单元的辅助空间用于交换,所以辅助空间为O(1).

稳定性:

堆排序调整过程中存在着交换,所以堆排序是一个不稳定的排序算法。

抱歉!评论已关闭.