iT邦幫忙

2021 iThome 鐵人賽

DAY 29
0
Software Development

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

[Day29]程式菜鳥自學C++資料結構演算法 – 桶排序法(Bucket sort)

前言:桶排序又名箱排序,究竟這個特殊的排序法是怎麼運作的,讓我們一來探討!

桶排序:

和上一篇的基數排序一樣是非比較型的排序法。運作原理通常是會先建立一些用來存放資料的桶子,每個桶子都有對應的資料區間,再將待排序的元素分別放到對應區間的桶內,並在桶內進行排序(在桶內的排序可以使用其他排序法,又或著可以用遞迴的方式繼續執行桶排序),最後在把桶內的元素取出就完成了,換言之,桶排序是用分析鍵值的分布來排序的。
https://ithelp.ithome.com.tw/upload/images/20211013/20140187tFenLiyaug.png

執行效率分析:如果共有n個元素需要排序,而這些元素剛好都分散在不同的桶子中,也就是不必在桶內進行額外的排序,這實是最理想的狀況,時間複雜度為O(n+m)(m用來表示桶子的數量);但如果所有的元素都在一個桶內,則為最差的情況,時間複雜度為O(n^2)。

必須使用桶來暫時存放資料,所以需要用到額外的記憶體空間。屬於穩定性的排序法,因為元素要分別放入桶內進行排序,所以相同鍵值的元素,排序後相對位置不會改變。

桶排序實作:
https://ithelp.ithome.com.tw/upload/images/20211013/201401874HHzizEYvM.png
https://ithelp.ithome.com.tw/upload/images/20211013/20140187FMeX4NfANB.png
https://ithelp.ithome.com.tw/upload/images/20211013/20140187yW1j4WeZEk.png

可以看到成功輸出兩組數組,負數也能在排序範圍。
https://ithelp.ithome.com.tw/upload/images/20211013/201401879zTwD8p5gv.png

各排序法的比較:最後來複習並比較一下有介紹過的排序法。
https://ithelp.ithome.com.tw/upload/images/20211013/201401874vXYPeZ7mI.png

本日小結:總算完結了排序的部分,其實排序法遠遠不止這些,這些是在課堂上比較有接觸到的才分享給大家,如果還有參加鐵人賽,或許還有機會跟大家一起討論,明天就沒有要在講新的東西了,純粹跟大家分享鐵人賽的心得和感想,感謝大家看到最後(〃^∇^)o

template <typename T>
void bucket_sort(vector<T>& data, const int bucket_num = 0) { //傳入桶的數目作為參數
	T minValue = data[0], maxValue = data[0];
	for (int i = 1; i < data.size(); i++) { //求最大值最小值
		if (data[i] > maxValue)
			maxValue = data[i];
		if (data[i] < minValue)
			minValue = data[i];
	}
	int bucket_n = maxValue - minValue + 1; //設定系統默認的桶數
	if (bucket_num != 0)
		bucket_n = bucket_num; //如果系統有傳回bucket_n,則將bucket_n設為桶數
	T interval = (maxValue - minValue) / (bucket_n - 1); //設定桶的區間
	//公式:區間=(最大值-最小值)/(桶數-1)

	vector<vector <T>>buckets(bucket_n);
	for (auto e : data) //計算桶內元素的下標,方便後續的交換
		buckets[(e - minValue) / interval].push_back(e);

	int k = 0;
	for (int i = 0; i < bucket_n; i++) {
		int bucketSize = buckets[i].size();
		if (bucketSize > 0) { //桶內至少有一個元素
			if (bucketSize > 1) { //桶內至少有兩個元素,並進行排序
				insert_sort(buckets[i]);
			}
			for (int j = 0; j < bucketSize; j++) {
				data[k] = buckets[i][j]; //如果桶內元素大於2才要排序,否則直接取出
				k++;
			}
		}
	}
}


上一篇
[Day28]程式菜鳥自學C++資料結構演算法 – 基數排序法(Radix sort)
下一篇
[Day30]程式菜鳥自學C++資料結構演算法 – 心得總結
系列文
程式菜鳥自學C++資料結構演算法30

尚未有邦友留言

立即登入留言