iT邦幫忙

2021 iThome 鐵人賽

DAY 27
0
Software Development

程式菜鳥自學C++資料結構演算法系列 第 27

[Day27]程式菜鳥自學C++資料結構演算法 – 堆積排序法(Heap sort)

前言:在第16、17天的時候有介紹到堆積,今天要利用堆積的特性來實現排序法,忘記或不知道堆積是甚麼的人可以回去這兩篇看看。

堆積排序:
快速幫大家複習一下,堆積是一顆完整二元樹,且堆積的父節點都比其左右子節點的資料大或相等,而堆積排序就是一種樹狀結構的排序法,最主要的工作就是建立「堆積」。
建立好堆積後就可以開始執行堆積排序,操作步驟可以大致分成三個階段

  1. 從二元樹調整節點或建立成堆積。
  2. 在輸出堆積的根節點後,將剩下的二元樹節點重建成堆積。
  3. 重複操作直到所有節點輸出。
    https://ithelp.ithome.com.tw/upload/images/20211011/20140187DDAMdTemml.png

執行效率分析:堆積排序法的執行效率是當排序的資料個數為n時,堆積排序的主迴圈一共執行n-1次,每次執行的效率為樹高(即Log n),可以得知時間複雜度為O(n Log n)。

堆積排序法不需要額外的記憶體空間,不過這種排序法並不穩定,因為在調節根節點時,可能會交換到相同件值得元素。

堆積排序實作:這次的排序會實作在之前堆積的檔案,因為有很多已經寫好的函示會使用到,大家可以先把堆積實作的檔案找出來。

首先要來修改之前向下調整的函式。
如果不想改原來的程式,可以先複製下來然後照著上面改,但是函式名稱要修改,不然程式會不知道要執行哪個向下調整的方法。
https://ithelp.ithome.com.tw/upload/images/20211011/201401871qZQq4tWo2.png

接著是堆積排序的主要執行方法。
https://ithelp.ithome.com.tw/upload/images/20211011/20140187daUNEQuXut.png

最後來看看執行結果。
https://ithelp.ithome.com.tw/upload/images/20211011/20140187MPxNyGqyya.png

這樣堆積排序就完成了。
https://ithelp.ithome.com.tw/upload/images/20211011/20140187AaZBD62jXT.png

本日小結:堆積排序法的執行速度在各排序法中也是佼佼者,但是因為堆積需要使用到樹狀結構,不僅架構時比較麻煩,如果之後有出錯或需要維護的話也會稍嫌困難,在撰寫程式時,這些問題都是必須要納入考量的。雖然這麼說好像很複雜似的,但是簡單的堆積排序其實只要使用一般的陣列就可以時做出來,就如同今天的實作一樣,下一篇要來介紹基數排序法(^・ω・^ )

template<typename T>
void heapsort_down_adjust(vector<T>& data, int s,int m) { //從下標為s的元素開始調整
	T t = data[s];  //把s節點的資料放入t元素變量內,表示s最後的去處
	for (int j = 2 * s + 1; j <= m;) { //先找到s的左子節點{j = 2 * s + 1}
		if (j < m && data[j] < data[j + 1]) //j可想成節點的編號,data[j]則是節點內的資料
			j++; //j指向較大的子節點
		if (!(t < data[j])) break; //如果t(data[s])沒有小於data[j],則跳出迴圈
		data[s] = data[j]; //接著開始移動元素和指標
		s = j; j = 2 * j;
	}
	data[s] = t;
}

template<typename T>
void heap_sort(vector<T>& data){
	int n = data.size();
	for (int s = floor((data.size() - 1 - 1) / 2); s >= 0; s--) //建立堆疊
		heapsort_down_adjust(data, s, n - 1); //s~n-1之間
	for (int i = n - 1; i > 0; i--) {
		swap(data[0], data[i]); //交換兩元素
		heapsort_down_adjust(data, 0, i - 1); //0~i-1之間
	}
}

上一篇
[Day26]程式菜鳥自學C++資料結構演算法 – 合併排序法(Merge Sort)
下一篇
[Day28]程式菜鳥自學C++資料結構演算法 – 基數排序法(Radix sort)
系列文
程式菜鳥自學C++資料結構演算法30

尚未有邦友留言

立即登入留言