代碼如下:

// 思想：// 使用了桶排序中桶的思想,但它比桶排序更精明,它只需要十個桶,因為他的排序思想是分別對元素中 // 的個位,十位,百位....進(jìn)行排序.// 也就是說,首先對所有數(shù)以個位數(shù)的大小進(jìn)行排序,然后再對所有數(shù)以他們的十位數(shù)進(jìn)行排序,依次類推.// 在整個過程中會使得原始序列逐漸趨近有序,待將最高位排完之后完全有序.// 想想為什么是從個位開始而不是從最高位開始呢,按道理從最高位開始的話每次都能得出一部分?jǐn)?shù)的正確大小關(guān)系.// 確實可以從最高位開始,而且可以減少比較次數(shù),但是從最高位開始會有一個致命缺點,那就是在如果從高位開始,在對高位相同的// 數(shù)繼續(xù)排序時,又需要另外創(chuàng)建十個桶對他們排序,其實也就是說最終的結(jié)果就是真多每一個不同的元素都會為它創(chuàng)建一個桶,// 如果待排序序列有10000個不同的元素,那么從高位開始比較的方法就需要創(chuàng)建10000個桶,而從個位開始比較的方法可以重復(fù)使用// 那10個桶,如果序列個數(shù)更多那么這樣的性能差異就更明顯,所以雖然減少了比較次數(shù)但浪費了非常多的空間,得不償失.// 所以我們說基數(shù)排序的話都默認(rèn)的是從個位開始比較的.#include <iostream> #include <cmath> #include <list> using namespace std;void RadixSort(int *a, int len) {int max = a[0];//遍歷待排序序列獲取最大值for (int i = 1; i < len; i++)if (a[i] > max) max = a[i];//計算最大值位數(shù)int digits = 1;while (max / 10 > 0){digits++;max /= 10;}//創(chuàng)建10個桶，因為需要頻繁地往桶里面插入元素，所以我們使用list容器list<int>bucket_list[10];for (int i = 1; i <= digits; i++){for (int j = 0; j < len; j++){int radix = static_cast<int>(a[j] / pow(10, i - 1)) % 10;bucket_list[radix].push_back(a[j]);}//每完成一輪便要將桶里的元素按順序合并到原序列int k = 0;for (int n = 0; n < 10; n++){for (auto value : bucket_list[n]){a[k++] = value;}bucket_list[n].clear();}} }int main() {int a[] = { 12,314,14,234,32,511,32,412,5,3575 };RadixSort(a, 10);for (int i = 0; i < 10; i++) cout << a[i] << " ";cout << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的C++ 简单实现基数排序(list容器)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。