1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 1 及答案与解析一、单项选择题1 某内部排序方法的稳定性是指_。【南京理工大学 1997 年】（A）该排序算法不允许有相同的关键字记录（B）该排序算法允许有相同的关键字记录（C）平均时间为 O(nlogn)的排序方法（D）以上都不对2 若要求尽可能快地对序列进行稳定的排序，则应选_。【北京邮电大学 2001年】（A）快速排序（B）归并排序（C）冒泡排序（D）根排序3 下列排序方法中，_是稳定的排序方法。【北方交通大学 2001】（A）直接选择排序（B）二分法插入排序（C）希尔排序（D）快速排序4 对有 n 个记录的表做直接插入排序，在最好情况
2、下，需比较_次关键字。【华中科技大学 2006 年】（A）n-1（B） n+1（C） n2（D）n(n-1)25 对 n 个不同的数据利用冒泡法从小到大排序，在下列哪种情况下元素交换的次数最多_。【北京交通大学 2007 年】（A）从大到小排列好的（B）从小到大排列好的（C）元素无序（D）元素基本有序6 采用简单选择排序，比较次数与移动次数分别为_。【南京理工大学 2000 年】（A）O(n)， O(10gn)（B） O(logn)，O(n*n)（C） O(n*n)，O(n)（D）O(nlogn) ，O(n)7 希尔排序属于_。【太原科技大学 2006 年】（A）插入排序（B）交换排序（C）选
3、择排序（D）归并排序8 对序列15，9，7，8， 20，一 1，4 用希尔排序方法排序，经一趟后序列变为15，一 1，4 ，8，20，9 ，7 则该次采用的增量是 _。【南京理工大学 1999 年】（A）1（B） 4（C） 3（D）29 有些排序算法在每趟排序过程中，都会有一个元素被放置到其最终位置上，下列算法不会出现此种情况的是_。【北京交通大学 2005 年】（A）希尔排序（B）堆排序（C）冒泡排序（D）快速排序10 从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于等于所选元素，而所选元素处在排序的最
4、终位置。这种排序法称为_。【北京航空航天大学 2005 年】（A）插入排序法（B）冒泡排序法（C）希尔排序法（D）快速排序法11 一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_。【北京交通大学 2005 年】（A）(38 ，40，46，56，79，84)（B） (40，38，46，79，56，84)（C） (40，38，46，56，79，84)（D）(40 ，38，46，84，56，79)12 对下列 4 个序列，以第一个关键字为基础用快速排序算法进行排序，在第一趟过程中移动记录次数最多的是_。【电子科技大学 2007
5、年】（A）92，96，100，110，42，35，30，88（B） 92，96，88，42，30，35，110，100（C） 100，96，92，35，30，110，88，42（D）42，30，35，92，100，96，88，11013 快速排序方法在_情况下最不利于发挥其长处。【华南理工大学 2007 年】（A）要排序的数据量太大（B）要排序的数据中含有多个相同值（C）要排序的数据个数为奇数（D）要排序的数据已基本有序14 对 n 个元素的表做快速排序，最坏情况下，算法的时间复杂度为_。【华中科技大学 2006 年】（A）O(log 2n)（B） O(nlog2n)（C） O(n2)（D）O
6、(2 n)15 对以下关键字序列用快速排序算法进行排序，速度最慢的是_。【北京交通大学 2002 年】（A）20，24，4，16，22，29（B） 24，22，29，16，20，4，8（C） 20，8，16，29，24，22，4（D）4，8，16，20，24，2916 快速排序在最坏的情况下的时间复杂度与下面哪个算法的最坏情况下的时间复杂度相同_。【北京交通大学 2006 年】（A）希尔排序（B）堆排序（C）冒泡排序（D）基数排序17 根据堆的定义，下面 4 个序列中，构成堆的是_。【广东工业大学 2002 年】（A）77，67，32，17，27，47，22，12（B） 77，67，47，12
7、，32，27，22，17（C） 77，47，67，32，17，27，22，12（D）77，47，67，12，27，32，22，1718 有组数据(15，9，7，8，20，一 1，7，4)，用堆排序的筛选方法建立的初始堆为_。【南京理工大学 1996 年】（A）一 1，4，8，9，20，7，15，7（B）一 1，7，15，7，4，8，20，9（C）一 1，4，7，8，20，15，7，9（D）A，B，C 均不对。19 构建 n 个记录的初始堆，其时间复杂度为_。【华中科技大学 2006 年】（A）O(n)（B） O(n2)（C） O(log2n)（D）O(nlog 2n)20 在对 n 个元素的序
8、列进行排序时，堆排序所需要的附加存储空间是_。【西安电子科技大学 2001 年】（A）O(log 2n)（B） O(1)（C） O(n)（D）O(nlog 2n)21 对 n 个记录的文件进行堆排序，最坏情况下的执行时间是_。【北京交通大学 2001 年（A）O(log 2n)（B） O(n)（C） O(nlog2n)（D）O(n 2)22 归并排序中，归并趟数的数量级是_。【南京理工大学 2000 年】（A）O(n)（B） O(log2n)（C） O(nlog2n)（D）O(n 2)23 对具有 n 个元素的序列采用二路归并排序算法排序，算法的空间复杂度是_。【北京航空航天大学 2007 年
9、】（A）O(n)（B） O(2n)（C） O(n2)（D）O(log 2n)24 若需在 O(nlog2n)的时间内完成对数组的排序，且要求排序是：稳定的，则可选择的排序方法是_。【北京交通大学 2004 年】【太原科技大学 2007 年】（A）快速排序（B）堆排序（C）归并排序（D）直接插入排序25 排序趟数与序列的原始状态有关的排序方法是_排序法。【北京航空航天大学 1999 年】（A）插入（B）选择（C）冒泡（D）基数26 下列排序方法中，_在待排序的数据为有序时，花费时间反而最多。【华中科技大学 2007 年】（A）快速排序（B）插入排序（C）堆排序（D）冒泡排序27 当待排序序列基本
10、有序时，下列方法中_最好。【北京邮电大学 2005 年】（A）直接插入排序（B）快速排序（C）堆排序（D）归并排序28 下面给出的 4 种排序方法中，排序过程中的比较次数与序列初始状态无关的是_。【北京航空航天大学 2000 年】（A）选择排序法（B）插入排序法（C）快速排序法（D）堆积排序法29 用直接插入排序方法对下面 4 个序列进行排序(由小到大)，元素比较次数最少的是_。【北方交通大学 2001 年】（A）94，32，40，90，80，46，21，69（B） 32，40，21，46，69，94，90，80（C） 21，32，46，40，80，69，90，94（D）90，69，80，46
11、，21，32，94，4030 数据序列(2，1，4，9，8，10，6，20)只能是下列排序算法中的_的两趟排序后的结果。【合肥工业大学 2000 年】（A）快速排序（B）冒泡排序（C）选择排序（D）插入排序31 对一组数据(84，47，25，15，21)排序，数据的排列次序在排序的过程中的变化为：(1)84,47,25,15,21(2)15,47,25,84,21(3)15,21,25,84,47(4)15,21,25,47,84 则采用的排序是_。【南京理工大学 1997 年】（A）选择（B）冒泡（C）快速（D）插入32 下列排序算法中，_算法可能会出现下面情况：在最后一趟开始之前，所有元素
12、都不在其最终的位置上。【南开大学 2000 年】【西北大学 2001 年】（A）堆排序（B）冒泡排序（C）快速排序（D）插入排序33 用某种排序方法对关键字序列(25，84，21，47，15，27，68，35，20)进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，84,15，20，21，25，35，27，47，68，84,15，20，21，25，27，35，47，68，84 则所采用的排序方法是_。【北京交通大学 2003 年】（A）选择排序（B）希尔排序（C）归并排序（D）快速排序34 若序列的原始状态为 1，2，3，4，5，10，6，7，8，9，要想使得排序
13、过程中元素比较次数最少，则应该采用_方法。【北京航空航天大学 2004 年】（A）插入排序（B）选择排序（C）希尔排序（D）冒泡排序35 下列排序算法中_排序在一趟结束后不一定能选出一个元素放在其最终位置上。【南京理工大学 2001 年】【哈尔滨工业大学 2001 年】（A）选择（B）冒泡（C）归并（D）堆36 在下面的排序方法中，辅助空间为 O(n)的是_ 。【南京理工大学 1999 年】（A）希尔排序（B）堆排序（C）选择排序（D）归并排序37 下列排序算法中，占用辅助空间最多的是_。【厦门大学 2002 年】（A）归并排序（B）快速排序（C）希尔排序（D）堆排序38 对初始状态为递增序列
14、的表按递增顺序排序，最省时间的是_算法，最费时间的是_算法。【南开大学 2000 年】（A）堆排序（B）快速排序（C）插入排序（D）归并排序39 就平均性能而言，目前最好的内部排序方法是_排序法。【西安电子科技大学 1998 年】（A）冒泡（B）希尔插入（C）交换（D）快速40 如果只想得到 1000 个元素组成的序列中第 lO 个最小元素之前的部分排序的序列，用_方法最快。【北京交通大学 2003 年】（A）冒泡排序（B）快速排列（C）希尔排序（D）堆排序41 基于比较方法的 n 个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是_。【南京理工大学 1996 年】（A）O(nlog
15、2n)（B） O(log2n)（C） O(n)（D）O(n 2)42 基于比较的排序算法时间复杂度最好的是 O(_)。【北京邮电大学 2007 年】（A）log 2n（B） n（C） nlog2n（D）n 243 在最好情况下，对 n 个记录的顺序表作_排序，其时间复杂度为 O(n)。【华中科技大学 2006 年】（A）归并排序（B）快速排序（C）堆排序（D）直接插入排序44 对各种内部排序方法来说，_。【华南理工大学 2006 年】（A）快速排序时间性能最佳（B）基数排序和归并排序是稳定的排序方法（C）快速排序是一种选择排序（D）堆排序所用的辅助空间比较大二、综合题45 冒泡排序算法是把大的
16、元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)请给出上浮和下沉过程交替的冒泡排序算法。【吉林大学 2001 年】46 有 50 个学生的记录(每个学生的记录包括学号和成绩)，组成记录数组，按成绩由高到低的次序输出(每行 10 个记录)。排序方法采用选择排序。【北京师范大学1999 年】46 有一种简单的排序算法，叫做计数排序(CountSorting)。这种排序算法对一个待排序的表(用数组表示) 进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键
17、码小，假设针对某一个记录，统计出的计数值为 c，那么，这个记录在新的有序表中的合适的存放位置即为 C。47 给出适用于计数排序的数据表定义。48 使用 C 语言编写实现计数排序的算法。49 对于有 n 个记录的表，关键码比较次数是多少?50 与简单选择排序相比较，这种方法是否更好?为什么? 【清华大学 2000 年】51 设有一个数组中存放了一个无序的关键序列 K1、K 2、K n。现要求将 Kn 放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过 n。【南京航空航天大学 1997 年】51 已知关键字序列(K 1，K 2，K 3，K n-1)是大根堆。52 试写
18、出一算法将(K 1，K 2，K 3，K n-1,Kn)调整为大根堆。53 利用 1)的算法写一个建大根堆的算法。【中科院软件所 1999 年】54 设有顺序放置的 n 个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。【上海大学 1999 年】计算机专业基础综合数据结构（排序）历年真题试卷汇编 1 答案与解析一、单项选择题1 【正确答案】 D【试题解析】 考查排序算法的稳定性。如果排序前后有相同关键字的记录的前后顺序不变，则称此排序
19、是稳定的。【知识模块】 排序2 【正确答案】 B【试题解析】 考查排序算法的稳定性及算法效率。归并排序和冒泡排序是稳定的，冒泡排序的平均时间复杂度为 O(n2)，归并排序的平均时间复杂度为 O(nlog2n)。【知识模块】 排序3 【正确答案】 B【试题解析】 考查稳定的排序算法有哪些。插入排序、冒泡排序、二路归并排序、基数排序是稳定的排序算法，选择排序、希尔排序、快速排序、堆排序属于不稳定排序。【知识模块】 排序4 【正确答案】 A【试题解析】 考查最好情况下直接插入排序比较次数。在最好的情况下，即初始序列有序列，则每次循环只需与前一个元素比较 1 次，且不需要移动，总的比较次数为 n1。【
20、知识模块】 排序5 【正确答案】 A【试题解析】 考查冒泡排序最差的情况。一般情况下冒泡排序最多进行 n1 次冒泡。若初始序列为逆序时，则需进行 n 一 1 次冒泡，并且需要交换次数最多。【知识模块】 排序6 【正确答案】 C【试题解析】 考查简单选择排序的比较次数和移动次数。简单选择排序过程共需选择 n1 次，第 i 趟选择具有最小元素所需的比较次数总是 ni 次，与初始排列无关，总共比较次数为 n(n 一 1)2 次。最多交换次数为 n 一 1 次。【知识模块】 排序7 【正确答案】 A【试题解析】 考查希尔排序的概念。希尔排序又称“缩小增量排序”，它也是一种属于插入排序类的方法。【知识模
21、块】 排序8 【正确答案】 B【试题解析】 考查希尔排序的过程。希尔排序将序列分成若干个组，只在组内进行交换。由观察可知，经过一趟后 9 和一 1 交换7 和 4 交换，可得增量为 4。【知识模块】 排序9 【正确答案】 A【试题解析】 考查希尔排序的性质。在希尔排序中，序列被分成了组，组内的排序并不能保证一定有元素被放置到其最终位置上。【知识模块】 排序10 【正确答案】 D【试题解析】 考查快速排序的概念。快速排序是基于分治的思想，将序列分为两个部分递归的实现排序。【知识模块】 排序11 【正确答案】 C【试题解析】 考查快速排序的过程。以第一个记录 46 为基准，先从后向前查找比它小的，
22、找到 40，交换两者位置，序列变为(40，79，56，38，46，84)，然后从前向后找比 46 大的，找到 79，交换位置，46 到了第二个位置，继续从后面找比46 小的元素，找到 38，交换。再次从前向后找比 46 大的元素，找到 56，交换。一趟划分完成。【知识模块】 排序12 【正确答案】 A【试题解析】 考查快速排序移动的过程。分别对 4 个选项进行一趟快速排序，可得 A 选项需要移动 7 个记录，次数最多。【知识模块】 排序13 【正确答案】 D【试题解析】 考查快速排序的最坏情况。每次分组时，分成的两个组大小平衡，快速排序处于最优状态。当待排序序列基本有序时，快速排序法性能最差。
23、【知识模块】 排序14 【正确答案】 C【试题解析】 考查快速排序的最坏情况。快速排序的最坏情况发生在两个区域分别包含 n1 个元素和 0 个元素时，这种最大程度的不对称性若发生在每一层递归上时，就得到时间复杂度为 O(n2)。【知识模块】 排序15 【正确答案】 D【试题解析】 考查快速排序的最坏情况。当待排序序列有序时，快速排序最慢。【知识模块】 排序16 【正确答案】 C【试题解析】 考查各类排序算法最坏情况下的时间复杂度。希尔排序时间复杂度无法进行详细比较，堆排序最坏情况和最好情况时间复杂度都为 0(n10g2n)，冒泡排序最坏时间复杂度为 O(n2)，基数排序最坏情况下的时间复杂度为
24、 O(d(n+r)。快速排序最坏情况下的时间复杂度为 O(n2)。【知识模块】 排序17 【正确答案】 C【试题解析】 考查堆的定义。堆有两种形式：大顶堆和小顶堆。在大顶堆中，树中任一非叶结点的关键字均不小于其左、右孩子(若存在)结点的关键字。显然，大顶堆中最大元素存放在根结点中，并且对其任一非根结点，它的值小于或等于其双亲结点。小顶堆的定义则刚好相反，其根结点是最小元素。【知识模块】 排序18 【正确答案】 C【试题解析】 考查建立堆的过程。本题中，建堆操作是将一个输入数组 ALn变为一个小顶堆的过程。从树中最后一个非叶结点(最后一个元素的父结点)开始，向前对各个元素进行调整。看每个结点值是
25、否小于其左、右子结点的值，若不是，将左、右子结点中较小值与之交换，并对交换后的子树结点继续向下调整。【知识模块】 排序19 【正确答案】 A【试题解析】 考查建堆的时间复杂度。建堆过程中，向下调整的时间与树高有关，为 O(h)。建堆过程中每次向下调整时，大部分结点的高度都较小。因此，可以证明在元素个数为 n 的序列上建堆，其时间复杂度为 O(n)。【知识模块】 排序20 【正确答案】 B【试题解析】 考查堆排序的空间复杂度。堆排序只需要一个辅助空间。【知识模块】 排序21 【正确答案】 C【试题解析】 考查堆排序最坏的时间复杂度。堆排序在最好、平均、晟坏情况下的时间复杂度都为 O(nlog2n
26、)。【知识模块】 排序22 【正确答案】 B【试题解析】 考查归并排序的趟数。归并排序将序列一分为二，将问题范围缩小到原来的一半递归地加以解决，最终归并的趟数应该为 O(log2n)。【知识模块】 排序23 【正确答案】 A【试题解析】 考查二路归并排序的空间复杂度。【知识模块】 排序24 【正确答案】 C【试题解析】 考查排序算法效率以及稳定性。各类排序算法的性能比较见表 6-1。【知识模块】 排序25 【正确答案】 C【试题解析】 考查原始序列状态对排序算法的影响。当待排序序列有序时，冒泡排序只需要比较 n1 次，而不需要移动元素：当待排序序列逆序时，需要进行n1 次冒泡。【知识模块】 排
27、序26 【正确答案】 A【试题解析】 考查各排序算法对于初始序列的敏感性。当待排序序列有序时，快速排序退化为冒泡排序。时间复杂度为 O(n2)。【知识模块】 排序27 【正确答案】 A【试题解析】 考查各类排序算法对初始序列的敏感性。当待排序序列基本有序时，直接插入排序只需要比较 n1 次，算法性能最好。【知识模块】 排序28 【正确答案】 A【试题解析】 考查比较次数和序列初始状态的关系。选择排序法整个排序过程共需选择 n 一 1 次，第 i 趟选择具有最小元素所需的比较次数总为 ni 次，总共比较次数为 n(n 一 1)2 次。【知识模块】 排序29 【正确答案】 C【试题解析】 考查直接
28、插入排序元素比较次数最少的条件。当初始序列有序时，直接插入排序的比较次数最少。观察可知，C 选项基本有序，所以比较次数最少。【知识模块】 排序30 【正确答案】 A【试题解析】 考查各类排序算法的过程。冒泡排序和选择排序两趟之后必然有两个最小值有序的排在序列头部，插入排序两趟之后前 3 个元素应该有序。【知识模块】 排序31 【正确答案】 A【试题解析】 考查各类排序算法的过程。通过观察发现每次排序都是从未排序序列中选择一个最小的元素放到其最终的位置。正是选择排序的特征。【知识模块】 排序32 【正确答案】 D【试题解析】 考查各类排序的过程。堆排序、冒泡排序、快速排序每一趟排序后总有一个元素
29、是在其最终位置上。插入排序有可能出现最小的元素在最后面，最后一个元素插入到前面之后，各个元素才各就各位。【知识模块】 排序33 【正确答案】 D【试题解析】 考查各种排序方法的过程。观察序列变化，发现第一趟排序序列位置变化很大，所以不可能是选择排序和归并排序。又发现第二趟排序 15 和 20 交换了位置，所以不可能是希尔排序。所采用的排序算法正是快速排序。【知识模块】 排序34 【正确答案】 A【试题解析】 考查各类排序算法的过程。当初始序列基本有序时，插入排序比较次数最少(13 次) ，冒泡排序(17 次) 。【知识模块】 排序35 【正确答案】 C【试题解析】 考查排序算法能否将元素放在最
30、终位置。选择排序、冒泡排序、堆排序在一趟结束后都可以选出一个元素放在最终位置上。归并排序是递归进行的，某一趟排序只是在各个局部进行排序，不一定能选出一个元素将其放在最终位置上。【知识模块】 排序36 【正确答案】 D【试题解析】 考查各类排序的空间复杂度。从空间复杂度来讲，希尔排序、堆排序、选择排序都为 O(1)，只有归并排序为 O(n)。【知识模块】 排序37 【正确答案】 A【试题解析】 考查各类排序算法所需辅助空间。快速排序是递归的，需要一个栈来存放每一层递归调用的必要信息，其最大容量应与递归调用的深度一致，最好情况下为 O(log2n)；最坏情况下，因为要进行 n 一 1 次递归调用，
31、所以，栈的深度为O(n)；希尔排序、堆排序空间复杂度都为 O(1)。【知识模块】 排序38 【正确答案】 C【试题解析】 B。考查各种排序当序列有序时的效率。当序列已经为递增时，插入排序只需要比较 n 一 1 次，不需移动，而快速排序此时需要比较 n(n1)次。堆排序、归并排序不受初始序列影响，算法时间复杂度为 O(nlog2n)。【知识模块】 排序39 【正确答案】 D【试题解析】 考查平均性能最好的排序算法。虽然快速排序算法在初始序列有序时性能变差，但是就平均性能而言，快速排序仍然是最好的排序算法。【知识模块】 排序40 【正确答案】 D【试题解析】 考查灵活运用各种排序算法的能力。希尔排
32、序和快速排序要等排序全部完成之后才能确定最小的 10 个元素，冒泡排序需要从头到尾冒 10 趟才能得到10 个最小的元素，而堆排序只需要调整 10 次小根堆，调整时间与树高成正比。显然堆排序所需时间更短。【知识模块】 排序41 【正确答案】 A【试题解析】 考查基于比较的排序算法的时间复杂度。最好下界即是最低的时间复杂度，归并排序在最坏情况下时间复杂度为 O(nlog2n)。【知识模块】 排序42 【正确答案】 C【试题解析】 考查基于比较的排序算法的时间复杂度。此处应按平均复杂度来比较。【知识模块】 排序43 【正确答案】 D【试题解析】 考查最好情况下时间复杂度为 O(n)的算法。归并排序
33、最好和最坏一样都为 O(nlog2n)，快速排序最好情况下为 O(nlog2n)，堆排序最好、最坏都为O(nlog2n)，直接插入排序最好情况下为 O(n)。【知识模块】 排序44 【正确答案】 B【试题解析】 考查各种排序算法的性质。快速排序并不是所有情况下时间性能都最佳。基数排序和归并排序是稳定的，快速排序是一种比较排序，堆排序只需要一个辅助空间。【知识模块】 排序二、综合题45 【正确答案】 算法的基本设计思想：冒泡排序的方法，先从上向下起泡，然后从下向上起泡，设置变量标记冒泡的上下界。算法的代码：VOid BubbleSOrt2(int a，int n)相邻两趟向相反方向起泡的冒泡排序
34、算法int change=1；int 10W=0；int high=n 一 1； 冒泡的上下界while(10wai+1)int temp=ai；ai=ai+1;ai+1=temp；change=1； 有交换，修改标志 changehigh 一一； 修改上界for(i=high; ilow，i-) 从下向上起泡if(aiRkScore)k=j ;if(i !=k)swap(Ri，Rk) ； 与第 i 个记录交换 forfor(i=1; i=x)j 一一；if(i=1；i=i2)if(ROkeyRikey)Rj=Ri；j=i；elsebreak；Rj=RO； sift【知识模块】 排序53 【正确答案】 算法的基本设计思想：从两个元素开始建堆，每加入一个元素，调整堆，最终将整个序列建立成大根堆。算法的代码：void HeapBuilder(RecType R，int n) for(int i=2； i=j) 左侧只有红色砾石，交换 rk和 ritemp=rk；rk=ri;ri=temp;i+；else 左侧已有红色和白色砾石，先交换白色砾石到位temp=rj；rj=ri;ri=temp;j+;temp=rk; 再交换 rk和 ri，使红色砾石入位rk=ri;ri=temp；i+；if(rkkey=2)if(i=j)temp=rk； 左侧已有白色砾石，交换 rk和 rj
