汽车加冷媒视频:9.5.1 直接插入排序算法

来源：百度文库 编辑：中财网 时间：2024/05/07 12:25:43

9.5 直接插入排序

扑克牌是我们几乎每个人都可能玩过的游戏。最基本的扑克玩法都是一边摸牌，一边理牌。假如我们拿到了这样一手牌，如图9‐5‐1所示。啊，似乎是同花顺呀，别急，我们得理一理顺序才知道是否是真的同花顺。请问，如果是你，应该如何理牌呢？

图9-5-1

应该说，哪怕你是第一次玩扑克牌，只要认识这些数字，理牌的方法都是不用教的。将3和4移动到5的左侧，再将2移动到最左侧，顺序就算是理好了。这里，我们的理牌方法，就是直接插入排序法。

9.5.1 直接插入排序算法

直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

顾名思义，从名称上也可以知道它是一种插入排序的方法。我们来看直接插入排序法的代码。

  1. /* 对顺序表L作直接插入排序 */  
  2. 1 void InsertSort（SqList *L）  
  3. 2 {  
  4. 3 int i,j;  
  5. 4 for（i=2;i<=L->length;i++）  
  6. 5 {  
  7. 6 if （L->r[i]r[i-1]） /* 需将L->r[i]插入有序子表 */  
  8. 7 {  
  9. 8 L->r[0]=L->r[i]; /* 设置哨兵 */  
  10. 9 for（j=i-1;L->r[j]>L->r[0];j--）  
  11. 10 L->r[j+1]=L->r[j]; /* 记录后移 */  
  12. 11 L->r[j+1]=L->r[0]; /* 插入到正确位置 */  
  13. 12 }  
  14. 13 }  
  15. 14 }

1．程序开始运行，此时我们传入的SqList参数的值为length=6,r[6]= {0,5,3,4,6,2}，其中r[0]=0将用于后面起到哨兵的作用。

2．第4～13行就是排序的主循环。i从2开始的意思是我们假设r[1]=5已经放好位置，后面的牌其实就是插入到它的左侧还是右侧的问题。

3．第6行，此时i=2，L.r[i]=3比L.r[i‐1]=5要小，因此执行第8～11行的操作。第8行，我们将L.r[0]赋值为L.r[i]=3的目的是为了起到第9～10行的循环终止的判断依据。如图9‐5‐2所示。图中下方的虚线箭头，就是第10行，L.r[j‐1]=L.r[j]的过程，将5右移一位。

图9-5-24．此时，第10行就是在移动完成后，空出了空位，然后第11 行L.r[j+1]=L.r[0]，将哨兵的3赋值给j=0时的L.r[j+1]，也就是说，将扑克牌3放置到L.r[1]的位置。如图9‐5‐3所示。
图9-5-35．继续循环，第6行，因为此时i=3，L.r[i]=4比L.r[i‐1]=5要小，因此执行第8～11行的操作，将5再右移一位，将4放置到当前5所在位置，如图9‐5‐4所示。
（点击查看大图）图9-5-46．再次循环，此时i=4。因为L.r[i]=6比L.r[i‐1]=5要大，于是第8～11行代码不执行，此时前三张牌的位置没有变化。如图9‐5‐5所示
（点击查看大图）图9-5-57．再次循环，此时i=5，因为L.r[i]=2比L.r[i‐1]=6要小，因此执行第8～11行的操作。由于6、5、4、3都比2小，它们都将右移一位，将2放置到当前3所在位置。如图9‐5‐6所示。此时我们的排序也就完成了。
（点击查看大图）图9-5-6
直接插入排序 如何直接插入排序 直接插入排序 一、题目：三种典型排序算法及其比较（直接法、插入法、shell排序比较） 给出直接插入排序的C++程序 设计CAI实现动态演示插入排序算法 谁会对C++中的排序算法,比如冒泡排序,插入排序,选择排序,快速排序等的MPI并行实现代码? 结构体排序算法 asp排序算法 什么是起泡排序算法?? 急求一排序算法 合并排序算法 vb选择排序算法 内部排序算法比较 内部排序算法比较 谁知道空间复杂度为o(1)的归并排序算法？ C算法.第1卷,基础、数据结构、排序和搜索 C算法.第1卷,基础、数据结构、排序和搜索 插入法排序 整数排序算法的问题？ 堆排序的具体算法 快速排序的循环算法 求几种排序法的算法 全排序的算法(PASCAL)