Blame: Algorithm/BucketSort.cpp - huihut/interview

huihut / interview UNCLAIMED

📚 C/C++ 技术面试基础知识总结，包括语言、程序库、数据结构、算法、系统、网络、链接装载库等知识及面试经验、招聘、内推等信息。This repository is a summary of the basic knowledge of recruiting job seekers and beginners in the direction of C/C++ technology, including language, program library, data structure, algorithm, system, network, link loading library, interview experience, recruitment, recommendation, etc.

0 0 5 C++

Normal View History Raw

-												添加插入、堆、归并、希尔、计数、桶、基数排序算法及其实现

											
										
										
											2018-04-16 13:30:03 +08:00
+								#include<iterator>
 								#include<iostream>
 								#include<vector>
-												创建test分支

											
										
										
											2018-06-19 17:15:53 +08:00
+								using std::vector;
-												添加插入、堆、归并、希尔、计数、桶、基数排序算法及其实现

											
										
										
											2018-04-16 13:30:03 +08:00
 								/*****************
-												修改排序算法代码

											
										
										
											2018-04-16 13:38:05 +08:00
+								桶排序：将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。
-												添加插入、堆、归并、希尔、计数、桶、基数排序算法及其实现

											
										
										
											2018-04-16 13:30:03 +08:00
+								桶排序序思路：
 . 设置一个定量的数组当作空桶子。
 . 寻访序列，并且把项目一个一个放到对应的桶子去。
 . 对每个不是空的桶子进行排序。
 . 从不是空的桶子里把项目再放回原来的序列中。
 								假设数据分布在[0，100)之间，每个桶内部用链表表示，在数据入桶的同时插入排序，然后把各个桶中的数据合并。
 								*****************/
 								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;
 									}
 								}