1.3 插入排序的原理和实现

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

1.3.1 插入排序的原理

插入排序算法也是一种常见的排序算法，其基本思想是：将需要排序的数据分为有序和无序两部分，排序的每一步将无序部分的数据插入前面已经排好序的有序部分，直到插完所有数据元素为止。

在实现插入排序算法时，每次从无序部分中取出一个元素与有序部分中的元素从后向前依次进行比较，并找到合适的位置将该元素插到有序部分。

假设6个要排序的数据元素为2、3、5、9、4和7。下面以该排序过程中的其中一个步骤为例，说明插入排序算法的具体实现过程。在插入排序过程中，6个数据元素中的有序部分为（2、3、5、9），无序部分为（4,7），需要将无序部分的数据元素4插入有序部分，具体过程如下。

（1）原始的数组元素排列顺序如下：

其中，带有阴影的数据元素表示有序部分，不带阴影的数据元素表示无序部分。

（2）在无序部分挑出要插入有序部分的数据元素4，将要插入的数据元素4与该数据元素左边最近的有序部分的元素进行比较。由于4 < 9，因此数据元素9向后移动，而数据元素4向前移动：

（3）将要插入的数据元素4与该数据元素左边最近的有序部分的数据元素5进行比较。由于4 < 5，因此数据元素5向后移动，而数据元素4继续向前移动：

（4）将要插入的数据元素4与该数据元素左边最近的有序部分的数据元素3进行比较。由于4 > 3，因此不需要再向前比较，将数据元素4插入当前位置：

此时，有序部分的数据元素由开始的（2、3、5、9）变成了（2、3、4、5、9）。

1.3.2 C语言程序设计

实现插入排序算法的C语言代码如代码清单1-5所示。

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

1.3.3 C语言编译和调试

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

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

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

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

（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.35所示的“Watchs”标签页。

1.3.4 汇编语言程序设计

实现插入排序算法的汇编语言代码如代码清单1-6所示。

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

1.3.5 汇编语言编译和调试

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

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

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

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

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

（5）单击“CPU Registers”标签，在“CPU Registers”标签页中找到寄存器名字为“s0”的一行，并用鼠标左键双击该行，弹出“View Memory”对话框，如图1.38所示。从图1.38中可以看出，用于存放数据段中名字“arr”的存储空间的首地址为0x80212530，同时也可看到从该地址开始的8个要排序的数据，即0x0003、0x0008、0x0001、0x0005、0x0002、0x0004、0x0006和0x0007。

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

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

（8）单击“CPU Registers”标签，在“CPU Registers”标签页中找到寄存器名字为“s0”的一行，并用鼠标左键双击该行，弹出“View Memory”对话框，如图1.39所示。从图1.39中可以看出，用于存放数据段中名字为“arr”的存储空间的首地址为0x80212530，同时也可看到从该地址开始的8个已经排完序的数据，即0x0001、0x0002、0x0003、0x0004、0x0005、0x0006、0x0007和0x0008。