下载掌阅APP，畅读海量书库
立即打开
本节将主要介绍归并排序算法的原理及其具体的实现方法。
简单来说，归并排序就是首先将初始序列的 n 个记录看作 n 个有序的子序列，每个子序列的长度为1，然后两两归并，得到 n/ 2个长度为2的有序子序列。在此基础上，再对长度为2的有序子序列进行两两归并，得到若干个长度为4的有序子序列。以此类推，直到得到一个长度为 n 的有序序列为止。
下面对图1.57中包含8个数据元素的序列进行归并排序。
在进行归并排序之前，首先将序列分为两个子序列，如图1.58所示。
图1.57 待归并排序的8个数据元素
图1.58 将待排序序列平均分为左右两个子序列
然后再想办法将左边的子序列（8、6、2、3）和右边的子序列（1、5、7、4）分别进行排序，之后再将它们归并在一起。
显然，在对左边的子序列和右边的子序列进行排序的时候，需要将左边的子序列和右边的子序列分别分成两个子序列，然后再对每个子序列先排序再归并，如图1.59所示。
图1.59 将图1.58给出的左右两个子序列继续进行划分
按照上面的思路，将图1.59划分出的4个子序列进一步划分为左右两个子序列，如图1.60 所示。此时，每个子序列中只有一个数据元素，因此无须继续划分，只需要对它们进行一次简单的归并即可。
图1.60 将图1.59给出的左右两个子序列继续进行划分
用二叉树表示上面“分离”的过程，如图1.61所示。
图1.61 用二叉树表示归并排序中的“分离”过程
开始归并的过程，将图1.61中的叶子节点进行第一次归并后的结果如图1.62所示。
图1.62 第一次归并后的结果
归并到上一个层级之后继续归并，如图1.63所示。
图1.63 第二次归并后的结果
继续进行归并，直到最高层，如图1.64所示。
图1.64 最后一次归并后的结果
用类似“倒二叉树”的结构表示上面的“归并”过程，如图1.65所示。
图1.65 归并过程的“倒二叉树”结构表示
下面要解决的问题就是：如果有两个已经排序好的子序列，那么如何将它们归并成一个序列？一个实现方法就是，开辟一个临时数组来辅助归并过程。也就是说，归并排序比其他排序方法多使用了存储空间，即需要 O ( n )的额外空间来完成这个排序过程。虽然多消耗了额外的存储空间，但是在当前时代，时间效率的重要性要远大于空间效率的重要性。而且，现在的计算机中提供的存储器的容量越来越大。所以，对于一个算法来说，时间复杂度是需要优先考虑的。
从整体上来说，归并排序要使用3个索引来在数组内进行追踪。例如，对于子序列（2，3，6，8）给出将它们归并为一个序列的具体实现过程如下。
（1）由于1<2，因此将1填入到右侧的序列中，并且右移指针j，使其指向数据元素4，如图1.66所示。
图1.66 归并过程的步骤（1）
（2）由于4>2，因此将2填入右侧的序列中，并且右移指针i，使其指向数据元素3，如图1.67所示。
图1.67 归并过程的步骤（2）
（3）由于4>3，因此将3填入右侧的序列中，并且右移指针i，使其指向数据元素6，如图1.68所示。
图1.68 归并过程的步骤（3）
（4）由于4<6，因此将4填入右侧的子序列中，并且右移指针j，使其指向数据元素5，如图1.69所示。
图1.69 归并过程的步骤（4）
（5）由于5<6，因此将5填入右侧的子序列中，并且右移指针j，使其指向数据元素7，如图1.70所示。
图1.70 归并过程的步骤（5）
（6）由于6<7，因此将6填入右侧的子序列中，并且右移指针i，使其指向数据元素8，如图1.71所示。
图1.71 归并过程的步骤（6）
（7）由于7<8，因此将7填入右侧的子序列中，如图1.72所示。
图1.72 归并过程的步骤（7）
（8）剩下左侧子序列中的最后一个元素8，将其填入右侧的子序列中，如图1.73所示。
图1.73 归并过程的步骤（8）
（9）将右侧子序列中的所有数据元素按顺序复制到原来的序列中即可。
实现归并排序算法（递归实现）的C语言代码如代码清单1-11所示。
代码清单1-11 实现归并排序算法（递归实现）的C语言代码
注 ：读者可以定位到本书提供资源的＼loongson1B_training_example＼example_1_11目录中，使用LoongIDE软件工具打开example_1_11.lxp工程文件。
本节将介绍如何对设计工程进行编译，并通过调试器对C语言设计代码进行调试。具体实现步骤如下所示。
（1）编译程序代码，给龙芯1B硬件开发平台上电。
（2）如图1.74所示，在代码清单1-11中设置第一个断点。
图1.74 在代码清单1-11中设置第一个断点
（3）如图1.75所示，在代码清单1-11中设置第二个断点。
图1.75 在代码清单1-11中设置第二个断点
（4）在LoongIDE主界面主菜单下，选择Debug->Run，程序停在第一个断点处。
（5）在调试器界面中，单击“Watchs”标签。在该标签页中，单击鼠标右键，出现浮动菜单。在浮动菜单内，选择Add Watch，弹出“Add Variable Watch”对话框。
（6）在“Add Variable Watch”对话框中的文本框中输入“arr［0］”，单击“OK”按钮，退出该对话框。
（7）重复步骤（5）和（6），再添加8个变量，即arr［1］、arr［2］、arr［3］、arr［4］、arr［5］、arr［6］、arr［7］和arr［8］。
（8）在LoongIDE主界面主菜单下，选择Debug->Run，程序停在第二个断点处。
（9）单击“Watchs”标签，即可看到如图1.76所示的“Watchs”标签页。
图1.76 “Watchs”标签页
实现归并排序算法（非递归实现）的C语言代码如代码清单1-12所示。
代码清单1-12 实现归并排序算法（非递归实现）的C语言代码
注 ：读者可以定位到本书提供资源的＼loongson1B_training_example＼example_1_12目录中，使用LoongIDE软件工具打开example_1_12.lxp工程文件。
本节将介绍如何对设计工程进行编译，并通过调试器对C语言设计代码进行调试。具体实现步骤如下所示。
（1）编译程序代码，给龙芯1B硬件开发平台上电。
（2）如图1.77所示，在代码清单1-12中设置第一个断点。
图1.77 在代码清单1-12中设置第一个断点
（3）如图1.78所示，在代码清单1-12中设置第二个断点。
图1.78 在代码清单1-12中设置第二个断点
（4）在LoongIDE主界面主菜单下，选择Debug->Run，进入调试器界面，程序自动停到第一个断点处。
（5）在调试器界面中，单击“Watchs”标签。在该标签页中，单击鼠标右键，出现浮动菜单。在浮动菜单内，选择Add Watch，弹出“Add Variable Watch”对话框。
图1.79 “Watchs”标签页
（6）在“Add Variable Watch”对话框中的文本框中输入“arr［0］”，单击“OK”按钮，退出该对话框。
（7）重复步骤（5）和（6），再添加8个变量，即arr［1］、arr［2］、arr［3］、arr［4］、arr［5］、arr［6］、arr［7］和arr［8］。
（8）在LoongIDE主界面主菜单下，选择Debug->Run，程序停在第二个断点处。
（9）单击“Watchs”标签，即可看到如图1.79所示的“Watchs”标签页。
实现归并排序算法的汇编语言代码如代码清单1-13所示。
代码清单1-13 实现归并排序算法的汇编语言代码
注 ：读者可以定位到本书提供资源的＼loongson1B_training_example＼example_1_13目录中，使用LoongIDE软件工具打开example_1_13.lxp工程文件。
本节将介绍如何对前面所设计的汇编语言代码进行编译，并在龙芯1B硬件开发平台上进行调试和验证。具体实现步骤如下所示。
（1）编译程序代码，给龙芯1B硬件开发平台上电。
（2）在LoongIDE主界面主菜单下，选择Project->Compile&Build，对整个工程文件进行编译和链接，生成可执行代码。
（3）如图1.80所示，在代码清单1-13中设置第一个断点。
图1.80 在代码清单1-13中设置第一个断点
（4）如图1.81所示，在代码清单1-13中设置第二个断点。
图1.81 在代码清单1-13中设置第二个断点
（5）在LoongIDE主界面主菜单下，选择Debug->Run，进入调试器界面，程序自动停到第一个断点处。
（6）单击在“CPU Registers”标签页中，找到寄存器名字为“s1”的一行，并用鼠标左键双击该行，弹出“View Memory”对话框，如图1.82所示。在图1.82中可以看出，用于存放数据段中名字为“arr”的存储空间的首地址为0x80212688。
（7）在“View Memory”对话框中，按如下设置参数。
① Count：18（通过“Count”右侧的旋转旋钮设置）。
② 单击“Fetch”按钮。
同时，该对话框中也显示了从该地址开始的9个要排序的数据，即0x0009、0x0005、0x0002、0x0007、0x000c、0x0004、0x0003、0x0001和0x000b。
（8）单击图1.82中按钮图标
，退出“View Memory”对话框。
（9）在LoongIDE主界面主菜单下，选择Debug->Run，程序停在第二个断点处。
（10）单击“CPU Registers”标签，在“CPU Registers”标签页中，找到寄存器名字为“s1”的一行，并用鼠标左键双击该行，弹出“View Memory”对话框，如图1.83所示。在图1.83中可以看出，用于存放数据段中名字为“arr”的存储空间的首地址为0x80212688，同时也可看到从该地址开始的9个已经排完序的数据，即0x0001、0x0002、0x0003、0x0004、0x0005、0x0007、0x0009、0x000b和0x000c。
图1.82 “View Memory”对话框（1）
图1.83 “View Memory”对话框（2）