箱子排序（桶排序），基数排序

#include <iostream>
#include <list>
#include <time.h>
//#include "circularListWithHeader.h"
#include "extendedChain.h"
#include <math.h>
/*本算法为箱子排序的算法* Author: zailushang* Data: 2020-06-27**目的为了熟悉C++的双向链表***/
#define BUFFSIZE 1000000
#define RADIX 100
struct studentRecord{
    //默认为公有的成员int sort;int number;std::string *name;int operator!=(const studentRecord &rht)const{
    return this->sort != rht.sort;}operator int()const{
    //赋给一个int的时候，赋予的是sort值return sort;}studentRecord():sort(0),name(NULL){
    }studentRecord(int sorts,std::string *names):sort(sorts),name(names){
    }
};
void binSort(std::list<studentRecord> &theList,int range){
    std::list<studentRecord> *p = new std::list<studentRecord>[range+1];//建立一个数组空间，用来保存各个链表clock_t t = clock();for(auto it = theList.begin();it != theList.end();it = theList.begin()){
    //使用迭代器去访问元素p[it->sort].push_back(*it);//将对应的分数报错到相应的链表中;时间复杂度theList.erase(it);}for(int i = 0; i <= range;++i){
    for(auto it = p[i].begin(); it != p[i].end();it=p[i].begin()){
    theList.push_back(*it);p[i].erase(it);}}delete []p;std::cout<<"the bin sort time is "<<float(clock()-t)/CLOCKS_PER_SEC;
}
void binSortByList(extendedChain<studentRecord> &theList,int range){
    extendedChain<studentRecord> *p = new extendedChain<studentRecord>[range+1];auto listSize = theList.mychain<studentRecord>::size();for(int i = 0; i != listSize;++i){
    studentRecord x = theList.get(0);theList.erase(0);p[x.sort].insert(0,x);}for(int j = range;j >= 0;--j){
    while(!p[j].empty()){
    studentRecord x = p[j].get(0);p[j].erase(0);theList.insert(0,x);}}delete []p;
}
void binSortUsedByRadix(extendedChain<studentRecord> &theList,int c){
    int listSize = theList.mychain<studentRecord>::size();extendedChain<studentRecord> *p = new extendedChain<studentRecord>[listSize+1];int number = 1,anotherNUmber=1;for(int i = 0; i != c;++i)number*=RADIX;anotherNUmber = number/RADIX;for(int i = 0; i != listSize;++i){
    studentRecord x = theList.get(0);theList.erase(0);p[((x.sort)%number)/anotherNUmber].insert(0,x);//这个是比较数}for(int j = listSize;j >= 0;--j){
    while(!p[j].empty()){
    studentRecord x = p[j].get(0);p[j].erase(0);theList.insert(0,x);}}delete []p;
}void radixSort(extendedChain<studentRecord> &theList,int range){
    int listSize  = theList.mychain<studentRecord>::size();std::cout<<"\nthe radix is "<<RADIX<<std::endl;int c = 1;extendedChain<studentRecord> *p = new extendedChain<studentRecord>[listSize+1];while(pow(RADIX,c) < range)c++;//获得指数的次方std::cout<<"\nthe radix is "<<c<<std::endl;for(int i = 0;i != c;i++){
    int number = 1,anotherNUmber=1;for(int j = 0;j != c;++j)number*=RADIX;anotherNUmber = number/RADIX;for(int k = 0; k != listSize;++k){
    studentRecord x = theList.get(0);theList.erase(0);p[((x.sort)%number)/anotherNUmber].insert(0,x);//这个是比较数}for(int j = listSize;j>= 0;--j){
    while(!p[j].empty()){
    studentRecord x = p[j].get(0);p[j].erase(0);theList.insert(0,x);}}//binSortUsedByRadix(theList,i+1);}delete []p;
}
int main(){
    std::list<studentRecord> listStduent;extendedChain<studentRecord> test1,test2,test3;    std::string s("test");clock_t t = clock();auto it = listStduent.begin();for(int i = 0;i != BUFFSIZE;++i,it = listStduent.begin())listStduent.insert(it,studentRecord(i,&s));//listStduent.push_front(studentRecord(i,&s));std::cout<<"use STL push_front insert "<<BUFFSIZE<<" numbers need time is "<<float(clock()-t)/CLOCKS_PER_SEC<<"\n";std::cout<<"\n********************************\n";clock_t t3 = clock();for(int i = 0;i != BUFFSIZE/1000;++i)test1.insert(0,studentRecord(i,&s));std::cout<<"use myself push_front insert "<<BUFFSIZE<<" numbers need time is "<<float(clock()-t3)/CLOCKS_PER_SEC<<"\n";std::cout<<"\n*********************\n";binSort(listStduent,BUFFSIZE);std::cout<<"\n*******************";/*for(auto it = listStduent.begin();it != listStduent.end();++it)std::cout<<(*it).sort<<" ";*//** 冒泡排序clock_t t4 = clock();test2.bubbleSort();std::cout<<"\nuse myself bubbleSort "<<BUFFSIZE<<" numbers need time is "<<float(clock()-t4)/CLOCKS_PER_SEC<<"\n";*/for(int i = 0; i != BUFFSIZE/1000;++i)test2.insert(0,studentRecord(i,&s));std::cout<<"\n*****************************\n";clock_t t5 = clock();binSortByList(test1,BUFFSIZE);std::cout<<"\nuse the list By the function that the time is "<<float(clock()-t5)/CLOCKS_PER_SEC;std::cout<<"\n*****************************";std::cout<<"\n******************************\n";clock_t t6 = clock();test2.binSort(BUFFSIZE);std::cout<<"\nuse the binSort of the member in class that the time is "<<float(clock()-t6)/CLOCKS_PER_SEC;/** for(auto it = test2.begin();it != test2.end();++it)std::cout<<(*it).sort<<" ";*/for(int i = 0; i != BUFFSIZE/1000;++i)test3.insert(0,studentRecord(i,&s));std::cout<<"\n******************************";clock_t t7 = clock();radixSort(test3,BUFFSIZE);std::cout<<"\nuse the binSort of the member in class that the time is "<<float(clock()-t7)/CLOCKS_PER_SEC;std::cout<<"\n******************************\n";return 0;
}
/*经过上述的测试比较，发现STL官方给的双向链表不如自己写的单向链表的插入和箱子排序速度快，因为主要是插入的时候需要两个指针进行要转换，肯定会比单链表慢。冒泡排序比箱子排序法慢了不止一点两点（在大数据的情况下)*/

这里说明一点，基数排序桶排序的一个优化。但是如果输入范围和你的桶的个数一样的时候，基数排序的优势就没有那么大了。
记住:虽然基数排序的时间复杂度虽然有O(n)，桶排序有O(n+range)。但是在实际中，在某种情况下，基数排序不一定比桶排序快。