排序算法全析：原理、实现与复杂度战场

🌟 嗨，我是Lethehong！🌟

🌍 立志在坚不欲说，成功在久不在速🌍

🚀 欢迎关注：👍点赞⬆️留言收藏🚀

🍀欢迎使用：小智初学计算机网页IT深度知识智能体

🍀欢迎使用：深探助手deepGuide网页deepseek智能体

目录

1．排序的基本概念

关键字

排序

排序算法的稳定性

内部排序与外部排序

排序的基本方法

趟

排序算法的效率

待排序记录序列的存储结构

2．直接插入排序

直接插入排序的基本思想

直接插入排序算法

3．折半插入排序

4．起泡排序

冒泡排序算法

5．简单选择排序

简单选择排序的基本思想

简单选择排序算法

6．希尔排序

7．快速排序

快速排序的基本思想

快速排序算法

堆排序算法

9．归并排序

10．链式基数排序

初始化操作

“分配”操作

11．各种内部排序算法的比较

12. 总结

1．排序的基本概念

关键字

是数据元素中的某个数据项。如果某个数据项可以唯一地确定一个数据元素，就将其称为主关键字；否则，称为次关键字。

排序

是把一组无序地数据元素按照关键字值递增（或递减）地重新排列。如果排序依据的是主关键字，排序的结果将是唯一的。

排序算法的稳定性

如果在待排序的记录序列中有多个数据元素的关键字值相同，经过排序后，这些数据元素的相对次序保持不变，则称这种排序算法是稳定的，否则称之为不稳定的。

内部排序与外部排序

根据在排序过程中待排序的所有数据元素是否全部被放置在内存中，可将排序方法分为内部排序和外部排序两大类。内部排序是指在排序的整个过程中，待排序的所有数据元素全部被放置在内存中；外部排序是指由于待排序的数据元素个数太多，不能同时放置在内存，而需要将一部分数据元素放置在内存，另一部分数据元素放置在外设上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。本章只讨论常用的内部排序方法。

排序的基本方法

内部排序主要有 5 种方法： 插入、交换、选择、归并和基数。

趟

在排序过程中，基本动作执行一次。

排序算法的效率

评价排序算法的效率主要有两点：一是在数据量规模一定的条件下，算法执行所消耗的平均时间，对于排序操作，时间主要消耗在关键字之间的比较和数据元素的移动上，因此我们可以认为高效率的排序算法应该是尽可能少的比较次数和尽可能少的数据元素移动次数；二是执行算法所需要的辅助存储空间，辅助存储空间是指在数据量规模一定的条件下，除了存放待排序数据元素占用的存储空间之外，执行算法所需要的其他存储空间，理想的空间效率是算法执行期间所需要的辅助空间与待排序的数据量无关。

待排序记录序列的存储结构

待排序记录序列可以用顺序存储结构和和链式存储结构表示。在本章的讨论中（除基数排序外），我们将待排序的记录序列用顺序存储结构表示，即用一维数组实现。其定义如下所示：

#define MAX_NUM 80//待排序记录序列中的最大数据元素个数typedef struct elemtype {//待排序的数据元素类型keytype key;//数据元素的关键字anytype otheritem;//数据元素中的其他成份}DataType[MAX_NUM+1];95

2．直接插入排序

直接插入排序的基本思想

直接插入排序是一种比较简单的排序方法。它的基本思想是依次将记录序列中的每一个记录插入到有序段中，使有序段的长度不断地扩大。其具体的排序过程可以描述如下：首先将待排序记录序列中的第一个记录作为一个有序段，将记录序列中的第二个记录插入到上述有序段中形成由两个记录组成的有序段，再将记录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的有序段，……依此类推，每一趟都是将一个记录插入到前面的有序段中，假设当前欲处理第 i 个记录，则应该将这个记录插入到由前 i-1 个记录组成的有序段中，从而形成一个由 i 个记录组成的按关键字值排列的有序序列，直到所有记录都插入到有序段中。一共需要经过 n-1 趟就可以将初始序列的 n 个记录重新排列成按关键字值大小排列的有序序列。

直接插入排序算法

将第 i 个记录插入到由前面 i-1 个记录构成的有序段中主要有两个步骤： ⑴ 将待插入记录 a[i] 保存在 a[0]中，即 a[0]=a[i]; ⑵ 搜索插入位置：

j=i-1;//j 最初指示 i 的前一个位置while (a[0].key <a[j].key){a[j+1]=a[j];//后移关键字值大于 a[0].key 的记录j=j-1;//将 j 指向前一个记录，为下次比较做准备}a[j+1]=a[0];//将 a[0]放置在第 j+1 个位置上完整的插入排序算法为：void insertsort (DataType a, int n){for (i=2; i<=n; i++)//需要 n-1 趟{a[0]=a[i];//将 a[i]赋予监视哨j=i-1;while (a[0].key<a[j].key) //搜索插入位置{a[j+1]=a[j];j=j-1;}a[j+1]=a[0];// 将原 a[i]中的记录放入第 j+1 个位置}}

直接插入排序算法简单、容易实现，只需要一个记录大小的辅助空间用于存放待插 入的记录（在 C 语言中，我们利用了数组中的 0 单元）和两个 int 型变量。当待排序记录较少时，排序速度较快，但是，当待排序的记录数量较大时，大量的比较和移动操作将使直接插入排序算法的效率降低；然而，当待排序的数据元素基本有序时，直接插入排序过程中的移动次数大大减少，从而效率会有所提高。 插入排序是一种稳定的排序方法。一般情况下，第 i 趟的操作为：在含有 i-1 个记录的有序子序列 r[1..i-1]中插入一个新记录 r[i]，变成含有 i 个记录的有序序列r[1..i]。设置 r[0]为空值，从 r[1]开始保存信息，可首先将待插入的记录 r[i]复制到r[0]中，如下所示： 可把 r[0]看成是 r[i]的备份，以后从 r[1]～r[i-1]查找插入位置时可直接同 r[0]比较，而且 r[i]也可被覆盖了。因为 r[i]复制到 r[0]后，可认为已经空出了 r[i]。考虑从后向前比较，只要 r[i-1]≤r[i]，则 r[i]的位置不必改变，否则（即 r[i－1]>r[i]），则将 r[i-1]移动到 r[i]处，然后再比较 r[i-2]和 r[0]，依次等等。当最后找到一个比r[0]小的关键字时，将 r[0]复制到此关键字的后面一个位置，结束。具体算法为：

void InsertSort(SqList &L){for (i = 2 ; i <= L.length ; ++i ) //第一个元素认为本身有序，所以从第二个元素开始即可if ( L.r[i].key < L.r[i-1].key ) // 当 r[i]小于 r[i-1]时，需排序，否则无需排序｛ L.r[0] = L.r[i] ; //复制 L.r[i]至 L.r[0]，保证下面的 for 循环肯定能正常结束for ( j = i -1 ; L.r[0].key < L.r[j].key ; --j)L.r[j+1] = L.r[j] ; //记录后移L.r[j+1] = L.r[0] ; //插入到第一个小于 L.r[0]的元素 L.r[j]的后面}}

举例： 排序以下序列 49 38 65 97 76 13 27 49

该算法的时间复杂度是 O(n 2 )， 属稳定排序。 直接插入排序算法简单、容易实现。当待排序记录较少时，排序速度较快，但是，当待排序的记录数量较大时，大量的比较和移动操作将使直接插入排序算法的效率降低；然而，当待排序的数据元素基本有序时，直接插入排序过程中的移动次数大大减少，从而效率会有所提高。

3．折半插入排序

由于直接插入排序的基本操作是向一个有序表中进行查找和插入，因此，其中的“查找”操作可以利用“折半查找”来实现。由此改进的直接插入排序称为“折半插入排序”。由于查找是找不到需插入的记录的，因此有一个固定的结论：待插入位置是查找之后 high 指示的坐标之后的位置，即 high＋1，则从 high＋1 到 i-1 的记录需向后整体平移一个单位，变成 high＋2～i。算法入下：

void BInsertSort(SqList &L){ for (i = 2 ;i <=L.length ; ++i ){ L.r[0] = L.r[i] ;low = 1 ; high = i -1 ;while (low <= high){ mid = (low +high)/2 ;if （L.r[0].key = high + 1 ; j --)L.r[j+1] = L.r[j] ;L.r[high+1] = L.r[0] ; //high 之后的第一个位置就是合适的位置}}

该算法的时间复杂度是 O(n 2 )，属稳定排序。折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。

4．起泡排序

冒泡排序是交换排序中一种简单的排序方法。它的基本思想是对所有相邻记录的关键字值进行比效，如果是逆顺（a[j]>a[j+1]），则将其交换，最终达到有序化。其处理过程为： （1）将整个待排序的记录序列划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。 （2）对无序区从前向后依次将相邻记录的关键字进行比较，若逆序将其交换，从而使得关键字值小的记录向上“飘浮”（左移），关键字值大的记录好像石块，向下“堕落”（右移）。每经过一趟冒泡排序，都使无序区中关键字值最大的记录进入有序区，对于由 n 个记录组成的记录序列，最多经过 n-1 趟冒泡排序，就可以将这 n 个记录重新按关键字顺序排列。

冒泡排序算法

原始的冒泡排序算法对由 n 个记录组成的记录序列，最多经过（n-1）趟冒泡排序，就可以使记录序列成为有序序列，第一趟定位第 n 个记录，此时有序区只有一个记录；第二趟定位第 n-1 个记录，此时有序区有两个记录；以此类推，算法框架为：

for（i=n；i>1；i--）{定位第 i 个记录；}若定位第 i 个记录，需要从前向后对无序区中的相邻记录进行关键字的比较，它可以用如下所示的语句实现。for（j=1；ja.[j+1].key）{temp=a[j]；a[j]=a[j+1]；a[j+1]=temp；}

下面给出完成的冒泡排序算法：

void BubbleSort1 (DataType a,int n){for (i=n；i>1；i--）{for (j=1;ja.[j+1].key）{temp=a[j]；a[j]=a[j+1]；a[j+1]=temp；}}}

冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低；其次冒泡排序只需要一个记录的辅助空间，用来作为记录交换的中间暂存单元；冒泡排序是一种稳定的排序方法。 举例： 利用冒泡法对以下序列进行排序。            （49,38 ,65 ,97 ,76, 13, 27, 49） n=8 第 1 趟：38 49 65 76 13 27 49 97 第 2 趟：38 49 65 13 27 49 76 97 第 3 趟：38 49 13 27 49 65 76 97 第 4 趟：38 13 27 49 49 65 76 97 第 5 趟：13 27 38 49 49 65 76 97 第 6 趟：13 27 38 49 49 65 76 97 第 7 趟：没有必要再比了，因为上一趟（第 6 趟）没有发生交换，这说明已经排序完毕。 该算法的时间复杂度为 O（n 2 )，属于稳定排序。

5．简单选择排序

简单选择排序的基本思想

简单选择排序的基本思想是：每一趟在 n-i+1(i=1,2,3,...,n-1)个记录中选取关键字最小的记录作为有序序列中的第 i 个记录。它的具体实现过程为： (1) 将整个记录序列划分为有序区域和无序区域，有序区域位于最左端，无序区域位于右端，初始状态有序区域为空，无序区域含有待排序的所有 n 个记录。 (2) 设置一个整型变量 index，用于记录在一趟的比较过程中，当前关键字值最小的记录位置。开始将它设定为当前无序区域的第一个位置，即假设这个位置的关键字最小，然后用它与无序区域中其他记录进行比较，若发现有比它的关键字还小的记录，就将 index 改为这个新的最小记录位置，随后再用 a[index].key 与后面的记录进行比较，并根据比较结果，随时修改 index 的值，一趟结束后 index 中保留的就是本趟选择的关键字最小的记录位置。 (3) 将 index 位置的记录交换到无序区域的第一个位置，使得有序区域扩展了一个记录，而无序区域减少了一个记录。 不断重复 (2)、(3)，直到无序区域剩下一个记录为止。此时所有的记录已经按关键字从小到大的顺序排列就位。

简单选择排序算法

简单选择排序的整体结构应该为：

for (i=1;i<n;i){第 i 趟简单选择排序；}

下面我们进一步分析一下“第 i 趟简单选择排序”的算法实现。 （1）初始化：假设无序区域中的第一个记录为关键字值最小的元素，即将index=i; （2）搜索无序区域中关键字值最小的记录位置：

for (j=i+1;j< =n;j++)if (a[j].key<a.[index].ke) index=j;

（3）将无序区域中关键字最小的记录与无序区域的第一个记录进行交换，使得有序区域由原来的 i-1 个记录扩展到 i 个记录。 完整算法：

void selecsort ( DataType a, int n){for( i=1; i<n; i++)//对 n 个记录进行 n-1 趟的简单选择排序{index=i;//初始化第 i 趟简单选择排序的最小记录指针for (j=i+1;j<=n;j++)//搜索关键字最小的记录位置if (a[j].key<a[i].key) index=j;if (index!=i){ temp=a[i]; a[i]=a[index]; a[index]=temp;}}}

简单选择排序算法简单，但是速度较慢，并且是一种不稳定的排序方法.，但在排序过程中只需要一个用来交换记录的暂存单元。简单选择排序算法简单，但是速度较慢，并且是一种不稳定的排序方法，但在排序过程中只需要一个用来交换记录的暂存单元。其时间复杂度为 O(n 2 )。 举例： 利用简单选择排序算法对以下序列排序：                     （72, 73, 71 , 23, 94, 16, 5, 68） 过程： 第一趟：5 , 73, 71, 23, 94, 16, 72, 68             第二趟：5, 16， 71， 23，94， 73，72, 68             第三趟：5，16， 23， 71，94， 73，72, 68             第四趟：5，16， 23， 68，94， 73，72， 71             第五趟：5，16， 23， 68，71， 73，72，94             第六趟：5，16， 23， 68，71， 72，73，94             第七趟：5，16， 23， 68，71， 72，73，94 完成

6．希尔排序

希尔排序又称“缩小增量排序”，是一种改进的插入排序，在时间效率上有了较大的改进。对直接插入排序来说，比较的步长为 1。这种情况下，如果较小的数在序列的较后面部分，则需要一步一步的向前移动，无疑是比较慢的。如果采用步长>1 的方法，则可以使较小的数向前推进是“跳跃式”进行，故可以提高排序效率。 方法：将整个序列分成若干子序列，对各个子序列进行直接插入排序，得到一趟希尔排序序列；然后缩短步长，重复以上动作，直到步长为 1。 具体步骤如下： ① 先取一正整数 d（d<n，一般可取 d  =  n/2  ）,把所有距离为 d 的倍数的记录编在一组，组成一个子序列，这样将整个待排序序列分成若干组； ② 在各个子序列中进行直接插入排序； ③ 取一个新的 d（比原来的要小，一般取原来的 1/2），重复执行 1)，2)，直到 d＝1 为止（此时，整个序列变成直接插入排序）。 例如： 利用希尔排序对下序列进行排序。                 （72, 73, 71, 23, 94, 16, 15, 68），n＝8 过程：1> 第一次分组，取 d＝  n/2  ＝4，则对序列分组为：

对每个子序列直接插入排序得(4 组)：

2> 第二次分组，取 d = 2（原来的一半），对序列分组为：

对每个子序列直接插入排序得(2 组)：

3> 第三次分组，取 d＝1（原来的一半），序列为一组，直接插入排序得：

排序完成。 说明： 步长的选择是迄今为止还没有完全解决的。         该算法的时间复杂度 O(n 1.5 ) ，是不稳定排序（因为存在着跳跃）。

7．快速排序

快速排序的基本思想

快速排序又称为分区交换排序。其基本思想是：首先将待排序记录序列中的所有记 录作为当前待排序区域，从中任选取一个记录（比如，第一个记录），并以该记录的关键字值为基准，从位于待排序记录序列左右两端开始，逐渐向中间靠拢，交替与基准记录的关键字进行比较、交换，每次比较，若遇左侧记录的关键字值大于基准记录的关键字，则将其与基准记录交换，使其移到基准记录的右侧，若遇右侧记录的关键字值小于基准值，则将其与基准记录交换，使其移至基准记录的左侧，最后让基准记录到达它的最终位置，此时，基准记录将待排序记录分成了左右两个区域，位于基准记录左侧的记录都小于或等于基准记录的关键字，位于基准记录右侧的所有记录的关键字都大于或等于基准记录的关键字，这就是一趟快速排序；然后分别对左右两个新的待排序区域，重复上 述一趟快速排序的过程，其结果分别让左右两个区域中的基准记录都到达它们的最终位置，同时将待排序记录序列分成更小的待排序区域，再次重复对每个区域进行一趟快束排序，直到每个区域只有一个记录为止，此时所有的记录都到达了它的最终位置，即整个待排序记录按关键值有序排列，至此排序结束。         对待排序记录序列进行一趟快速排序的过程描述如下： (1) 初始化：取第一个记录作为基准，其关键字值为 19，设置两个指针 i，j 分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置。最开始从右侧开始比较，当发生交换操作后，转去再从左侧比较； (2) 用基准记录与右侧记录进行比较：即与指针 j 指向的记录进行比较，如果右侧记录的关键字值大，则继续与右侧前一个记录进行比较，即 j 减 1 后，再用基准元素与j 指向的记录比较，若右侧的记录小（逆序），则将基准记录与 j 指向的记录进行交换； (3) 用基准元素与左侧记录进行比较：即与指针 i 指向的记录进行比较，如果左侧记录的关键字值小，则继续与左侧后一个记录进行比较，即 i 加 1 后，再用基准记录与i 指向的记录比较，若左侧的记录大（逆序），则将基准记录与 i 指向的记录交换，； (4) 右侧比较与左侧比较交替重复进行，直到指针 i 与 j 指向同一位置，即指向基准记录最终的位置。 一趟快速排序之后，再分别对左右两个区域进行快速排序，以此类推，直到每个分区域都只有一个记录为止。下面是对关键字值为（19,6,47,26,18,26,7,13）的记录序列进行快速排序的各趟状态

快速排序算法

快速排序是一个递归的过程，只要能够实现一趟快速排序的算法，就可以利用递归的方法对一趟快速排序后的左右分区域分别进行快速排序。下面是一趟快速排序的算法分析： (1) 初始化： 将 i 和 j 分别指向待排序区域的最左侧记录和最右侧记录的位置。                 i=first;         j=end; 将基准记录暂存在 temp 中。                 temp=a[i]; (2) 对当前待排序区域从右侧将要进行比较的记录（j 指向的记录）开始向左侧进行扫描，直到找到第一个关键字值小于基准记录关键字值的记录：

while (i<j && temp.key<=a[j]) j--;103

(3) 如果 i!=j，则将 a[j]中的记录移至 a[i]，并将 i++：         a[i]=a[j]; i++; (4) 对当前待排序区域从左侧将要进行比较的记录（i 指向的记录）开始向右侧进行扫描，直到找到第一个关键字值大于基准记录关键字的记录：

while (i<j && a[i]<=temp.key) i++;

(5) 如果 i!=j，则将 a[i]中的记录移至 a[j]，并将 j++：         a[j]=a[i]; j++; (6) 如果此时仍 i<j，则重复上述（2）、（3）、（4）、（5）操作，否则，表明找到了基准记录的最终位置，并将基准记录移到它的最终位置上：

while （i<j）{执行(2)、(3)、(4)、(5) 步骤}a[i]=temp;下面是快速排序的完整算法。void quicksort (DataType a,int first,int end ){i=first; j=end; temp=a[i];//初始化while(i<j){while (i<j && temp.key<= a[j].key) j--；a[i]=a[j]；while (i<j && a[i].key<=temp.key) i++；a[j]=a[i]；}a[i]=temp；if (first<i-1) quicksort(a, first, i-1)；//对左侧分区域进行快速排序if (i+1<end) quicksort(a, i+1, end)； //对右侧分区域进行快速排序}

快速排序实质上是对冒泡排序的一种改进，它的效率与冒泡排序相比有很大地提高。在冒泡排序过程中是对相邻两个记录进行关键字比较和互换的，这样每次交换记录后，只能改变一对逆序记录，而快速排序则从待排序记录的两端开始进行比较和交换，并逐渐向中间靠拢，每经过一次交换，有可能改变几对逆序记录，从而加快了排序速度。到目前为止快速排序是平均速度最大的一种排序方法，但当原始记录排列基本有序或基本逆序时，每一趟的基准记录有可能只将其余记录分成一部分，这样就降低了时间效率，所以快速排序适用于原始记录排列杂乱无章的情况。快速排序是一种不稳定的排序，在递归调用时需要占据一定的存储空间用来保存每一层递归调用时的必要信息。 举例： 利用快速排序法对以下序列进行排序： 说明： 在一趟排序中，支点最后才确定位置，故只需最后一步赋值即可，中间不必 交换。即，虽然快速排序是交换排序的一种，但是可以不用交换操作即可实 现） 该算法由于有不相邻元素交换，故是不稳定排序，其时间复杂度为 O(nlog 2 n )，是内 排序中最好的方法之一。 8．堆排序 (一)堆排序的基本思想 堆排序是另一种基于选择的排序方法。下面我们先介绍一下什么是堆？然后再介绍 如何利用堆进行排序。 堆定义：由 n 个元素组成的序列{k 1 ，k 2 ，……，k n-1 ，k n }，当且仅当满足如下关系时，称之为堆。

若将堆看成是一棵以 k 1 为根的完全二叉树，则这棵完全二叉树中的每个非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此可以看出，若一棵完全二叉树是堆，则根结点一定是这 n 个结点中的最小者或最大者。下面给出两个堆的示例。

下面我们讨论一下如何利用堆进行排序？ 从堆的定义可以看出，若将堆用一棵完全二叉树表示，则根结点是当前堆中所有结点的最小者（或最大者）。堆排序的基本思想是：首先将待排序的记录序列构造一个堆，此时，选出了堆中所有记录的最小者或最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小（或次大）的记录，以此类推，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列。

堆排序算法

假设当前要进行筛选的结点编号为 k，堆中最后一个结点的编号为 m，且 a[k+1]至 a[m]之间的结点都已经满足堆的条件，则调整过程可以描述为： (1) 设置两个指针 i 和 j： i 指向当前（要筛选）的结点：i=k; j 指向当前结点的左孩子结点：j=2*i; (2) 比较当前结点的左右孩子的关键字值，并用 j 指向关键字值较大的孩子结点。 if (j<m && a[j].key<a[j+1]).key ) j++; 107 (3) 用当前结点的关键字与 j 所指向的结点关键字值进行比较，根据比较结果采取相应的操作，即结束筛选或交换结点内容并继续进行筛选。实现这个操作的语句为：

if (a[i].key>a[j].key) break;//结束筛选操作else {temp=a[i]; a[i]=a[j]; a[j]=temp;//交换结点内容i=j;j=2*i;//准备继续筛选}

可以将交换改进为：

if (a[i].key>a[j].key) break;else{ a[i]=a[j]; i=j; j=2*i; }堆排序的筛选算法：void sift (DataType a,int k,int m){i=k;；j=2*i；temp=a[i]；while (j<=m)//{if ( j < m && a[j].key  a[j] .key) break；else{ a[i]=a[j] ；i=j；j=2*i； }}a[i] = temp；}堆排序完整的算法。void heapsort (DataType a, int n){h=n/2 ;//最后一个非终端结点的编号for ( i=h ; i>=1; i--)//初建堆。从最后一个非终端结点至根结点sift ( a, i, n ) ;for ( i=n ; i>1 ; i-- )//重复执行移走堆顶结点及重建堆的操作{temp=a[1] ; a[1]=a[i]; a[i]=temp ;sift ( a , 1 , i-1 );}}

void merge (DataType a,DataType a1,int s,int m,int t){//a[s]~[m]和 a[m+1]~a[t]已经分别有序，将它们归并至 a1[s]~a1[t]中k=s; i=s; j=m+1;while(i<=m && j<=t){if (a[i].key<=a[j].key) a1[k++]=a[i++];else a1[k++]=a[j++];}if (i<=m)//将剩余记录复制到数组 a1 中while ( i<=m) a1[k++]=a[i++];if (j<=t)while (j<=t) a1[k++]=a[j++];}

for（j=0;j<r;j++）{f[j]=NULL;t[j]=NULL;}

p=h;//p 指向当前分配的结点，初始指向单链表的首结点while(p){k=p->key%n/m// “分离”if(f[k]==NULL)f[k]=p;//入队else t[k]->next=p;t[k]=p;110p=p->next;//从单链表中获取下一个结点}m=m*10; n=n*10;“收集”操作“收集”操作实际上就是将非空队列首尾相接。具体操作可以这样实现：h=NULL; p=NULL;for(j=0;jnext=f[j];p=t[j];}}

List_Node *radixsort( List_Node *h,int d,int r){n=10; m=1;for(i=1; i<=d;i++)//共“分配”、“收集”d 次{for(j=0;jkey%n/m// “分离”if(f[k]==NULL)f[k]=p;//入队else t[k]->next=p;t[k]=p;p=p->next;//从单链表中获取下一个结点}m=m*10; n=n*10;h=NULL; p=NULL;//“收集”111for(j=0;jnext=f[j];p=t[j];}}}return(h);}