熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

交換排序之堆排序

2013-11-15 15:41:10  來源: 數據結構 
堆排序
 
  堆的定義n個元素的序列{kkkn)當且僅當滿足以下關系時稱之為堆 

 



  若將和序列{kkkn)對應的一維數組(即以一維數組作此序列的存儲結構)看成是一個完全二叉樹則堆的含義表明完全二叉樹中所有非終端結點的值均不大於(或不小於)其左右孩子結點的值由此若序列{kkkn)是堆則堆頂元素(或完全二叉樹的根)必為序列中n個元素的最小值(或最大值)這兩種堆分別稱之為小根堆和大根堆
 
  堆排序(Heap Sort)對一組待排序的關鍵字首先是把它們按堆的定義排列成一個序列(稱為初建堆)這就找到了最大關鍵字然後將最大的關鍵字取出用剩下的關鍵字再重建堆便得到次大關鍵字如此反復進行直到把全部關鍵字排好序為止
 
堆排序算法


 
堆排序的平均時間復雜度接近於O(nlgn)
堆排序是一種不穩定的排序方法
From:http://tw.wingwit.com/Article/program/sjjg/201311/23797.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.