桶排序

大致思想:

桶排序的基本思想是假设数据在[min,max]之间均匀分布,其中min、max分别指数据中的最小值和最大值。那么将区间[min,max]等分成n份,这n个区间便称为n个桶。将数据加入对应的桶中,然后每个桶内单独排序。由于桶之间有大小关系,因此可以从大到小(或从小到大)将桶中元素放入到数组中。

分步骤图示说明:

设有数组 array = [63, 157, 189, 51, 101, 47, 141, 121, 157, 156, 194, 117, 98, 139, 67, 133, 181, 13, 28, 109],对其进行桶排序
在这里插入图片描述

  • 设置一个定量的数组当作空桶子。
  • 寻访序列,并且把项目一个一个放到对应的桶子去。
  • 对每个不是空的桶子进行排序。
  • 从不是空的桶子里把项目再放回原来的序列中。

代码:

方式一

1/*算法:桶排序*/ 2 3#include <iostream> 4#include <vector> 5#include <algorithm> 6 7using namespace std; 8 9void bksort(float A[],int l,int h){ 10 int size = h-l+1; 11 vector<float> b[size];//有size个数据,就分配size个桶 12 for(int i=l;i<=h;i++){ 13 int bi = size*A[i];//元素A[i]的桶编号 14 b[bi].push_back(A[i]);//将元素A[i]压入桶中 15 } 16 for(int i=0;i<size;i++) 17 sort(b[i].begin(),b[i].end());//桶内排序 18 int idx = l;//指向数组A的下标 19 for(int i=0;i<size;i++){//遍历桶 20 for(int j=0;j<b[i].size();j++){//遍历桶内元素 21 A[idx++] = b[i][j]; 22 } 23 } 24} 25 26int main(){ 27 float A[] = {0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68}; 28 bksort(A,2,9); 29 for(int i=0;i<10;i++) 30 cout<<A[i]<<" "; 31} 32 33

方式二:

1#include "stdafx.h" 2#include<iostream> 3#include<ctime> 4#include<vector> 5 6using namespace std; 7 8typedef unsigned long long MyLoop_t; 9 10template<typename Comparable> 11inline Comparable GetMax(vector<Comparable> &a) { 12 Comparable Max = 0; 13 for (MyLoop_t i = 0; i < a.size(); i++) 14 if (a[i] > a[Max]) 15 Max = i; 16 return a[Max]; 17} 18 19template<typename Comparable> 20void BuncketSort(vector<Comparable> &a) { 21 Comparable Max = GetMax(a); 22 23 MyLoop_t number = a.size(); 24 MyLoop_t gap =(Max/a.size())+1;//算出每个桶容量 25 MyLoop_t buncketNumber = Max/gap+1; 26 struct node { 27 Comparable element; 28 node* next; 29 }; 30 node **allBuncket = new node*[sizeof(node)*buncketNumber];//new出一个桶数组,emmmm我也成刘备了,不过我比他轻松,hhhh :-) 31 for (MyLoop_t i = 0; i < buncketNumber; i++) 32 { 33 allBuncket[i]=nullptr; 34 } 35 for (MyLoop_t i = 0; i < number; i++) {//数据入桶 36 MyLoop_t buncketLab = a[i]/gap;//取桶下标 37 if (allBuncket[buncketLab] == nullptr){//如果桶空 38 allBuncket[buncketLab] = new node; 39 allBuncket[buncketLab]->element = a[i]; 40 allBuncket[buncketLab]->next = nullptr; 41 } 42 else { 43 if (allBuncket[buncketLab]->element > a[i]) { 44 node *temp = new node; 45 temp->element = a[i]; 46 temp->next = allBuncket[buncketLab]; 47 allBuncket[buncketLab] = temp; 48 } 49 else { 50 node* temp = allBuncket[buncketLab]; 51 while (a[i] > temp->element && temp->next != nullptr && a[i]>temp->next->element) { 52 temp = temp->next; 53 } 54 node *newNode = new node; 55 newNode->element = a[i]; 56 newNode->next = temp->next; 57 temp->next = newNode; 58 } 59 } 60 } 61 MyLoop_t j = 0; 62 for (MyLoop_t i = 0; i <buncketNumber; i++) { 63 if (allBuncket[i] != nullptr) { 64 a[j++] = allBuncket[i]->element; 65 node* temp = allBuncket[i]->next; 66 while(temp!=nullptr){ 67 a[j++] = temp->element; 68 node * temp2 = temp->next; 69 delete temp; 70 temp = temp2; 71 } 72 delete allBuncket[i]; 73 } 74 } 75 delete[] allBuncket; 76} 77 78int main() 79{ 80 time_t start, end; 81 vector<int>a; 82 for (long long i = 0; i < 1000000; i++){ 83 int c = rand(); 84 a.push_back(c); 85 } 86 start = clock(); 87 BuncketSort(a); 88 end = clock(); 89 double totaltime = (double)(end - start) / CLOCKS_PER_SEC; 90 for (long long i = 1; i < 1000000; i++) 91 if (a[i] < a[i - 1]) { 92 cout << "error"; 93 return 1; 94 } 95 cout << totaltime<<'s'<<endl; 96 system("pause"); 97 return 0; 98} 99 100 101

算法复杂度:

在这里插入图片描述

下一篇:八大排序算法

代码交流 2021