1、第 1 页 第 2 页 uu学习的意义：学习的意义： 早期的计算机约有一半的时间花在排序操作上，虽然随着计早期的计算机约有一半的时间花在排序操作上，虽然随着计 算机速度的提高，排序操作不再像早期那样占用计算机过多的算机速度的提高，排序操作不再像早期那样占用计算机过多的 时间，但它仍然是信息处理中最常用，也是最重要的运算之一时间，但它仍然是信息处理中最常用，也是最重要的运算之一 。 实际上，在计算机科学中，排序仍然是组织数据最基本的运实际上，在计算机科学中，排序仍然是组织数据最基本的运 算，许多程序和软件均以它作为一个中间步骤。因此，人们设算，许多程序和软件均以它作为一个中间步骤。因此，人们设
2、计了大量的排序算法以满足不同的需求。计了大量的排序算法以满足不同的需求。 计算机图灵奖获得者，著名计算机科学家计算机图灵奖获得者，著名计算机科学家D.E.KnuthD.E.Knuth在他的在他的 巨著巨著Art of Computer ProgrammingArt of Computer Programming中列举分析了中列举分析了2525中经典中经典 排序方法，并且指出，这只是现有方法中的排序方法，并且指出，这只是现有方法中的“一小部分一小部分”。 第 3 页 3.1 3.1 排序的基本概念排序的基本概念 3.2 3.2 简单的排序方法简单的排序方法 3.2.1 3.2.1 插入排序插入排
3、序 3.2.2 3.2.2 起泡排序起泡排序 3.3 3.3 先进的排序方法先进的排序方法 3 3.3.1 .3.1 快速排序快速排序 3 3.3.2 .3.2 归并排序归并排序 3 3.3.3 .3.3 堆排序堆排序 3.4 3.4 基数排序基数排序 3.4 3.4 各种排序方法的综合比较各种排序方法的综合比较 uu主要内容：主要内容： 第 4 页 在很多情况下，相对于无序表而言，使用有序表可以提在很多情况下，相对于无序表而言，使用有序表可以提 高算法效率，因为有序表可以充分利用其有序性采用一些效高算法效率，因为有序表可以充分利用其有序性采用一些效 率较高的算法，例如，在进行数据元素的查找时
4、，采用有序率较高的算法，例如，在进行数据元素的查找时，采用有序 表比无序表效率要高很多。表比无序表效率要高很多。 如何得到有序表？我们可以在构造顺序表的时候依顺序表如何得到有序表？我们可以在构造顺序表的时候依顺序表 的有序性进行数据元素的插入，从而求得有序表。的有序性进行数据元素的插入，从而求得有序表。 更多的时候，我们需要对一个无序的顺序表进行更多的时候，我们需要对一个无序的顺序表进行“排序排序” ，将它转化为，将它转化为“有序有序”的顺序表。的顺序表。 3. 1 3. 1 排序的基本概念排序的基本概念 第 5 页 排序排序 是按关键字的非递减或非递增顺序对一组记录重新进行整队是按关键字的非
5、递减或非递增顺序对一组记录重新进行整队 ( (或或) )排列的操作排列的操作. . 姓名姓名 电话号码电话号码 蔡颖蔡颖 63214444 63214444 陈红陈红 63217777 63217777 刘建平刘建平 63216666 63216666 王小林王小林 63218888 63218888 张力张力 63215555 63215555 . . 3. 1 3. 1 排序的基本概念排序的基本概念 例例1 1、高考考生信息管理系统提供了将考生按总分排序、按单科排序的功能高考考生信息管理系统提供了将考生按总分排序、按单科排序的功能 ； 例例2 2、数学中的数列（、数学中的数列（1111，1
6、313，1515，1717，1919，2121） 例例3 3、英文字母表（、英文字母表（A, B, C, D, EA, B, C, D, E Z Z ）。）。 例例4 4、某单位的电话号码簿。、某单位的电话号码簿。 排序的定义排序的定义 第 6 页 排序的形式化描述排序的形式化描述 假设含有假设含有n n个记录的序列为：个记录的序列为： r r 1 1,r ,r2 2,r ,r3 3 ,rn,rn 它们的关键字相应为：它们的关键字相应为： k k 1 1 ,k,k 2 2 ,k,k 3 3 ,k,k n n 对记录序列进行排序就是确定序号对记录序列进行排序就是确定序号1,2,3,1,2,3,n
7、 n的一种排列：的一种排列： p p1 1 ,p,p 2 2 ,p,p 3 3 ,p,p n n 使其相应的关键字满足使其相应的关键字满足非递减或非递增的关系非递减或非递增的关系 k k p1p1 k kp2 p2 k kp3 p3。 k kpn pn 也就是使记录序列重新排列成为一个按关键字有序的序列也就是使记录序列重新排列成为一个按关键字有序的序列 第 7 页 排序分类排序分类 什么叫内部排序？什么叫外部排序？什么叫内部排序？什么叫外部排序？ 若整个排序过程若整个排序过程不需要访问外存不需要访问外存便能完成，则称此便能完成，则称此 类排序问题类排序问题为内部排序为内部排序；称为内部排序；称
8、为内部排序； 反之，若参加排序的记录数量很大，整个序列的排反之，若参加排序的记录数量很大，整个序列的排 序过程序过程不可能在内存中完成不可能在内存中完成，则称此类排序问题为外部，则称此类排序问题为外部 排序。排序。 注：注：外部排序时，要将数据分批调入内存来排序，中间外部排序时，要将数据分批调入内存来排序，中间 结果还要及时放入外存，显然外部排序要复杂得多。结果还要及时放入外存，显然外部排序要复杂得多。 第 8 页 内部排序的算法有哪些？内部排序的算法有哪些？ 按排序的规则不同，可分为按排序的规则不同，可分为5 5类：类： 插入排序插入排序 交换排序（重点是快速排序）交换排序（重点是快速排序）
9、 选择排序选择排序 归并排序归并排序 基数排序基数排序 d d关键字的位数关键字的位数( (长度长度) ) 按排序算法的时间复杂度不同，可分为按排序算法的时间复杂度不同，可分为3 3类：类： 简单的排序算法：时间效率低，简单的排序算法：时间效率低，O(nO(n 2 2 ) ) 先进的排序算法先进的排序算法: : 时间效率高，时间效率高，O( nlogO( nlog 2 2 n )n ) 基数排序算算法：时间效率高，基数排序算算法：时间效率高，O( dn)O( dn) 第 9 页 按稳定性分类：按稳定性分类： 在待排记录序列中，任何两个关键字相同的记录，用某种排序方法在待排记录序列中，任何两个关
10、键字相同的记录，用某种排序方法 排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的 。 例例 设设 4949,38,65,97,76,13,27,38,65,97,76,13,27,4949 是待排序列是待排序列 排序后排序后:13,27,38,:13,27,38,49,49,4949,65,76,97 ,65,76,97 稳定稳定 排序后排序后:13,27,38,:13,27,38,4949,49,49,65,76,9765,76,97不稳定不稳定 稳性排序的应用：稳性排序的应用： 例例 股票交易系统股票交易系统 考虑
11、一种股票交易考虑一种股票交易( (清华紫光清华紫光) )） 1 1）顾客输入：股东帐号、股票代码、申购价格、数量，股票交易系统将用）顾客输入：股东帐号、股票代码、申购价格、数量，股票交易系统将用 户申购请求插入申购队列队尾户申购请求插入申购队列队尾； 2 2）股票股票交易系统按如下原则交易：交易系统按如下原则交易： A A）申购价高者先成交申购价高者先成交 B B）申购价相同者按申购时间先后顺序成交申购价相同者按申购时间先后顺序成交 第 10 页 如何实现股票交易系统如何实现股票交易系统 ？ 申购队列：用线性表表示申购队列：用线性表表示 交易前：将申购队列按申购价排序，显然为满足原则交易交易前
12、：将申购队列按申购价排序，显然为满足原则交易 B B），），要求排序方法是稳定的要求排序方法是稳定的 申购队列申购队列（09,10)09,10),(06,10,(06,10. .5),(033,95),(033,9. .8),8),(051,10)(051,10) ) 排序后：排序后：(06,10.5),(06,10.5),(09,10)(09,10), ,(051,10)(051,10),(033,9.8),(033,9.8) 第 11 页 待排序记录在内存中怎样存储和处理？待排序记录在内存中怎样存储和处理？ 顺序顺序排序排序排序时直接移动记录；排序时直接移动记录； 链表链表排序排序排序时只
13、移动指针；排序时只移动指针； 地址地址排序排序排序时先移动地址，最后再移动记录。排序时先移动地址，最后再移动记录。 注：注：地址排序地址排序中可以增设一维数组来专门存放记录的地址。中可以增设一维数组来专门存放记录的地址。 第 12 页 内部排序的方法内部排序的方法 内部排序的过程是一个逐步扩大内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。记录的有序序列长度的过程。 经过一趟排序经过一趟排序 有序序列区有序序列区无无 序序 序序 列列 区区 有序序列区有序序列区无无 序序 序序 列列 区区 第 13 页 选择排序选择排序 从记录的无序子序列中从记录的无序子序列中“ “选择选择” ”关键
14、字最小或最大的记录，并将关键字最小或最大的记录，并将 它加入到有序子序列中，以此方法增加记录的有序子序列的长度。它加入到有序子序列中，以此方法增加记录的有序子序列的长度。 【算法算法3.1 3.1 】一趟选择排序的算法如下：一趟选择排序的算法如下： void SelectPass( SqList k for ( k=i+1; k=L.length; k+ ) L.length; k+ ) if ( if ( L.rk.key L.rj.keyL.rk.key L.rj.key ) j = k ) j = k ； / / 暂不进行记录交换，只记录位置暂不进行记录交换，只记录位置 if ( i i
15、f ( i !=!= j ) j ) W=L.rj W=L.rj；L.rj =L.riL.rj =L.ri；L.ri = WL.ri = W； / / 最后互换记录最后互换记录Rj Rj 和和RiRi / SelectPass/ SelectPass 第 14 页 【算法算法3.2 3.2 】 void SelectSort (SqList iL.length; +i) for (i=1; iL.length; +i) / / 选择第选择第i i小的记录，并交换到位小的记录，并交换到位 j = ij = i； for ( k=i+1; k=L.length; k+ ) for ( k=i+1;
16、 k=L.length; k+ ) / / 在在L.ri.L.lengthL.ri.L.length中选择中选择keykey最小的记录最小的记录 if ( L.rk.key L.rj.key ) j =k if ( L.rk.key L.rj.key ) j =k ； if ( i!=j ) W=L.rj if ( i!=j ) W=L.rj；L.rj =L.riL.rj =L.ri；L.ri = WL.ri = W； / / 与第与第i i个记录交换个记录交换 / / SelectSortSelectSort 整个选择排序的过程是一趟选择排序过程的多次重复，整个选择排序的过程是一趟选择排序过
17、程的多次重复， 融合融合S SelectPasselectPass。 第 15 页 初试关键字：初试关键字： 49 49 1 1 38 65 49 38 65 49 2 2 76 13 27 52 76 13 27 52 i=1 i=1 （1313） 38 65 49 38 65 49 2 2 76 76 49491 1 27 52 27 52 i=2 i=2 （1313 27 27）65 4965 49 2 2 76 49 76 491 1 38 38 52 52 i=3 i=3 （13 2713 27 3838） 49 49 2 2 76 49 76 491 1 65 65 52 52 i
18、=4 i=4 （13 27 3813 27 38 4949 2 2 ）76 4976 491 1 65 52 65 52 i=5 i=5 （13 27 38 4913 27 38 492 2 49 49 1 1 ）7676 65 52 65 52 i=6 i=6 （13 27 38 4913 27 38 492 2 49 491 1 52 52）65 65 7676 i=7 i=7 （13 27 38 4913 27 38 492 2 49 491 1 52 52 65 65 ）7676 【例例3 3-1 -1 】对下面一组关键字：对下面一组关键字： 4949 1 1 38 65 49 38
19、65 49 2 2 76 13 27 52 76 13 27 52 进行选择排序，每趟排序之后的状况如下：进行选择排序，每趟排序之后的状况如下： 第 16 页 选择排序时间性能分析选择排序时间性能分析 对对 n n 个记录进行简单选择排序，所需进行的个记录进行简单选择排序，所需进行的 关键字间的比较次数关键字间的比较次数 总计为总计为: : 移动记录的次数，最小值为移动记录的次数，最小值为 0, 0, 最大值为最大值为3(3(n-n- 1) 1) 第 17 页 简单排序算法，除前面讨论的选择排序外，常用的还简单排序算法，除前面讨论的选择排序外，常用的还 有插入排序和起泡排序。有插入排序和起泡排
20、序。 3.2 3.2 简单排序方法简单排序方法 插入排序的基本思想：插入排序的基本思想： 每步将一个待排序的对象，按其关键码大小，每步将一个待排序的对象，按其关键码大小， 插入到前面插入到前面已经排好序的一组对象已经排好序的一组对象的的适当位置适当位置上，直上，直 到对象全部插入为止。到对象全部插入为止。 简而言之，边插入边排序简而言之，边插入边排序，保证子序列中随时都是排好序的。保证子序列中随时都是排好序的。 第 18 页 利用利用 “ “顺序查找顺序查找” ”实现实现“ “在在R1.i-1R1.i-1中查找中查找RiRi的插入位置的插入位置” ” 直接插入排序直接插入排序 算法实现：算法实
21、现： 当插入第当插入第i (i i (i 1) 1) 个对象时个对象时, , 前面的前面的r0, r1, , r0, r1, , riri- -11已经排好序。这时已经排好序。这时, , 用用riri的排序码与的排序码与riri- -1, ri1, ri- - 2, 2, 的排序码顺序进行比较的排序码顺序进行比较, , 找到插入位置即将找到插入位置即将riri插插 入入, , 原来位置上的对象向后顺移。原来位置上的对象向后顺移。 第 19 页 有序序列有序序列R1.i-1R1.i-1 RiRi 无序序列无序序列 Ri.nRi.n 有序序列有序序列R1.iR1.i无序序列无序序列 Ri+1.nR
22、i+1.n 一趟直接插入排序的基本思想：一趟直接插入排序的基本思想： 第 20 页 【算法算法3.3 3.3 】 void InsertPass( SqList L.r0 = L.ri; / / 复制为哨兵复制为哨兵 for ( j=i-1; L.r0.key L.rj.key; -j )for ( j=i-1; L.r0.key L.rj.key; -j ) L.rj+1 = L.rj; L.rj+1 = L.rj; / / 记录后移记录后移 L.rj+1 = L.r0; L.rj+1 = L.r0; / / 插入到正确位置插入到正确位置 / / InsertPassInsertPass 注
23、意：注意：“ “哨兵哨兵” ”的作用的作用 一趟插入排序一趟插入排序 第 21 页 从从Ri-1Ri-1起向前进行顺序查找，起向前进行顺序查找，监视哨设置在监视哨设置在R0R0； R0 = Ri; / R0 = Ri; / 设置设置“ “哨兵哨兵” ” 循环结束表明循环结束表明RiRi的插入位置为的插入位置为 j +1j +1 R0R0 j j RiRi for (j=i-1; R0.keyRj.key; -j); / for (j=i-1; R0.keyRj.key; -j); / 从后往前找从后往前找 插入位置插入位置 第 22 页 对于在查找过程中找到的那些关键字不小于对于在查找过程中找
24、到的那些关键字不小于Ri.keyRi.key的记录的记录 ，并在查找的同时实现记录向后移动；，并在查找的同时实现记录向后移动； for (j=i-1; R0.keyRj.key; -j); for (j=i-1; R0.keyRj.key; -j); Rj+1 = RjRj+1 = Rj R0R0 j j RiRi j= i-1j= i-1 上述循环结束后可以直接进行上述循环结束后可以直接进行“ “插入插入” ” 插入位置插入位置 第 23 页 例例2 2：关键字序列关键字序列T= T= （2121，2525，4949，25*25*，1616，0808），）， 请写出直接插入排序的具体实现过程
25、。请写出直接插入排序的具体实现过程。* *表示后一个表示后一个2525 i=1i=1 2121 2525 4949 25*25* 1616 0808 0 1 2 3 4 5 60 1 2 3 4 5 6 暂暂 存存 2121 i=2i=2i=3i=3i=5i=5i=4i=4i=6i=6 252525252525 494949494949 25*25*25*25* 4949 1616 161625*25* 08080808 4949 解：解：假设该序列已存入一维数组假设该序列已存入一维数组V7V7中，将中，将V0V0作为缓冲或暂存作为缓冲或暂存 单元（单元（TempTemp）。则程序执行过程为：
26、）。则程序执行过程为： 2121 2525 4949 25*25* 2121 初态：初态： 1616 4949 25*25* 2525 21211616 0808 完成完成! ! 时间效率：时间效率：O(nO(n 2 2 ) )因为在最坏情况下，所有元素的比较次数总和为（因为在最坏情况下，所有元素的比较次数总和为（ 0 01 1n-1)O(nn-1)O(n 2 2 ) )。其他情况下还要加上移动元素的次数。其他情况下还要加上移动元素的次数 。 空间效率：空间效率：O(1)O(1)因为仅占用因为仅占用1 1个缓冲单元个缓冲单元 算法的稳定性：稳定算法的稳定性：稳定因为因为25*25*排序后仍然在
27、排序后仍然在2525的后面。的后面。 第 24 页 【算法算法3.4 3.4 】 void InsertSort ( SqList i=L.length; +i ) for ( i=2; i=L.length; +i ) / / 对顺序表对顺序表L L作插入排序作插入排序 if ( L.ri.key L.ri-1.key ) if ( L.ri.key L.ri-1.key ) / / 时，才需将时，才需将L.riL.ri插入有序子表插入有序子表 L.r0 = L.ri; L.r0 = L.ri; / / 复制为哨兵复制为哨兵 for ( j=i-1; L.r0.key L.rj.key; -
28、j )for ( j=i-1; L.r0.key L.rj.key; -j ) L.rj+1 = L.rj; L.rj+1 = L.rj; / / 记录后移记录后移 L.rj+1 = L.r0; L.rj+1 = L.r0; / / 插入到正确位置插入到正确位置 / / if if / InsertSort/ InsertSort 整个插入排序需要进行整个插入排序需要进行n-1n-1趟趟“ “插入插入” ”。 因为只含有一个关键字的序列必定是有序序列，因此，插入应该从因为只含有一个关键字的序列必定是有序序列，因此，插入应该从i=1i=1开始进开始进 行，此外，若第行，此外，若第i i个记录的关
29、键字不小于第个记录的关键字不小于第i-1i-1个关键字，插入也就不需要进行了。个关键字，插入也就不需要进行了。 第 25 页 4949 38 65 97 76 13 27 38 65 97 76 13 27 4949 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 初始时，有序子表中只有一个元素初始时，有序子表中只有一个元素 待排序记录集合：待排序记录集合： 3838 38 4938 49 65 97 76 13 27 65 97 76 13 27 4949 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 i=2i=2 i=3i=
30、3 i=4i=4 65 65 38 49 6538 49 65 97 76 13 27 97 76 13 27 4949 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 97 97 38 49 65 9738 49 65 97 76 13 27 76 13 27 4949 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 第 26 页 38 49 65 9738 49 65 97 76 13 27 76 13 27 4949 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 L.r0.key 1) /
31、i1 / i1 表明上一趟曾进行过记录的交换表明上一趟曾进行过记录的交换 lastExchangeIndex = 1;lastExchangeIndex = 1; for (j = 1; j i; for (j = 1; j i; j+j+) ) if (L.rj+1.key L.rj.key) if (L.rj+1.key L.rj.key) W=L.rj W=L.rj；L.rj =L.rj+1L.rj =L.rj+1；L.rj+1 = WL.rj+1 = W； / / 互换记录互换记录 lastExchangeIndex = lastExchangeIndex = j j; ; /if/i
32、f /for/for i = lastExchangeIndexi = lastExchangeIndex; ; / / 一趟排序中无序序列中最后一个记录的位置一趟排序中无序序列中最后一个记录的位置 / / whilewhile / BubbleSort/ BubbleSort 空间复杂度空间复杂度O(1)O(1) 第 33 页 注意注意: : 2. 2. 一般情况下，每经过一趟一般情况下，每经过一趟“起泡起泡”，“i i 减一减一”，但并不是，但并不是 每趟都如此。每趟都如此。 例如例如: : i=7i=7 for (j = 1; j i; j+) if (Rj+1.key Rj.key)
33、for (j = 1; j i; j+) if (Rj+1.key Rj.key) 1. 1. 起泡排序的结束条件为，起泡排序的结束条件为， 最后一趟没有进行最后一趟没有进行“ “交换记录交换记录” ”。 2 2 3 3 1 1 5 5 7 7 8 8 9 9 i=6i=6i=2i=2 3 3 1 1 1 1 3 3 第 34 页 时间分析时间分析: : 最好最好的情况（关键字在记录序列中顺序有序）：的情况（关键字在记录序列中顺序有序）： 只需进行一趟起泡只需进行一趟起泡 “ “比较比较” ”的次数：的次数： 最坏最坏的情况（关键字在记录序列中逆序有序）：的情况（关键字在记录序列中逆序有序）：
34、 需进行需进行n-1n-1趟起泡趟起泡 “ “比较比较” ”的次数：的次数： 0 0 “ “移动移动” ”的次数：的次数： “ “移动移动” ”的次数：的次数： n-1n-1 第 35 页 3.3 3.3 先进的排序方法先进的排序方法 3.3.1 3.3.1 快速排序快速排序( (quick sort)quick sort) 快速排序是从起泡排序改进而得的一种快速排序是从起泡排序改进而得的一种“ “交换交换” ”排序方法，排序方法， 它的基本思想是通过一趟排序将将记录分割成相邻的两个区域，它的基本思想是通过一趟排序将将记录分割成相邻的两个区域， 其中一个区域中记录的关键字均比另一区域中记录关键
35、字小（区其中一个区域中记录的关键字均比另一区域中记录关键字小（区 域内不一定有序），则可分别对这两个区域的记录进行再排序，域内不一定有序），则可分别对这两个区域的记录进行再排序， 以达到整个序列有序。以达到整个序列有序。 目标：找一个记录，以它的关键字作为目标：找一个记录，以它的关键字作为“ “枢轴枢轴” ”，凡其关键字小于枢轴的记录，凡其关键字小于枢轴的记录 均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致 使一趟排序之后，记录的无序序列使一趟排序之后，记录的无序序列Rs.tRs.t将分割成两部分：将
36、分割成两部分：Rs.i-1Rs.i-1和和Ri+1.t, Ri+1.t, 且且 Rj.key Ri.key Rj.keyRj.key Ri.key Rj.key (sji-1) (sji-1) 枢轴枢轴 ( (i+1jt)i+1jt) 第 36 页 基本步骤：基本步骤： 为简洁起见，对待排记录仍只写出其关键字序列为简洁起见，对待排记录仍只写出其关键字序列 1 1、( (一趟快速排序）设被指定的关键字为待排序列的第一个关键字一趟快速排序）设被指定的关键字为待排序列的第一个关键字k k ，i i指向指向 待排序列的的第一个关键字；待排序列的的第一个关键字； j j指向最后一个关键字；指向最后一个关
37、键字； 若若i i j j 循环：循环： 1 1）从后向前将关键字与）从后向前将关键字与k k比较，直至遇到小于比较，直至遇到小于k k的的关键字关键字 k k ，k k 前移；前移； 2 2）从前向后将关键字与从前向后将关键字与k k比较，直至遇到大于比较，直至遇到大于k k的的关键字关键字k k ，k k 后移；后移； （一趟快速排序后，（一趟快速排序后，“ “小小” ”记录被移至记录被移至k k 前，前，“ “大大” ”的记录被移至的记录被移至k k 后后 2 2、继续对继续对k k前后两部分关键字进行快速排序，直至排序范围为前后两部分关键字进行快速排序，直至排序范围为1;1; 第 37
38、 页 27 27 38 65 97 76 13 38 65 97 76 13 2727 4949 i i i i 27 38 65 27 38 65 97 76 13 97 76 13 65 65 4949 j j j j 27 38 13 27 38 13 4949 76 76 97 97 65 65 4949 j j j j i i 被指定的被指定的 关键字关键字 从后向前，将关从后向前，将关 键字与键字与4949比较，比较， 直至遇到小于直至遇到小于4949 的关键字，前移的关键字，前移 从后向前，将关从后向前，将关 键字与键字与4949比较，比较， 直至遇到小于直至遇到小于4949 的关键字，前移的关键字，前移 从前向后，将关从前向后，将关 键字与键字与4949比较，比较， 直至遇到大于直至遇到大于4949 的关键字，后移的关键字，后移 从前向后，将关从前
