目录
一、基本思想
二、算法思路
1、个位排序
(1)分配
(2)收集
2、十分位排序
(1)分配
(2)收集
三、源码分享
1、InitMyBucket
2、DestroyMyBucket
3、ClearMyBucket
4、PushData2Bucket
5、PopDataFromBucket
6、GetIntegerDigit
7、BucketSortSentryQueue
四、算法效率
五、Linux环境编译测试
排序的其他相关知识点和源码分享可以参考之前的博客:
《数据结构与算法基础-学习-30-插入排序之直接插入排序、二分插入排序、希尔排序》,
《数据结构与算法基础-学习-31-交换排序之冒泡排序、快速排序》,
《数据结构与算法基础-学习-32-选择排序之简单选择排序、堆排序》,
《数据结构与算法基础-学习-33-归并排序》
一、基本思想
基数排序的基本思想就是分配和收集。
基数排序也叫桶排序、箱排序,设置若干个桶,将关键字为k的记录放入第k个桶,然后再按照序号将非空的连接。
二、算法思路
我们还是以升序为例,初始化10个桶来存放数据,因为上面的数据最多到十分位,我们只需要两部就可以完成排序。
1、个位排序
(1)分配
10的个位是0,放到0号桶。
34的个位是4,放到4号桶。
1的个位是1,放到1号桶。
后面的数据以此类推。
(2)收集
我们按照顺序从第0个桶、第1个桶。。。。的顺序取数据,可以发现个位已经有序。并且只有个位的元素就不需要进行下一轮十分位的排序,我们只用比较有十分位的元素,这样可以减少排序时间。收集前桶中数据是全部,为了效率我们可以直接把只有个位的放入原序列中。
2、十分位排序
(1)分配
我们清空桶,将临时队列中的元素按照十分位的数值放入桶中。
(2)收集
我们按照顺序从第0个桶、第1个桶。。。。的顺序取数据,由于这些元素只有最大十分位,我们可以直接放入原队列中,这样就排好序啦。
三、源码分享
1、InitMyBucket
Status InitMyBucket(MyBucket** Bucket, QueueLenType BucketGroupNums, QueueLenType OneBucketNums, JudgeTypeFlag Flag)
{JudgeAllNullPointer(Bucket);if (BucketGroupNums * OneBucketNums > __LONG_LONG_MAX__){LogFormat(Error,"Init Bucket Fail, Reason : BucketGroupNums(%lld) * OneBucketNums(%lld) > %lld.\n",BucketGroupNums,OneBucketNums,__LONG_LONG_MAX__);return FailFlag;}QueueLenType i;(*Bucket) = (MyBucket*)MyMalloc(sizeof(MyBucket));(*Bucket)->BucketArrayMaxLen = BucketGroupNums;(*Bucket)->BucketDataUseNums = 0;(*Bucket)->BucketDataMaxUseNums = BucketGroupNums * OneBucketNums;(*Bucket)->BucketArray = (SqQueue**)MyMalloc(BucketGroupNums * sizeof(SqQueue*));for ( i = 0; i < (*Bucket)->BucketArrayMaxLen; i++){InitSqQueue(&((*Bucket)->BucketArray[i]),OneBucketNums,Flag);}LogFormat(Debug,"Init Bucket OK.\n");return SuccessFlag;
}
2、DestroyMyBucket
Status DestroyMyBucket(MyBucket** Bucket)
{JudgeAllNullPointer(*Bucket);QueueLenType i;for ( i = 0; i < (*Bucket)->BucketArrayMaxLen; i++){DestroySqQueue(&((*Bucket)->BucketArray[i]));}free((*Bucket)->BucketArray);(*Bucket)->BucketArray = NULL;(*Bucket)->BucketArrayMaxLen = 0;(*Bucket)->BucketDataUseNums = 0;(*Bucket)->BucketDataMaxUseNums = 0;free(*Bucket);*Bucket = NULL;LogFormat(Debug,"Destroy Bucket OK.\n");return SuccessFlag;
}
3、ClearMyBucket
Status ClearMyBucket(MyBucket* Bucket)
{JudgeAllNullPointer(Bucket);QueueLenType i;for ( i = 0; i < Bucket->BucketArrayMaxLen; i++){ClearSqQueue(Bucket->BucketArray[i]);}Bucket->BucketDataUseNums = 0;LogFormat(Debug,"Clear Bucket OK.\n");return SuccessFlag;
}
4、PushData2Bucket
//将数据压入桶中。
Status PushData2Bucket(MyBucket* Bucket, QueueLenType BucketGroupIndex, void* Data)
{JudgeAllNullPointer(Bucket);JudgeAllNullPointer(Data);if (BucketGroupIndex < 0 || BucketGroupIndex >= Bucket->BucketArrayMaxLen){LogFormat(Error,"Push Data To Bucket Fail, Reason : Illegal BucketGroupIndex(%lld).\n",BucketGroupIndex);return FailFlag;}if (Bucket->BucketDataUseNums == Bucket->BucketDataMaxUseNums){LogFormat(Warning,"Push Data To Bucket Fail, Reason : Bucket Is Full(%lld).\n",Bucket->BucketDataMaxUseNums);return NormalFlag;}Status ReturnStatus;ReturnStatus = EnterSqQueue(Bucket->BucketArray[BucketGroupIndex],Data);if (ReturnStatus == SuccessFlag){Bucket->BucketDataUseNums++;LogFormat(Debug,"Push Data To Bucket OK.\n");}return ReturnStatus;
}
5、PopDataFromBucket
//将数据从桶中取出来。
Status PopDataFromBucket(MyBucket* Bucket, QueueLenType BucketGroupIndex, void* Data)
{JudgeAllNullPointer(Bucket);JudgeAllNullPointer(Data);if (BucketGroupIndex < 0 || BucketGroupIndex >= Bucket->BucketArrayMaxLen){LogFormat(Error,"Pop Data From Bucket Fail, Reason : Illegal BucketGroupIndex(%lld).\n",BucketGroupIndex);return FailFlag;}if (Bucket->BucketDataUseNums == 0){LogFormat(Warning,"Pop Data From Bucket Fail, Reason : Bucket Is Empty.\n");return NormalFlag;}Status ReturnStatus;ReturnStatus = LeaveSqQueue(Bucket->BucketArray[BucketGroupIndex],Data);if (ReturnStatus == SuccessFlag){Bucket->BucketDataUseNums--;LogFormat(Debug,"Pop Data From Bucket OK.\n");}return ReturnStatus;
}
6、GetIntegerDigit
//给出一个正整数,和你想要的位数,返回相应的位数。
//例如1234,你要十分位,返回一个3。
//1表示个位,2表示十分位,以此类推。
//目前只支持int类型
int GetIntegerDigit(int Num, int Digit)
{// LogFormat(Debug,"Num : %d, Digit : %d\n",Num,Digit);if (Digit < 1 || Digit > 9){return GET_INTEGER_DIGIT_FAIL_FLAG;}if (Num < 0){return GET_INTEGER_DIGIT_FAIL_FLAG;}if (Digit == 1){return Num % 10;}else if (MyIntSquare(10,Digit - 1) > Num)//如果Num不存在Digit相应的位数,如89不存在百分位的情况。{return GET_INTEGER_DIGIT_NO_EXISTS_FLAG;}else{return (Num % MyIntSquare(10,Digit) - Num % MyIntSquare(10,Digit - 1)) / MyIntSquare(10,Digit - 1);}
}
7、BucketSortSentryQueue
//由于GetIntegerDigit实现的原因,导致BucketSortSentryQueue只支持正整数排序。
//此函数如果执行出错,会改变Queue的值,里面存了中间结果。
Status BucketSortSentryQueue(SqQueue* Queue)
{JudgeAllNullPointer(Queue);MyBucket* Bucket = NULL;SqQueue* TmpQueue = NULL;//临时队列,存放中间数据。switch(Queue->Flag){case INT_TYPE_FLAG :InitMyBucket(&Bucket,INTEGER_BUCKET_NUMS,Queue->SqQueueLen,Queue->Flag);InitSqQueue(&TmpQueue,Queue->SqQueueLen,Queue->Flag);break;default :LogFormat(Error,"BucketSortSentry Function , Queue->Flag(%d) Is Unknow Type Flag, Exit!!!\n",Queue->Flag);exit(ExceptionExitFlag);}//后续再做成万能数据型//现在只支持整型int ReutrnVal = 0;QueueLenType i;QueueLenType BucketGroupIndex = 0;Status ReturnStatus;int Digit = 1;//计算的位数QueueLenType MaxQueueLen = Queue->SqQueueLen;do{if (Digit != 1){//第n次收集是从TmpQueue读取数据,做整数Digit位的排序,放入桶中。for ( i = 0; i < TmpQueue->SqQueueLen; i++){ReadSqQueue(TmpQueue,i,&ReutrnVal);BucketGroupIndex = GetIntegerDigit(ReutrnVal,Digit);PushData2Bucket(Bucket, BucketGroupIndex, &ReutrnVal);}//清理临时队列。ClearSqQueue(TmpQueue);}else{//第一次收集是从传入参数Queue读取数据,做整数个位的排序,放入桶中。for ( i = 1; i < Queue->SqQueueLen; i++){ReadSqQueue(Queue,i,&ReutrnVal);BucketGroupIndex = GetIntegerDigit(ReutrnVal,Digit);PushData2Bucket(Bucket, BucketGroupIndex, &ReutrnVal);}ReadSqQueue(Queue,0,&ReutrnVal);ClearSqQueue(Queue);EnterSqQueue(Queue,&ReutrnVal);}//第n次分配,从桶中把顺序数据读取出来。i = 0;Digit++;while (Bucket->BucketDataUseNums != 0){ReturnStatus = PopDataFromBucket(Bucket, i, &ReutrnVal);if (ReturnStatus == SuccessFlag)//成功读出数据,放入临时队列中。{if (GetIntegerDigit(ReutrnVal,Digit) == GET_INTEGER_DIGIT_NO_EXISTS_FLAG)//如果给的数没有Digit,放到最终队列中。{EnterSqQueue(Queue,&ReutrnVal);}else if (GetIntegerDigit(ReutrnVal,Digit) != GET_INTEGER_DIGIT_FAIL_FLAG)//有Digit的进行下一步计算。{EnterSqQueue(TmpQueue,&ReutrnVal);}else//异常情况{LogFormat(Error,"Bucket Sort Sentry Queue Fail, Reason : Error Data(%d).\n",ReutrnVal);exit(ExceptionExitFlag);}}else if (ReturnStatus == NormalFlag)//由于第i个桶的数据被读取完了,读下一个桶。{i++;}else//读取数据失败{DestroyMyBucket(&Bucket);DestroySqQueue(&TmpQueue);Bucket = NULL;TmpQueue = NULL;LogFormat(Error,"Bucket Sort Sentry Queue Fail, Reason : Pop Data From Bucket Fail.\n");return FailFlag;}}//清理桶ClearMyBucket(Bucket);}while (GetSqQueueLen(Queue) < MaxQueueLen);//如果最终结果队列的元素个数小于Queue队列的元素个数,说明数据没有排序完。DestroyMyBucket(&Bucket);DestroySqQueue(&TmpQueue);Bucket = NULL;TmpQueue = NULL;LogFormat(Debug,"Bucket Sort Sentry Queue OK.\n");return SuccessFlag;
}
四、算法效率
情况 | 时间复杂度 | 是否稳定 |
最好 | O(n + m) | 稳定 |
最坏 | O(k * (n + m)) | |
平均 | O(k * (n + m)) |
例如我们上面这个计算时间复杂度是多少呢?
(10个数字 + 10个桶)* 2位数 = 40
五、Linux环境编译测试
[gbase@czg2 Sort]$ make
gcc -Wall -Wextra -O3 InsertSort.c SwapSort.c SelectSort.c MergeSort.c BucketSort.c main.c -o TestSort -I /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/Log/ -I /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/ -I /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/HashTable/include/ -I /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/SqQueue/ -I /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/SqStack/ -L /opt/Developer/ComputerLanguageStudy/C/DataStructureTestSrc/PublicFunction/Make/Libs/ -lPublicFunction -lLog -lSqQueue
[gbase@czg2 Sort]$ time ./TestSort
2023-9-12--[ Debug ]--Init SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Info ]--SqQueue Data :
Data : [ 0 ,5 ,6 ,7 ,8 ,9 ,0 ,1 ,2 ,3 ,4 ]
FrontIndex : 0
RearIndex : 0
SqQueueLen : 11
SqQueueMaxLen : 11
Flag : INT_TYPE_FLAG
2023-9-12--[ Debug ]--Init SqQueue OK
2023-9-12--[ Debug ]--Init SqQueue OK
2023-9-12--[ Debug ]--Init SqQueue OK
2023-9-12--[ Debug ]--Init SqQueue OK
2023-9-12--[ Debug ]--Init SqQueue OK
2023-9-12--[ Debug ]--Init SqQueue OK
2023-9-12--[ Debug ]--Init SqQueue OK
2023-9-12--[ Debug ]--Init SqQueue OK
2023-9-12--[ Debug ]--Init SqQueue OK
2023-9-12--[ Debug ]--Init SqQueue OK
2023-9-12--[ Debug ]--Init Bucket OK.
2023-9-12--[ Debug ]--Init SqQueue OK
2023-9-12--[ Debug ]--Read SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Push Data To Bucket OK.
2023-9-12--[ Debug ]--Read SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Push Data To Bucket OK.
2023-9-12--[ Debug ]--Read SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Push Data To Bucket OK.
2023-9-12--[ Debug ]--Read SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Push Data To Bucket OK.
2023-9-12--[ Debug ]--Read SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Push Data To Bucket OK.
2023-9-12--[ Debug ]--Read SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Push Data To Bucket OK.
2023-9-12--[ Debug ]--Read SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Push Data To Bucket OK.
2023-9-12--[ Debug ]--Read SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Push Data To Bucket OK.
2023-9-12--[ Debug ]--Read SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Push Data To Bucket OK.
2023-9-12--[ Debug ]--Read SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Push Data To Bucket OK.
2023-9-12--[ Debug ]--Read SqQueue OK
2023-9-12--[ Debug ]--Clear SqQueue OK
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Leave SqQueue OK
2023-9-12--[ Debug ]--Pop Data From Bucket OK.
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--SqQueue is Empty, Data cannot be left
2023-9-12--[ Debug ]--Leave SqQueue OK
2023-9-12--[ Debug ]--Pop Data From Bucket OK.
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--SqQueue is Empty, Data cannot be left
2023-9-12--[ Debug ]--Leave SqQueue OK
2023-9-12--[ Debug ]--Pop Data From Bucket OK.
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--SqQueue is Empty, Data cannot be left
2023-9-12--[ Debug ]--Leave SqQueue OK
2023-9-12--[ Debug ]--Pop Data From Bucket OK.
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--SqQueue is Empty, Data cannot be left
2023-9-12--[ Debug ]--Leave SqQueue OK
2023-9-12--[ Debug ]--Pop Data From Bucket OK.
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--SqQueue is Empty, Data cannot be left
2023-9-12--[ Debug ]--Leave SqQueue OK
2023-9-12--[ Debug ]--Pop Data From Bucket OK.
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--SqQueue is Empty, Data cannot be left
2023-9-12--[ Debug ]--Leave SqQueue OK
2023-9-12--[ Debug ]--Pop Data From Bucket OK.
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--SqQueue is Empty, Data cannot be left
2023-9-12--[ Debug ]--Leave SqQueue OK
2023-9-12--[ Debug ]--Pop Data From Bucket OK.
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--SqQueue is Empty, Data cannot be left
2023-9-12--[ Debug ]--Leave SqQueue OK
2023-9-12--[ Debug ]--Pop Data From Bucket OK.
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--SqQueue is Empty, Data cannot be left
2023-9-12--[ Debug ]--Leave SqQueue OK
2023-9-12--[ Debug ]--Pop Data From Bucket OK.
2023-9-12--[ Debug ]--Enter SqQueue OK
2023-9-12--[ Debug ]--Clear SqQueue OK
2023-9-12--[ Debug ]--Clear SqQueue OK
2023-9-12--[ Debug ]--Clear SqQueue OK
2023-9-12--[ Debug ]--Clear SqQueue OK
2023-9-12--[ Debug ]--Clear SqQueue OK
2023-9-12--[ Debug ]--Clear SqQueue OK
2023-9-12--[ Debug ]--Clear SqQueue OK
2023-9-12--[ Debug ]--Clear SqQueue OK
2023-9-12--[ Debug ]--Clear SqQueue OK
2023-9-12--[ Debug ]--Clear SqQueue OK
2023-9-12--[ Debug ]--Clear Bucket OK.
2023-9-12--[ Debug ]--Destroy SqQueue OK
2023-9-12--[ Debug ]--Destroy SqQueue OK
2023-9-12--[ Debug ]--Destroy SqQueue OK
2023-9-12--[ Debug ]--Destroy SqQueue OK
2023-9-12--[ Debug ]--Destroy SqQueue OK
2023-9-12--[ Debug ]--Destroy SqQueue OK
2023-9-12--[ Debug ]--Destroy SqQueue OK
2023-9-12--[ Debug ]--Destroy SqQueue OK
2023-9-12--[ Debug ]--Destroy SqQueue OK
2023-9-12--[ Debug ]--Destroy SqQueue OK
2023-9-12--[ Debug ]--Destroy Bucket OK.
2023-9-12--[ Debug ]--Destroy SqQueue OK
2023-9-12--[ Debug ]--Bucket Sort Sentry Queue OK.
2023-9-12--[ Info ]--Sort Function Elapsed Time : 0 s
2023-9-12--[ Info ]--SqQueue Data :
Data : [ 0 ,0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ]
FrontIndex : 0
RearIndex : 0
SqQueueLen : 11
SqQueueMaxLen : 11
Flag : INT_TYPE_FLAG
2023-9-12--[ Debug ]--Destroy SqQueue OKreal 0m0.002s
user 0m0.002s
sys 0m0.000s