下载掌阅APP，畅读海量书库
立即打开
本节将主要介绍快速排序算法的原理及其具体的实现方法。
快速排序又称为分区交换排序，简称快排。快排是排序中的一种算法，最早由托尼·霍尔提出。以从小到大快排为例，其主要思想是：
（1）在一个待排序的序列中取出一个元素作为中心元素（可以用第一个、最后一个，也可以是中间任意一个），习惯上将其称为基准；
（2）将所有比基准小的放在其左边，将所有比基准大的放在其右边，形成左右两个子表；
（3）对左右两个子表按照前面的算法进行排序，直到每个子表的元素只剩下一个。
显然，快排用到了分而治之的思想。将一个数组分成两个数组的方法为：
（1）从数组的右边找到一个比基准元素小的元素，将数组的第一个位置赋值给该元素；
（2）从数组的左边找到一个比基准元素大的元素，将从上面取元素的位置赋值为该值；
（3）依次进行，直到左右相遇，将基准元素赋值到相遇位置。
1.原始数组的第一次快速排序
为了更清楚地说明快排算法，下面举一个例子。假设一个数组：
x ={39,28,55,87,66,3,17,40}
（1）定义基准，将其初始化为第一个元素的值，即39。其中，查询左边元素的指针为left，查询右边元素的指针为right，如图1.8所示。
图1.8 初始指针left和right的位置
（2）right从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，遇到17时，因为17<基准，因此将 x ［right］填入到 x ［left］，即此时变量left指向的数为17，如图1.9所示。
图1.9 原始数组right从右向左遍历第一次的结果
（3）left从左边开始遍历，找到第一个比基准大的元素，如果没找到，left一直递增1，遇到55时，因为55>基准，因此将 x ［left］填入到 x ［right］，即此时指针right指向的数为55，如图1.10所示。
图1.10 left从左向右遍历第一次的结果
（4）right继续从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，遇到3时，因为3<基准，因此将 x ［right］填入到 x ［left］，即此时指针left指向的数为3，如图1.11所示。
图1.11 right从右向左遍历第二次的结果
（5）left从左边开始遍历，找到第一个比基准大的元素，如果没找到，left一直递增1，遇到87时，因为87>基准，因此将 x ［left］填入到 x ［right］，即此时指针right指向的数为87，如图1.12所示。
图1.12 left从左向右遍历第二次的结果
（6）right继续从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，此时出现left和right重合，因此在left和right重合的位置，填入基准值，如图1.13所示。
图1.13 left和right重合
这样，就将数组分成了两个子数组，即{17，28，3}和{66,87,55,40}。
2.第一个子数组的快速排序
本部分将介绍如何对子数组{17，28，3}进行快速排序。
（1）定义基准，将其初始化为第一个元素的值，即17。查询左边元素的指针为left，查询右边元素的指针为right，如图1.14所示。
（2）right从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，遇到3时，因为3<基准，因此将 x ［right］填入 x ［left］，即此时指针left指向的数为3，如图1.15所示。
图1.14 初始指针left和right的位置
图1.15 right从右向左遍历第一次的结果
（3）left从左边开始遍历，找到第一个比基准大的元素，如果没找到，left一直递增1，遇到28时，因为28>基准，因此将 x ［left］填入到 x ［right］，即此时指针right指向的数为28，如图1.16所示。
（4）right从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，结果left和right重合，因此在left和right重合的位置，填入基准值，如图1.17所示。
图1.16 left从左向右遍历第一次的结果
图1.17 right从右向左遍历第二次的结果
由于左侧和右侧都只有一个元素，因此排序结束。
3.第二个子数组的快速排序
本部分将介绍如何对子数组{66,87,55,40}进行快速排序。
（1）定义基准，将其初始化为第一个元素的值，即66。查询左边元素的指针为left，查询右边元素的指针为right，如图1.18所示。
（2）right从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，遇到40时，因为40<基准，因此将 x ［right］填入到 x ［left］，即此时指针left指向的数为40，如图1.19所示。
图1.18 初始指针left和right的位置
图1.19 right从右向左遍历第一次的结果
（3）left从左边开始遍历，找到第一个比基准大的元素，如果没找到，left一直递增1，遇到87时，因为87>基准，因此将 x ［left］填入到 x ［right］，即此时指针right指向的数为87，如图1.20所示。
（4）right从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，因为55<基准，因此将 x ［right］填入到 x ［left］，即此时指针left指向的数为55，如图1.21所示。
图1.20 left从左向右遍历第一次的结果
图1.21 right从右向左遍历第二次的结果
（5）left从左边开始遍历，找到第一个比基准大的元素，如果没找到，left一直递增1，结果left和right重合，因此在left和right重合的位置，填入基准值，如图1.22所示。
由于左侧有两个元素{40,55}，因此需要再一次快排；而右侧只有一个元素，因此无须进行排序。
4.第三个子数组的快速排序
本部分将介绍如何对子数组{40,55}进行快速排序。
（1）定义基准，将其初始化为第一个元素的值，即40。查询左边元素的指针为left，查询右边元素的指针为right，如图1.23所示。
图1.22 left从左向右遍历第二次的结果
图1.23 初始指针left和right的位置
（2）right从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，结果left和right重合，因此在left和right重合的位置，填入基准值，如图1.24所示。
图1.24 right从右向左遍历第一次的结果
因此，快速排序的过程如图1.25所示。
图1.25 快速排序的过程
实现快速排序算法的C语言代码如代码清单1-3所示。
代码清单1-3 实现快速排序算法的C语言代码
注 ：读者可以定位到本书提供资源的＼loongson1B_training_example＼example_1_3目录中，使用LoongIDE软件工具打开example_1_3.lxp工程文件。
本节将介绍如何对设计工程进行编译，并通过调试器对C语言设计代码进行调试。具体实现步骤如下所示。
（1）编译程序代码，给龙芯1B硬件开发平台上电。
（2）如图1.26所示，在代码清单1-3中设置第一个断点。
图1.26 在代码清单1-3中设置第一个断点
（3）如图1.27所示，在代码清单1-3中设置第二个断点。
图1.27 在代码清单1-3中设置第二个断点
（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.28所示的“Watchs”标签页。
图1.28 “Watchs”标签页
实现快速排序算法的汇编语言代码如代码清单1-4所示。
代码清单1-4 实现快速排序算法的汇编语言代码
注 ：读者可以定位到本书提供资源的＼loongson1B_training_example＼example_1_4目录中，使用LoongIDE软件工具打开example_1_4.lxp工程文件。
本节将介绍如何对前面所设计的汇编语言代码进行编译，并在龙芯1B硬件开发平台上进行调试和验证。具体实现如下所示。
（1）编译程序代码，给龙芯1B硬件开发平台上电。
（2）如图1.29所示，在代码清单1-4中设置第一个断点。
图1.29 在代码清单1-4中设置第一个断点
（3）如图1.30所示，在代码清单1-4中设置第二个断点。
图1.30 在代码清单1-4中设置第二个断点
（4）在LoongIDE主界面主菜单下，选择Debug->Run，进入调试器界面，此时程序自动停到第一个断点处。
（5）单击“CPU Registers”标签，在“CPU Registers”标签页中找到寄存器名字为“s0”的一行，并用鼠标左键双击该行，弹出“View Memory”对话框，如图1.31所示。
（6）从图1.31可以看出，用于存放数据段中名字为“arr”的存储空间的首地址为0x802125a0，同时也可看到从该地址开始的8个要排序的数据，即0x0003、0x0008、0x0001、0x0005、0x0002、0x0004、0x0006和0x0007。
（7）单击图1.31中的按钮图标
，退出“View Memory”对话框。
（8）在LoongIDE主界面主菜单下，选择Debug->Run，程序停到第二个断点处。
（9）单击“CPU Registers”标签，在“CPU Registers”标签页中找到寄存器名字为“s0”的一行，并用鼠标左键双击该行，弹出“View Memory”对话框，如图1.32所示。从图1.32中可以看出，用于存放数据段中名字为“arr”的存储空间的首地址为0x802125a0，同时也可看到从该地址开始的8个已经排完序的数据，即0x0001、0x0002、0x0003、0x0004、0x0005、0x0006、0x0007和0x0008。
图1.31 “View Memory”对话框（1）
图1.32 “View Memory”对话框（2）