嵌入式全栈开发学习笔记---数据结构（排序算法）

排序的分类

稳定排序与不稳定排序

内部排序和外部排序

算法的复杂性

常见的排序算法

直接插入排序

希尔排序

快速排序

简单选择排序

堆排序

归并排序

基数排序

常见的排序总结

到目前为止，数据结构的线性结构和树状结构就都讲完了，本节开始学习排序的相关算法！

我们学习C语言的时候学习过冒泡排序，其实在嵌入式中冒泡排序已经可以解决很多问题了，但是一旦数据量非常大，冒泡排序就不太好使了，所以我们需要学习另外几种排序方法。

排序的分类

稳定排序与不稳定排序

假设 Ki = Kj ，且排序前序列中 Ri 领先于 Rj ；

若在排序后的序列中 Ri 仍领先于 Rj ，则称排序方法是稳定的。

若在排序后的序列中 Rj 仍领先于 Ri ，则称排序方法是不稳定的。

内部排序和外部排序

根据排序过程中待排序记录是否全部放置在内存中，排序分为内排和外排。

内部排序: 指的是待排序记录存放在计算机随机存储器（内存）中进行的排序过程。

外部排序: 指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

算法的复杂性

算法的复杂性：体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。

辅助空间：辅助空间是评价排序算法的一个重要指标，辅助空间是指除了存放待排序资源之外，执行算法所需要的其他存储空间。（比如交换两个空间的数据时，需要申请一个中间变量的空间）

时间复杂度：简单的说就是程序循环执行的总的次数。算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。时间复杂度常用大O符号表述，即O(f(n))。（可以理解为这个算法需要多少行代码，所有的代码加起来就是最终的时间复杂度）

以冒泡排序的算法为例：

for(i=0;i<n-1;i++)

{

for(j=0;j<n-i-1;j++)

{

}

这个算法在执行的过程中，i=0执行依1次，i<n-1执行n-1次，i++也是执行n-1次

j=0执行n-1次，j<n-i-1执行(n-1)(n-i-1)次，j++也是执行n-1次，然后其他的就是for循环体里面的一些代码，不过在这里我们不讨论。

最终计算时间复杂度时要去掉常量，因为常量没有意义，比如，1+n-1+n-1+n-1+(n-1)(n-i-1)+n-1，的结果大概是n^2+xn-20+i，当n趋近于无穷大的时候，整个式子就受n^2的影响最大，所以我们可以把低次幂的量全部去掉，就得到这个算法的时间复杂度大概是O(n^2)，O是表示时间复杂度，括号里面就是和n相关的表达式。

在一些笔试题中可能会出现“要求时间复杂度是O(n)”，一旦有这个要求，那么我们的代码中就不能出现好像上面的这种for循环嵌套了，因为一旦嵌套，肯定会出现n*n。

补充：时空复杂度（时间复杂度/空间复杂度）O(1)、O(n)、O(n^2)、O(log n)、O(n log n)是什么意思_空间复杂度为o(1)什么意思-CSDN博客

常见的排序算法

按照排序过程中所依据的原则的不同可以分类为:

插入排序：直接插入排序希尔排序

交换排序：冒泡排序快速排序

选择排序：简单选择排序堆排序

归并排序

基数排序

直接插入排序

就是把一个数字插入到一串有序的序列中。

比如将2插入到1 4 5这个序列中，我们首先将2与5比较，5比2大，就把5往后挪一个位置；2再跟4比较，4比2大，把4往后挪一个位置；2再和1比较，2比1大，就把2放在1的后面，结果就是：1 2 4 5

但是实际上插入排序并不会一开始就给一个有序的序列，但是有一个规律就是如果一个序列只有一个数字，那么它肯定是一个有序的序列。我们可以利用这个规律来完成插入排序。

比如6 5 7 4 8 3 9 2 1 0，

我们把6当成一个单独的有序序列

然后把5和6比较，6比5大，就把6往后挪一个位置，把5放到6左边去，那就得到：5 6这样的有序序列；

然后将7和6比较，7比6大，就直接放到6的右边，结果就是5 6 7

然后将4和7比较，7比4大，把7往后挪一个位置，

4再和6比，6比4大，也把6往后挪一个位置，

4再和5比，5也比4大，5也往后挪一个位置，

最后就把4放在5的左边，结果就是：4 5 6 7

以此类推，结果就得到一个有序的序列。

接下来通过代码实现：

新建一个sort目录

1.insertsort.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define SIZE 100000//数字个数//直接插入排序
void insert_sort(int *a,int size)
{int i,j,num;for(i=1;i<size;i++)//因为一开始是拿下标为1的那个数和下标为0的数比较，所以i=1{num=a[i];//先把想要插入的数记录下来for(j=i-1;j>=0;j--)//因为每次都是跟最大最右边的那个数开始比起，所以j=i-1{if(num<a[j]){a[j+1]=a[j];//将a[j]的位置往后挪一个}else{break;//如果要插入的数已经比序列中最大的数大了就没必要比较了，直接跳出循环}}//一个数字比完了,就把这个数插入到空出来的位置a[j+1]=num;//因为for循环还要进行一次j--才跳到这里的，所以要给它把1加回来，所以是j+1,并且如果一开始比较就是比序列中最大的数大的话，也是将这个数放在j+1的位置}
}int main()
{int arr[SIZE]={0},i;//随机产生数组srand(time(NULL));for(i=0;i<SIZE;i++){arr[i]=rand()%100;}//直接插入排序insert_sort(arr,SIZE);//打印排序结果for(i=0;i<SIZE;i++){printf("%d ",arr[i]);}printf("\n");return 0;
}

运行结果

直接插入排序的特点

稳定性：稳定

时间复杂度： O(n^2)，和冒泡排序的时间复杂度差不多

(1)初始数据正序，总比较次数：n-1

(2)初始数据逆序，总比较次数：(n2 + n - 1) / 2 = O(n2)

(3)初始数据无序，第i趟平均比较次数(i+1)/2，总次数为 (n2 + 3n) / 4 = O(n2)

(4)可见，原始数据越趋向正序，比较次数和移动次数越少。

希尔排序

希尔排序也是属于直接插入排序的一种，但是它比直接插入排序的效率高很多。

具体步骤如下：

(1)选择一个步长序列t1, t2, ..., tk,满足ti > tj(i <ｊ)，tk = 1。

(2)按步长序列个数k，对待排序序列进行k趟排序。

(3)每趟排序，根据对应的步长ti，将待排序的序列分割成ti个子序列，分别对各个子序列进行直接插入排序。

例，序列 4 8 6 7 5 3 9 2 1 0排序

第一趟排序先取步长10/2=5（间隔为4个数）进行两两分组，共分成了5组

比如现在对5 和0进行排序，先把0取出来，0和5比较，0比5小，所以把5放到0原来的位置，把0放到5原来的位置

其他组数据的操作一样，最后我们得到一个不那么乱的序列

然后我们再缩写步长5/2=2（间隔1个数）进行分组，然后两两比较

现在是3 2 0 9 7为一组，8 1 4 6 5为一组，这两组分别进行直接插入排序，而且是两组同时进行的。

以此类推，最终这个序列会随着步长的减小而变的越来越有序。

代码直接在插入排序的基础上改

复制直接插入排序的文件改名为2.shellsort.c

2.shellsort.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define SIZE 100000//数字的个数//希尔排序
void shell_sort(int *a,int size)
{int i,j,num,h;for(h=size/2;h>0;h/=2)//设置步长{for(i=h;i<size;i++)//因为一开始是拿下标为h的那个数和下标为0的数比较的，所以i=h{	num=a[i];//先把想要插入的数记录下来for(j=i-h;j>=0;j-=h)//因为每次都是跟最大最右边的那个数开始比起，所以j=i-5，比如步长为2的时候，刚开始和组内倒数第二个数比，所以每次跨越一个步长h，所以是j-h{if(num<a[j]){a[j+h]=a[j];//将a[j]的位置往后挪一个步长}else{break;//如果要插入的数已经比序列中最大的数大了就没必要比较了，直接跳出循环}}//一个数字比完了,就把这个数插入到空出来的位置a[j+h]=num;//因为for循环还要进行一次j-h才跳到这里的，所以要给它把h加回来，所以是j+h,并且如果一开始比较就是比序列中最大的数大的话，也是将这个数放在j+h的位置}	}
}int main()
{int arr[SIZE]={0},i;//随机产生数组srand(time(NULL));for(i=0;i<SIZE;i++){arr[i]=rand()%100;}//希尔排序shell_sort(arr,SIZE);//打印排序结果for(i=0;i<SIZE;i++){printf("%d ",arr[i]);}printf("\n");return 0;
}

运行结果

如果要比较直接插入排序和希尔排序的效率的话，可以将他们的size改成100000测试一下

补充命令：time 文件路径，这行命令可以让我们看到代码执行的用时。

比如

直接插入排序用时

希尔插入排序用时

很明显，不考虑程序中的其他操作的话，希尔排序用时更少，效率更高

希尔排序的特点：

时间复杂度：希尔排序的时间复杂性在O（nlog2n）和O（n2 ）之间，大致为O（n1.3）。

稳定性：不稳定

快速排序

快速排序也比直接插入排序的效率高，而且它用的是递归。

比如这样一个虚序列：3 8 2 1 0 4 9 6 7 5

我们首先要选择一个基准，比如取第一个3作为基准，并且我们需要两个指针，一个指针x指向地第一个位置，另一个指针y指向最后的位置。

从最后一个位置开始比较，5比3大，不用动；

然后3和7比，指针y指向7，7比3大，也不用动；

指针y继续指向6，6比3大，不用动；

y继续指向9，9比3大，不用动；

y指向4，4比3大，不用动；

y继续指向0，

0比3小，所以将0挪到x指向的位置

然后x向右移一个位置，指向8

现在8和3比较，8比3大，所以将8挪到y指向的位置

同时y向左移动一个位置，指向1

现在1和3比较，1比3小，所以要挪到左边去，同时x要向右移一个位置，指向2

现在2比3小，就应该是放在左边的，所以不用动了，然后x再继续右移一个位置，和y重合了

x和y重合的时候就说明这一趟排序已经结束，我们把3放到x和y指向的位置

此时3已经在合适的位置了，然后我们分别对3的左边和右边做刚刚一样的操作，也就是递归，继续调用这个函数。

接下来用代码实现一下

我们也是在直接插入排序的基础上改

3.quicksort.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define SIZE 100000//快速排序
void quick_sort(int *a,int start,int end)
{//递归需要退出的条件if(end<=start)return;//记录下开始和结束的位置int x=start;int y=end;int num=a[start];//记录下基数,要不然等会儿回来覆盖掉while(x<y)//循环的条件是x小于y，如果x=y，循环就结束了{//只要y指向的位置的值比num大，y就减1while(a[y]>num && x<y){y--;}//一旦跳出上面的while循环，说明a[y]<numif(x<y){a[x++]=a[y];//就把a[y]放到a[x]的位置，同时x要往右移动一个位置}//只要x指向的位置的值比num小，x就加1while(a[x]<num && x<y){x++;}//一旦跳出这个while，说明a[x]>numif(x<y){a[y--]=a[x];//就把a[x]放到a[y]的位置，同时y要往左移动一个位置}}//跳出循环的时候，说明x=y了，就把num放到x或者y指向的位置a[x]=num;//然后对num左右两边的序列都作以上同样的操作quick_sort(a,start,x-1);quick_sort(a,x+1,end);
}int main()
{int arr[SIZE]={0},i;//随机产生数组srand(time(NULL));for(i=0;i<SIZE;i++){arr[i]=rand()%100;}//快速排序quick_sort(arr,0,SIZE-1);//开始是0，结束下标是SIZE－1//打印排序结果for(i=0;i<SIZE;i++){printf("%d ",arr[i]);}printf("\n");return 0;
}

运行结果：

把size也改成100000，测试一下它的用时

和那个希尔排序差不多，甚至比希尔排序的效率更高一点

快速排序特点：

稳定性：不稳定

平均时间复杂度： O(nlog2n)

简单选择排序

这种算法比较简单，但是效率比较低

比如这样一个序列：3 8 2 1 0 4 9 6 7 5

现在我们要从小到大排序，一开始我们需要记录最小值min=3，下标是index=0，

然后从8开始遍历，8比3大就不用管，

然后2比3小，我们就更新一下最小值min=2和下标index=2，

然后继续往后，1比2小，再次更新min=1,index=3，

再往后，0比1小，再次更新min=0,index=4

之后的4 9 6 7 5走比0大都不用管，这一趟结束后结果就是min=0，index=4，所以将3挪走，把0放到原来3的位置，3再放到原来0的位置。

之后以此类推得到一个有序的序列，这就是简单选择排序。

接下来用代码实现

还是在直接插入排序的代码基础上修改

4.selectsort.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define SIZE 100000//数字个数//简单选择排序
void select_sort(int *a,int size)
{int i,min,index,j;//一共要循环9次for(i=0;i<size-1;i++){min=a[i];//先把第一个数记录下来index=i;for(j=i+1;j<size;j++)//从i+1的位置上的值开始和min比较,一直到最后一个位置，一共要比较9次{if(a[j]<min)//如果遇到比目前min小的数{//更新min和index的值min=a[j];index=j;}//如果是比目前min大，那就不用管}//等一趟比较完之后，就把这一趟最小的数放在一开始这一趟index记录的地方if(min!=a[i]){a[index]=a[i];a[i]=min;}}
}int main()
{int arr[SIZE]={0},i;//随机产生数组srand(time(NULL));for(i=0;i<SIZE;i++){arr[i]=rand()%100;}//简单选择排序select_sort(arr,SIZE);//打印排序结果for(i=0;i<SIZE;i++){printf("%d ",arr[i]);}printf("\n");return 0;
}

运行结果：

把size改成100000看看效率

和直接插入排序的效率差不多

简单选择排序的特点

最大特点：移动次数少；

时间复杂度：总共比较 n(n-1)/2 次，移动次数最多n-1, 时间复杂度为O(n2)

稳定性：不稳定。

我们主要是掌握这种思想，但是不建议用这种排序，如果想要这种还不如用冒泡排序。

堆排序

这是最难的一种排序

堆其实是一种特殊的二叉树。堆有两种，一种是大顶堆，一种是小顶堆。

大顶堆要求所有的子树的父节点的值要比孩子节点的值要大。

比如

注意，大顶堆不是有序的，但是很明显的一个特点是根节点的值一定是最大的。

小顶堆和大顶堆相反，孩子节点的值要比它的双亲结点的值要大，所以根节点上的值一定是最小的

现在比如有这样一个序列：6 5 7 4 8 3 9 3 2 0

第一步是先把这些数放到这个二叉树里面

目前这个不是大顶堆也不是小顶堆

接下来我们要做的是构建大顶堆，就是调整上面的二叉树，使它变成大顶堆。

我们先从最后一个有孩子节点的双亲节点开始，这里是从下标为10/2-1=4的8开始调整，0比8小不用调整；

再看4比3大也不用调整，4比2大爷不用调整；

接下来7比9小，需要调整，要7记录下来，把9挪到7的位置，然后再把7放到9原来的位置上，然后3比9小不用进一步调整；

现在轮到5比4到不用管，8比5大，需要把5记录下来，把8放到5的位置，然后再把5放到8原来的位置；

8和5调换位置后，要记录再将5和它自己的孩子节点比较，0比5小就不用动了（如果孩子节点比5大还是要进行调换位置操作的）。

然后是9和6比，9大，就将9和6调换位置

同样，9和6调换过位置，那么不要忘了需要将6和它自己的孩子节点再比较一下，此时7比6大，所以需要将6和7调换位置，调换位置后3比7小就不用动了。

这样就完成了大顶堆的调整。9是这个数组中最大的元素

然后接下来把9和最下面的0调换位置

然后将9从这个数组里面剔除（相当于9这个节点跟这个二叉树断开了）

接下来我们调整的时候就跟这个9没有关系了。并且接下来我们的操作就不叫构建大顶堆了，叫调整大顶堆。

刚刚0和9调换过位置，所以我们需要将0和和它的孩子节点进行比较，8比0大，需要调换位置

然后0也需要和它自己的孩子节点进行比较，4和5比较，5大，5比0大，所以就将5和0调换位置。

调整完成后我们发现8是最大的。

此时要将8和2调换位置，之后的调整过程也跟8没有关系了。

以此类推，这个过程就是堆排序，总共就是两个步骤，一个构建大顶堆，一个调整大顶堆。

数据量越大利用堆排序的效率越高。

下面开始用代码实现。

虽然我们刚刚的过程都是在树里面完成的，但是其实在代码中并不涉及树，本质上我们一直操作的是数组的下标。

5.heapsort.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define SIZE 100000//数字个数void adjust_heap_sort(int *a,int root,int last)
{int child;while(1){child=2*root+1;//计算出left的下标if(child>last){break;//跳出循环}if(child+1<=last && a[child]<a[child+1])//child+1<=last保证右孩子存在{child++;//接下来的操作和原来的child无关}if(a[child]>a[root]){//交换位置int num=a[root];a[root]=a[child];a[child]=num;}//由于child的位置被调换过，所以要再次将这个位置的值和其孩子调整root=child;//把child当成根节点}}//堆排序
void heap_sort(int *a,int size)
{//构建大顶堆int i;for(i=size/2-1;i>=0;i--)//从最后一个有孩子节点的双亲节点开始，下标从size/2-1{adjust_heap_sort(a,i,size-1);//i是根的下标,size-1是每一趟最后一个节点的下标}//调整大顶堆//从下标为0的节点开始调整for(i=size-1;i>0;i--)//上面构建的环节已经找出来了最大的那个，下面剔除了一个，size-1{//每次都将最大的数从开始的位置挪到最后一个位置iint num=a[0];a[0]=a[i];a[i]=num;//交换完成后需要调整adjust_heap_sort(a,0,i-1);//i－1是下一轮调整的最后一个位置}}int main()
{int arr[SIZE]={0},i;//随机产生数组srand(time(NULL));for(i=0;i<SIZE;i++){arr[i]=rand()%100;}//堆排序heap_sort(arr,SIZE);//打印排序结果for(i=0;i<SIZE;i++){printf("%d ",arr[i]);}printf("\n");return 0;
}

运行结果

将size改成100000看看效率

27ms，可以说是目前为止我们学过的效率最高的排序算法了

堆排序的特点：

稳定性：不稳定

时间复杂度：O(nlogn)

堆排序对记录较少的文件效果一般，但对于记录较多的文件很有效果，其运行时间主要耗费在创建堆与调整堆上

归并排序

归并排序就是应用到递归和合并两个有序的序列的思想

比如这样两个有序的序列，要求把它们合并成一个有序的序列：

1 3 5 7

0 2 4 6 8

我们需要两个指针（下标），分别指向两个序列的开头位置

我们需要将这两个序列合并成一个序列，那就需要另外申请一个数组

开始是1和0比较，0小，就把0放到k指向的位置，然后y往后移动一个，k也往后移动一个

然后1和2比较，1小，就把1放到k目前指向的位置，然后x++，k++

依次类推，我们发现k每次都要移动，而x和y取决于谁的值小谁移动。

最后当7和8比较，7小，x++，k++之后，第一个序列后面没有数和第二个序列的8及后面的数比较了，我们就直接将8及后面的数接在k指向的位置及后面。

以上只是一个合并的过程，当我们遇到的两个序列不是有序的时候，就还需要用到递归

比如这样一个序列：6 7 5 8 4 3 9 0 2 1

我们之前说过如果一个序列中只有一个数，那么它一定是一个有序序列，我们利用这个思想，先将这组数组分成两份，5个为一份

此时两组数据都不是有序的，继续分组，5/2取整等于2，所以这样分

但是还是存在无序的序列

再进一步分组

此时6和7这两个序列是有序的，那就对6和7执行我们刚才的合并操作，结果合并成6 7

然后5 8和4两个序列是有序的，执行合并操作，结果是：4 5 8

接下来将6 7和4 5 8两个序列再做一个合并，结果是：4 5 6 7 8

然后右边的这5个执行和左边5个一样的操作，得出的结果0 1 2 3 9

最后将4 5 6 7 8和0 1 2 3 9再做一次合并就得到了结果：0 1 2 3 4 5 6 7 8 9

接下来用代码实现

还是在直接插入排序的代码基础上修改

6.mergesort.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define SIZE 100000//数字个数void merge(int *a, int start,int mid, int end)
{//计算左右两边的序列长度int left_len=mid-start+1;int right_len=end-mid;//为左右两边的序列申请空间int*L=(int*)malloc(sizeof(int)*left_len);int*R=(int*)malloc(sizeof(int)*right_len);//将左右两边的序列搬到刚刚申请的空间int i,k=start,j;for(i=0;i<left_len;i++,k++){L[i]=a[k];}for(i=0;i<right_len;i++,k++)//k正好加到第二个序列的0下标位置，接着用就行了{R[i]=a[k];}//i和k回到下标为0的位置,开始合并操作for(i=0,j=0,k=start;i<left_len && j<right_len;k++)//只要其中一边的序列比较完了，就退出循环{//小的那个放到合并的那快内存中if(L[i]>R[j]){a[k]=R[j++];}else{a[k]=L[i++];}}//其中一个序列比较完了，判断一下哪个序列还剩数字没有比较的if(i<left_len)//i指向的序列还剩数字{for(;i<left_len;i++,k++){a[k]=L[i];//将剩下的接到合并的序列中}}if(j<left_len)//j指向的序列还剩数字{for(;j<right_len;j++,k++){a[k]=R[j];}}//将i和j指向的序列的空间释放free(L);free(R);
}//归并排序
void merge_sort(int *a,int start,int end)
{//递归的退出条件if(start>=end)//如果分组后一个序列中只有一个数，就停止分组return;//找到中间元素的下标，因为一开始就要从中间元素的位置进行分割的int mid=(end+start)/2;//继续分组merge_sort(a,start,mid);//对左边分组merge_sort(a,mid+1,end);//对右边分组//合并merge(a,start,mid,end);
}int main()
{int arr[SIZE]={0},i;//随机产生数组srand(time(NULL));for(i=0;i<SIZE;i++){arr[i]=rand()%100;}//归并排序merge_sort(arr,0,SIZE-1);//开头下标0和结尾下标SIZE－1//打印排序结果for(i=0;i<SIZE;i++){printf("%d ",arr[i]);}printf("\n");return 0;
}

运行结果

把size改成100000看看效率

比堆排序和快速排序慢了一点。

归并排序特点：

平均时间复杂度：O(nlog2n)

稳定性：稳定

基数排序

这种排序适用于数字本身所表示的值特别大的情况下，比如数字的值是1000，2000或者几万，就可以使用这种排序。

比如这样一种序列：1024 345 2045 32 8

我们需要10个“桶”，编号是0~9（因为自然数是0~9）

然后按个位进行排序

然后按照上面的排序顺序收集

这一趟就结束了

接下来按照十位进行排序

然后按照这个顺序进行第二次收集

然后再按百位来排序

然后再按照这个顺序进行收集

然后再按照千位进行排序

然后再这个顺序进行收集

这样就得到一个有序序列了，这个过程就叫基数排序

一共要循环排多少趟取决于这个序列最大的那个数是多少位。

并且排序的结果中，某个数排在了下标为几的位置是因为它前面有几个数导致的，比如2045被排在下标为4的位置，是因为前面累计有4个数。

下面用代码来实现

还是复制直接插入排序的代码，进行修改

7.radixsort.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define SIZE 100000//数字个数//基数排序
void radix_sort(int *a,int size)
{int i,max=a[0];//先找出最大的那个数，因为它决定循环的趟数for(i=1;i<size;i++){if(a[i]>max)//如果找到一个数比max还大就更新maxmax=a[i];}int radix=1;while(max>0){int bucket[10]={0};//申请10个”桶"的空间//按照哪一位进行排序for(i=0;i<size;i++){//统计桶里的数的个数bucket[a[i]/radix%10]++;//直接把取出来的数位上的数当成桶的下标}//为排序结果申请空间int *tmp=(int*)malloc(sizeof(int)*size);for(i=1;i<=9;i++){bucket[i]=bucket[i]+bucket[i-1];//把每个桶里的数累加起来}//分配，将a数组的数倒过来考虑放在哪个桶for(i=size-1;i>=0;i--)//有多少个数就循环多少次{tmp[bucket[a[i]/radix%10]-1]=a[i];//桶里面统计的数的个数-1当成要放在排序结果数组tmp中的下标bucket[a[i]/radix%10]--;//让桶里面的数字减1，留着给下一个数使用}//将tmp数组中的结果搬移到数组a中for(i=0;i<size;i++){a[i]=tmp[i];}//释放tmp的空间free(tmp);radix=radix*10;//为下一趟排序作准备max=max/10;//计算最大的那个数的位数}
}int main()
{int arr[SIZE]={0},i;//随机产生数组srand(time(NULL));for(i=0;i<SIZE;i++){arr[i]=rand()%100000;//适合数值大的序列}//基数排序radix_sort(arr,SIZE);//打印排序结果for(i=0;i<SIZE;i++){printf("%d ",arr[i]);}printf("\n");return 0;
}

运行结果