國大里電研社

現在大家能使用http://dcirc.twbbs.org進入本討論區

國大里電研社

登入


版面鎖定 這個主題已被鎖定,您不能編輯或回覆這個主題。
 第 1 頁 (共 1 頁)  [ 1 篇文章 ] 

2012年 1月 20日, 22:43

離線
站務管理員
站務管理員
頭像
註冊時間: 2011年 6月 4日, 05:58
文章: 58
屆數:

一開始,讓我們先認識一下堆積(Heap)

堆積樹,一種資料結構,而堆積樹是一種二元樹
而堆積樹的父節點皆小於子節點,則為最小堆積樹
反之則為最大堆積樹,例如:下圖是一個最大堆積樹
圖檔
使用一為陣列儲存堆積樹,為了方便起見,將陣列的索引值起始設為1
設父節點為s,則子節點則為s*2以及s*2+1,如上圖

而堆積排序必須維護一個最大堆積樹,所以我們來稍微講解一下:
第一、top必為最大值,故將top直接跟最後的值交換,然後將堆積樹的範圍往前移
第二、交換後的top,跟其子節點比較,如果大於最大的子節點,則維持原最大堆積樹
第三、如小於最大子節點,則與其進行交換,重複檢查,直到符合最大堆積樹
第四、一直取出最大堆積樹的top,與堆積樹的最後交換

cpp 代碼: 選擇全部
  1. #include <iostream>
  2. #include <cstdlib>
  3.  
  4. using namespace std;
  5.  
  6. template<class T>
  7. void HeapSort(T begin, T end);
  8. template<class T>
  9. void Swap(T&, T&);
  10.  
  11. int main(){
  12.     int num[] = {99, 20, 50, 91, 1000, 5000, 10, 0};
  13.  
  14.     HeapSort(num, num + 8);
  15.     for(int i = 0; i < 8; i++)
  16.         cout << num[i] << " ";
  17.            
  18.     return 0;
  19. }
  20.  
  21. template<class T>
  22. void HeapSort(T begin, T end){
  23.     //create Heap
  24.     int len = end - begin;
  25.     int son = len - 1;
  26.     int parent = (son - 1) / 2;
  27.  
  28.     for(int i = 0; i < len; i++){
  29.         son = i;
  30.         parent = (son - 1) / 2;
  31.         while(parent >= 0 && *(begin + son) > *(begin + parent)){
  32.             Swap(*(begin + son), *(begin + parent));
  33.             son = parent;
  34.             parent = (son - 1) / 2;
  35.         }
  36.     }
  37.    
  38.     //HeapSort
  39.     parent = 0;
  40.     son = parent * 2 + 1;
  41.     while(len > 0){
  42.         Swap(*(begin), *(begin + len -1));
  43.         len--;
  44.         parent = 0;
  45.         son = parent * 2 + 1;
  46.         while(son < len){
  47.             if(son < len - 1 && *(begin + son) < *(begin + son + 1))
  48.                 son++;
  49.             if(*(begin + parent) >= *(begin + son))
  50.                 break;
  51.             Swap(*(begin + parent), *(begin + son));
  52.             parent = son;
  53.             son = parent * 2 + 1;
  54.         }
  55.        
  56.     }
  57. }
  58.  
  59. template<class T>
  60. void Swap(T &a, T &b){
  61.         T tmp = a;
  62.         a = b;
  63.         b = tmp;
  64. } 

Output:
代碼: 選擇全部
0 10 20 50 91 99 1000 5000

_________________
圖檔


回頂端 回頂端
  個人資料
 
顯示文章 :  排序  
版面鎖定 這個主題已被鎖定,您不能編輯或回覆這個主題。
 第 1 頁 (共 1 頁)  [ 1 篇文章 ] 

所有顯示的時間為 UTC + 8 小時


誰在線上

正在瀏覽這個版面的使用者:沒有註冊會員 和 1 位訪客


不能 在這個版面發表主題
不能 在這個版面回覆主題
不能 在這個版面編輯您的文章
不能 在這個版面刪除您的文章


搜尋:
前往 :  
cron