下载掌阅APP，畅读海量书库
立即打开
本节将主要介绍希尔排序算法的原理及其具体的实现方法。
希尔排序又称缩小增量排序，是插入排序的一种优化版本。优化的主要地方在于，不需要在每次插入一个元素时就与序列中有序部分中的所有元素进行比较。
假设待排序序列中有 n 个数据元素，则使用希尔排序算法对其进行排序的基本思想是：
（1）取一个整数（increment，小于待排序序列中的数据元素总数）作为间隔，将所有距离为increment的数据元素放在同一个逻辑数组中，并对每一个逻辑数组中的数据元素通过插入排序算法对其中的数据元素进行排序。
（2）缩小increment，重复上述逻辑数组划分和排序工作。直到最后使得increment等于1时，将所有数据元素放在同一个数组中进行排序为止。
从上面给出的希尔排序思想可知，实现希尔排序的具体步骤如下：
（1）选取increment，划分逻辑分组，通过插入排序算法对组内的数据元素进行排序；
（2）不断缩小increment，继续通过插入排序算法对组内的数据元素进行排序；
（3）直到increment=1，在包含所有数据元素的序列内进行插入排序操作。
假如待排序序列中有6个数据元素，分别为3、5、9、2、4和7。对该待排序序列进行希尔排序的过程如下：
（1）第一次排序开始时选取increment的方法是，执行6除以3的运算后向下取整加1，得到：
这样，将整个待排序序列划分为间隔为3的3个逻辑分组，对每一个逻辑分组内的数据元素进行插入排序，相当于对整个待排序序列进行了部分排序调整，如图1.47所示。
（2）第二次排序开始时选取increment的方法是，执行3除以3的运算后向下取整再加1，得到：
这样，将整个待排序序列划分为2个间隔为2的逻辑分组，对每个逻辑分组内的数据元素进行插入排序，如图1.48所示。
图1.47 第一次排序的过程
图1.48 第二次排序的过程
（3）第三次排序开始时选取increment的方法是，执行2除以3的运算后向下取整再加1，得到：
图1.49 第三次排序的过程
这样，当increment（增量）为1的时候，实际上就是将整个待排序序列作为一个逻辑分组，对其内的数据元素进行插入排序，如图1.49所示，
从上面给出的排序过程可以看出，希尔排序与插入排序相似。这是因为，希尔排序就是插入排序的优化版本，两者不同的之处在于，希尔排序的间隔慢慢缩减为1，而直接插入排序的间隔一直为1。
实现希尔排序算法的C语言代码如代码清单1-9所示。
代码清单1-9 实现希尔排序算法的C语言代码
注 ：读者可以定位到本书提供资源的＼loongson1B_training_example＼example_1_9目录中，使用LoongIDE软件工具打开example_1_9.lxp工程文件。
本节将介绍如何对设计工程进行编译，并通过调试器对C语言设计代码进行调试。具体实现步骤如下所示。
（1）编译程序代码，给龙芯1B硬件开发平台上电。
（2）如图1.50所示，在代码清单1-9中设置第一个断点。
图1.50 在代码清单1-9中设置第一个断点
（3）如图1.51所示，在代码清单1-9中设置第二个断点。
图1.51 在代码清单1-9中设置第二个断点
（4）在LoongIDE主界面主菜单下，选择Debug->Run，进入调试器界面。
（5）在调试器界面中，单击“Watchs”标签。在该标签页中，单击鼠标右键，出现浮动菜单。在浮动菜单内，选择Add Watch，弹出“Add Variable Watch”对话框。
图1.52 “Watchs”标签页
（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.52所示的“Watchs”标签页。
实现希尔排序算法的汇编语言代码如代码清单1-10所示。
代码清单1-10 实现希尔排序算法的汇编语言代码
注 ：读者可以定位到本书提供资源的＼loongson1B_training_example＼example_1_10目录中，使用LoongIDE软件工具打开example_1_10.lxp工程文件。
本节将介绍如何对前面所设计的汇编语言代码进行编译，并在龙芯1B硬件开发平台上进行调试和验证。具体实现步骤如下所示。
（1）编译程序代码，给龙芯1B硬件开发平台上电。
（2）如图1.53所示，在代码清单1-10中设置第一个断点。
图1.53 在代码清单1-10中设置第一个断点
（3）如图1.54所示，在代码清单1-10中设置第二个断点。
图1.54 在代码清单1-10中设置第二个断点
（4）在LoongIDE主界面主菜单下，选择Debug->Run，进入调试器界面，程序自动停在第一个断点处。
（5）单击“CPU Registers”标签，在“CPU Registers”标签页中找到寄存器名字为“s0”的一行，并用鼠标左键双击该行，弹出“View Memory”对话框，如图1.55所示。在图1.55中可以看出，用于存放数据段中名字为“arr”的存储空间的首地址为0x80212548，同时也可看到从该地址开始的8个要排序的数据，即0x0063（十进制数99）、0x004e（十进制数78）、0x0041（十进制数65）、0x0020（十进制数32）、0x0017（十进制数23）、0x000d（十进制数13）、0x0070（十进制数112）和0x007f（十进制数127）。
（6）单击图1.55中的按钮图标
，退出“View Memory”对话框。
（7）在LoongIDE主界面主菜单下，选择Debug->Run，程序停在第二个断点处。
（8）单击“CPU Registers”标签，在“CPU Registers”标签页中找到寄存器名字为“s0”的一行，并用鼠标左键双击该行，弹出“View Memory”对话框，如图1.56所示。在图1.56中可以看出，用于存放数据段中名字为“arr”的存储空间的首地址为0x80212548，同时也可看到从该地址开始的8个已经排完序的数据，即0x000d（十进制数13）、0x00017（十进制数23）、0x0020（十进制数32）、0x0041（十进制数65）、0x004e（十进制数78）、0x0063（十进制数99）、0x0070（十进制数112）和0x007f（十进制数127）。
图1.55 “View Memory”对话框（1）
图1.56 “View Memory”对话框（2）