1.4 基数排序的原理和实现

本节将主要介绍基数排序算法的原理及其具体的实现方法。

1.4.1 基数排序的原理

基数排序算法的核心思想是：利用除法和取余即可得到一个数值的某一位。基数排序算法，即根据数值的位（如个位、十位、百位等）来进行排序的算法，该算法有点类似哈希表。在基数排序中，首先在待排序数中找到最大的数，其次算出该数有几位，最后依次根据个位、十位、百位、千位、…、最大位进行排序。假设对8个数进行基数排序，如表1.1所示。在待排序的数中，最大的数为999，该数有个位、十位和百位。

（1）根据个位排序，将以上8个数按照个位大小放入对应的桶中，如表1.2所示。

（2）按照从左到右、从上到下的顺序将表1.2桶中的元素重新放入数组arr中，如表1.3所示。

（3）根据十位进行排序，将以上8个数按照十位大小依次放入对应的桶中，如表1.4所示。

（4）按照从左到右、从上到下的顺序将表1.4桶中的元素重新放入数组arr中，如表1.5所示。

（5）根据百位进行排序，将以上8个数按照百位大小依次放入对应的桶中，如表1.6所示。

（6）按照从左到右、从上到下的顺序将表1.6桶中的元素重新放入数组arr中，如表1.7所示。

由上述过程可知，基数排序就是重复进行“置入”与“取出”过程，其整体“置入”与“取出”的次数只与待排序数据的最大值有关。为什么先对“个位”进行排序，而不是我们通常比较两个数时先比较最高位？因为最后排序的位数对结果的影响最大。在此算法中，先排最低位，后排最高位，最低位对最终结果影响最小、最高位对最终结果影响最大，符合客观逻辑。

1.4.2 C语言程序设计

实现基数排序算法的C语言代码如代码清单1-7所示。

注 ：读者可以定位到本书提供资源的＼loongson1B_training_example＼example_1_7目录中，使用LoongIDE软件工具打开example_1_7.lxp工程文件。

1.4.3 C语言编译和调试

本节将介绍如何对设计工程进行编译，并通过调试器对C语言设计代码进行调试。具体实现步骤如下所示。

（1）编译程序代码，给龙芯1B硬件开发平台上电。

（2）如图1.40所示，在代码清单1-7中设置第一个断点。

（3）如图1.41所示，在代码清单1-7中设置第二个断点。

（4）在LoongIDE主界面主菜单下，选择Debug->Run，进入调试器界面。

（5）在调试器界面中，单击“Watchs”标签。在该标签页中，单击鼠标右键，出现浮动菜单。在浮动菜单内，选择Add Watch，弹出“Add Variable Watch”对话框。

（6）在“Add Variable Watch”对话框中的文本框中输入“arr［0］”，单击“OK”按钮，退出该对话框。

（7）重复步骤（5）和（6），再添加7个变量，即arr［1］、arr［2］、arr［3］、arr［4］、arr［5］、arr［6］、arr［7］。

（8）在LoongIDE主界面主菜单下，选择Debug->Run，程序停在第二个断点处。

（9）单击“Watchs”标签，即可看到如图1.42所示的“Watchs”标签页。

1.4.4 汇编语言程序设计

实现基数排序算法的汇编语言代码如代码清单1-8所示。

注 ：读者可以定位到本书提供资源的＼loongson1B_training_example＼example_1_8目录中，使用LoongIDE软件工具打开example_1_8.lxp工程文件。

1.4.5 汇编语言编译和调试

本节将介绍如何对前面所设计的汇编语言代码进行编译，并在龙芯1B硬件开发平台上进行调试和验证。具体实现步骤如下所示：

（1）编译程序代码，给龙芯1B硬件开发平台上电。

（2）如图1.43所示，在代码清单1-8中设置第一个断点。

（3）如图1.44所示，在代码清单1-8中设置第二个断点。

（4）在LoongIDE主界面主菜单下，选择Debug->Run，进入调试器界面，程序自动停在第一个断点处。

（5）单击“CPU Registers”标签，在“CPU Registers”标签页中找到寄存器名字为“s1”的一行，并用鼠标左键双击该行，弹出“View Memory”对话框，如图1.45所示。从图1.45中可以看出，存放数据段中名字为“arr”的存储空间的首地址为0x802125f8，同时也可看到从该地址开始的8个要排序的数据，即0x0021（十进制数33）、0x003a（十进制数58）、0x03e7（十进制数999）、0x0000（十进制数0）、0x00e9（十进制数233）、0x0036（十进制数54）、0x0085（十进制数133）和0x0007（十进制数7）。

（6）单击图1.45中的按钮图标 ，退出“View Memory”对话框。

（7）在LoongIDE主界面主菜单下，选择Debug->Run，程序停在第二个断点处。

（8）单击“CPU Registers”标签，在“CPU Registers”标签页中找到寄存器名字为“s1”的一行，并用鼠标左键双击该行，弹出“View Memory”对话框，如图1.46所示。从图1.46中可以看出，用于存放数据段中名字为“arr”的存储空间的首地址为0x802125f8，同时也可看到从该地址开始的8个已经排完序的数据，即0x0000（十进制数0）、0x0007（十进制数7）、0x0021（十进制数33）、0x0036（十进制数54）、0x003a（十进制数58）、0x0085（十进制数133）、0x00e9（十进制数233）和0x03e7（十进制数999）。