簡單掌握桶排序算法及C++版的代碼實現(xiàn)
桶排序介紹
桶排序(Bucket Sort)的原理很簡單,它是將數(shù)組分到有限數(shù)量的桶子里。
假設(shè)待排序的數(shù)組a中共有N個整數(shù),并且已知數(shù)組a中數(shù)據(jù)的范圍[0, MAX)。在桶排序時,創(chuàng)建容量為MAX的桶數(shù)組r,并將桶數(shù)組元素都初始化為0;將容量為MAX的桶數(shù)組中的每一個單元都看作一個"桶"。
在排序時,逐個遍歷數(shù)組a,將數(shù)組a的值,作為"桶數(shù)組r"的下標(biāo)。當(dāng)a中數(shù)據(jù)被讀取時,就將桶的值加1。例如,讀取到數(shù)組a[3]=5,則將r[5]的值+1。
C++實現(xiàn)算法
假設(shè)數(shù)據(jù)分布在[0,100)之間,每個桶內(nèi)部用鏈表表示,在數(shù)據(jù)入桶的同時插入排序。然后把各個桶中的數(shù)據(jù)合并。
#include<iterator> #include<iostream> #include<vector> using namespace std; const int BUCKET_NUM = 10; struct ListNode{ explicit ListNode(int i=0):mData(i),mNext(NULL){} ListNode* mNext; int mData; }; ListNode* insert(ListNode* head,int val){ ListNode dummyNode; ListNode *newNode = new ListNode(val); ListNode *pre,*curr; dummyNode.mNext = head; pre = &dummyNode; curr = head; while(NULL!=curr && curr->mData<=val){ pre = curr; curr = curr->mNext; } newNode->mNext = curr; pre->mNext = newNode; return dummyNode.mNext; } ListNode* Merge(ListNode *head1,ListNode *head2){ ListNode dummyNode; ListNode *dummy = &dummyNode; while(NULL!=head1 && NULL!=head2){ if(head1->mData <= head2->mData){ dummy->mNext = head1; head1 = head1->mNext; }else{ dummy->mNext = head2; head2 = head2->mNext; } dummy = dummy->mNext; } if(NULL!=head1) dummy->mNext = head1; if(NULL!=head2) dummy->mNext = head2; return dummyNode.mNext; } void BucketSort(int n,int arr[]){ vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0)); for(int i=0;i<n;++i){ int index = arr[i]/BUCKET_NUM; ListNode *head = buckets.at(index); buckets.at(index) = insert(head,arr[i]); } ListNode *head = buckets.at(0); for(int i=1;i<BUCKET_NUM;++i){ head = Merge(head,buckets.at(i)); } for(int i=0;i<n;++i){ arr[i] = head->mData; head = head->mNext; } }
欄 目:C語言
下一篇:C++面試題之?dāng)?shù)a、b的值互換(不使用中間變量)
本文標(biāo)題:簡單掌握桶排序算法及C++版的代碼實現(xiàn)
本文地址:http://mengdiqiu.com.cn/a1/Cyuyan/2183.html
您可能感興趣的文章
- 01-10如何用C語言生成簡單格式的xml
- 01-10C++中簡單讀寫文本文件的實現(xiàn)方法
- 01-10簡單說說STL的內(nèi)存管理
- 01-10c語言調(diào)用匯編的方法
- 01-10c++讀寫文件流實例程序講解
- 01-10c語言 字符串轉(zhuǎn)大寫的簡單實例
- 01-10Qt 實現(xiàn)桌面雪花飄落代碼
- 01-10C中qsort快速排序使用實例
- 01-10用while判斷輸入的數(shù)字是否回文數(shù)的簡單實現(xiàn)
- 01-10c語言網(wǎng)絡(luò)編程-標(biāo)準步驟(比較簡單)


閱讀排行
本欄相關(guān)
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言的正則匹配函數(shù) c語言正則表達
- 04-02c語言用函數(shù)寫分段 用c語言表示分段
- 04-02c語言中對數(shù)函數(shù)的表達式 c語言中對
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段
- 04-02C語言中怎么打出三角函數(shù) c語言中怎
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求
隨機閱讀
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文
- 01-11ajax實現(xiàn)頁面的局部加載
- 01-10delphi制作wav文件的方法
- 01-10使用C語言求解撲克牌的順子及n個骰子
- 01-10C#中split用法實例總結(jié)
- 01-10SublimeText編譯C開發(fā)環(huán)境設(shè)置
- 08-05dedecms(織夢)副欄目數(shù)量限制代碼修改
- 04-02jquery與jsp,用jquery
- 08-05織夢dedecms什么時候用欄目交叉功能?
- 08-05DEDE織夢data目錄下的sessions文件夾有什