美文网首页
算法导论第6.4章 - 堆排序算法

算法导论第6.4章 - 堆排序算法

作者: 彩虹小星星 | 来源:发表于2021-09-24 23:09 被阅读0次

    伪代码利用了维护堆和建立堆的部分

    堆排序

    HEAPSORT(A)
      BUILD-MAX-HEAP(A)
        for i = A.length downto 2
          exchange A[1] with A[i]
          A.heap-size = A.heap-size - 1
          MAX-HEAPIFY(A, 1)
    

    建立堆

    BUILD-MAX-HEAP(A)
      A.heap-size = A.length
      for i = int(A.length / 2) downto 1
        MAX-HEAPIFY(A, i)
    

    维护堆的性质

    MAX-HEAPIFY(A, i)
      l = LEFT(i)
      r = RIGHT(i)
      if l <= A.heap-size and A[l] > A[i]
        largest = l
      else largest = i
      
      if r <= A.heap-size and A[r] > A[largest]
        largest = r
    
      if largest <> i
        exchange A[i] with A[largest]
        MAX-HEAPIFY(A, largest)
    

    在建立好的堆里面,根部的元素是最大的,然后把这个最大的元素和A[n]进行替换,
    剩下的节点再进一步进行维护堆的性质和建立堆,如此递归到调整完所有元素,
    结束的时候可以获得排好序的数组。

    HEAPSORT的复杂程度为 O(nlgn)

    相关文章

      网友评论

          本文标题:算法导论第6.4章 - 堆排序算法

          本文链接:https://www.haomeiwen.com/subject/yxetnltx.html