当前位置：文档之家 › 数据结构c课件 第九章 内部排序

数据结构c课件 第九章 内部排序

  • 格式：ppt
  • 大小：443.50 KB
  • 文档页数：67

下载文档原格式

  / 67

合集下载

数据结构——第9章内排序(C#)

数据结构——第9章内排序(C#)
n 1
总的平均比较和移动次数约为
n 1 i i (n 1)( n 4) O( n2) ( 2 2 2) (i 2) 2 i 1 i 1 n 1
9.2.2 折半插入排序
查找采用折半查找方法，称为二分插入排序或折半插入排序。
public void BinInsertSort() //对R[0..n-1]按递增有序进行折半插入排序 { int i,j,low,high,mid;RecType tmp; for (i=1;i<length;i++) { tmp=R[i]; //将R[i]保存到tmp中 low=0;high=i-1; while (low<=high) //在R[low..high]中折半查找有序插入的位置 { mid=(low+high)/2; //取中间位置 if (tmp.key<R[mid].key) high=mid-1; //插入点在左半区 else low=mid+1; //插入点在右半区 } for (j=i-1;j>=high+1;j--) //元素后移 R[j+1]=R[j]; R[high+1]=tmp; //插入原来的R[i] } }
关键字最大位数用于基数排序radixnode用于基数排序的单链表头指针int关键字的位数用于基数排序publicint关键字的进制用于基数排序publicintersortclass构造函数用于顺序表等初始化rnewrectypemaxsize
第9章 内排序
9.1 排序的基本概念
所谓排序，是要整理表中的记录，使之按关键字递增 （或递减）有序排列。其确切定义如下： 输 入 ： n 个 记 录 ,R0,R1,…,Rn-1, 其 相 应 的 关 键 字 分 别 为 k0,k1,…,kn-1。 输 出 ： Ri,0,Ri,1,…,Ri,n-1, 使 得 ki,0≤ki,1≤…≤ki,n-1 ( 或

数据结构第九章内部排序

数据结构第九章内部排序

举例
比较 移动 次数 次数
012345678
五趟
38 49 65 76 90 13 27 49 12345次 1234567次
1、直接插入排序法
方法 ⑵依次逐个将Ri（i=2,3,…,n）插入已有的按关键字值有序 的序列，并使插入完成后的序列仍按关键字值有序。
举例
比较 移动 次数 次数
012345678
值 间的比较，
(3+4+…+n+1)=1()n/-2 1)(n+4)/2
次元素的移动。
1、直接插入排序法
算法时间复杂度在最好时为O ，最坏时为O( ，并需可要见一素直个接元插入的排辅序助法存在储空待间排(。数n)据元素序列已基n本2)有 少或待排数据元素个数较 时效率较高。 序
1、直接插入排序法
举例
比较 移动 次数 次数
012345678
二趟
38 49 65 97 76 13 27 49 1次
1、直接插入排序法
方法 ⑵依次逐个将Ri（i=2,3,…,n）插入已有的按关键字值有序 的序列，并使插入完成后的序列仍按关键字值有序。
举例
比较 移动 次数 次数
012345678
三趟
38 49 65 97 76 13 27 49 1次
数据结构第九章内部排序
一、基本术语
排序 将n个性质相同的数据元素按关键字值从小到大或从大
到小排为有序序列。 内部排序
当待排数据元素的数量较少时，可将其一次全部调入内 存进行排序，即称内部排序。 外部排序
当待排数据元素的数量较大时，在排序过程中尚需对外 存进行访问，则称外部排序。
一、基本术语
1、直接插入排序法

数据结构9.内部排序

数据结构9.内部排序

2、快速排序
<1>、排序策略 x=r[1].key 一趟排序后，得：[ <=x的部分 ] x [ >=x的部分 ] 任选一个元素的关键字（如[1].key）作为标准，将序列分成两部分。其中 左半部分的结点的关键字小于等于该元素的关键字，右半部分的结点的关键字大 于等于该元素的关键字。然后, 对左右两部分分别进行类似的处理，直至排好序 为止。 <2>、示例 将 { 49、38、65、97、76、13、27、49 } 用 快速排序的 方法进行排序。 1 2 3 4 5 6 7 8
二、交换排序
1、冒泡排序 <1>、排序方法 相邻的两个元素的关键字进行比较，小的元素向上冒，大的元素 向下沉。 <2>、排序示例 将 { 49, 38, 65, 97, 76, 13, 27, 49 } 用起泡排序的方法进行排序。
2 3 4 5 6 7 8
0
1
49
第一趟排序
38
65
97
76
13
27
76 97
27 97 27
49
76
49
49
13
13 13 13
38 49
38 49 38 38 13 38
76 97 27
65 76 97 27 76 97 27 76 97 27 76 97 27
49 49
49 49
49 65 49 65 49 65
<3>直接插入排序算法 void InsertSort ( ){ // 对记录序列r[1]..r[n]作直接插入排序 for ( i=2; i<=n; i++ ) //从第二个元素开始比较 { r[0] = r[i]; //r[0]为监视哨 j= i-1; while ( r[0].key < r[j].key) { r[j+1] = r[j];j--; } // 记录后移,边移动边找插入位置 r[j+1] = r[0]；//插入到正确位置 } } // InsertSort <4>算法分析 （1）时间分析: (用移动和比较次数可作为衡量时间复杂性的标准) 正序时：比较次数 ∑ 1 = n-1,移动次数 0 逆序时：比较次数 ∑ i, 移动次数 ∑ (i+1) 所以时间复杂度 T(n)=O(n2) （2 ）空间分析: 在移动时不需要另增加存储空间， 所以空间复杂度 S(n)=O(1) （3）稳定性 由于是在线性表中逐一比较，所以该算法是稳定的。

数据结构教程 第九章 排序

数据结构教程 第九章 排序
2 插入排序


9.2.3 希尔排序
3.算法



void ShellSort() { gap=n/2;//初次增量取序列元素个数n的一半为步长 while(gap>0) { for(i=gap+1;i<=n;i++) { j=i-gap; while(j>0) { if(r[j]>r[j+gap]) { x=r[j];r[j]=r[j+gap];r[j+gap]=x; j=j-gap; }//对子序列作直接插入排序 else j=0; } } gap=gap/2;}//每次减半，直至步长为1 上一页 }
上一页
下一页
9.3 快速排序法


9.3.2 快速排序
3【例9-5】对数据序列:70, 75, 69, 32, 88, 18, 16, 58进行快速排序如图9-3所示。 4.算法


void QuickSort(int low, int high)//递归形式的快速排序 { int pivotpos; if(low<high) { pivotpos=Partition(low,high); QuickSort(low,pivotpos-1);//对低子表递归排序 QucikSort(pivotpos+1,high);//对高子表递归排序 } }
9.2 插入排序


9.2.2 二分插入排序
3.算法



void BinsSort() { for(i=2;i<=n;i++) { r[0]=r[i];low=1;high=i-1;//将r[i]暂存到r[0] while(low<=high) //在r[low..high]中折半查找有序插入的位置 { m=(low+high)/2;//折半 if(r[0].key<r[m].key) high=m-1;//插入点在低半区 else low=m+1;//插入点在高半区 } for(j=i-1;j>high+1;--j) r[j+1]=r[j];//记录后移 r[high+1]r[0];//插入 } 上一页 下一页

数据结构第9章 排序

数据结构第9章 排序

R[3] 10
R[4] 60
R[5] 25
R[6] 30
R[7] 18 18 18 18
18 36 20

10 10 36
60 60 60
25 25 25
30 30 30
【算法】直接插入排序 void D_InsertSort(datatype R[ ], int n) { /*对排序表R[1]..R[n]进行直接插入排序，n是记录的 个数*/ for(i=2; i<=n; i++) if (R[i].key<R[i-1].key) {R[0]=R[i]; /*将R[i]插入R[1].. R[i-1]中， R[0]为监测哨*/ for(j=i-1; R[0].key<R[j].key; j--) R[j+1]=R[j]; /*后移记录*/ R[j+1]=R[0]; /*插入到合适位置*/ } }
空间性能：除排序表以外的内存占用情况。 时间性能：比较关键码的次数，数据移动的次数。 它们往往是排序表规模（n）的函数
6. 记录和排序表的数据结构
一般采用顺序结构存储排序表。 记录和排序表的类型定义如下： #define MAXNUM … /* MAXNUM 为足够大的数 typedef struct { keytype key; …… } datatype; datatype R[MAXNUM]; /*关键码字段*/ /*其它信息*/ /*记录类型*/ /*定义排序表的存储
第一趟排序结果，使得间隔为5的字表有序： P=3
29 7 41 30 11 39 50 76 41 13 10 0 80 78 86
子序列分别为:{29,30,50,13,78}，{7,11,76,100,86}， {41,39,41,80}。第二趟排序结果： P=1

数据结构 第9章(内排序)

数据结构 第9章(内排序)

3. 将R[j+1]=R[0] 实现整个序列的排序。
North China Electric Power University
排序算法如下：
void insort(List r, int n) {//r为给定的表，其记录为r[i]，i=0，1，…，n，x为暂存单元。 for (i=2; i<=n; i++) { r[0]=r[i]; //r[0]作为标志位 j=i-1; while (r[0].key<r[j].key) { r[j+1]=r[j]; j--; } //j从i-1至0，r[j].key与r[i].key进行比较 r[j+1]=r[0]; } }//insort
North China Electric Power University
例如：
第二趟希尔排序，设增量d = 3
第三趟希尔排序，设增量d = 1
North China Electric Power University
希尔排序的算法描述如下:
void ShellInsert (List r,int d) //本算法对直接插入算法作了以下修改： // 1. 前后记录位臵的增量是d，而不是1； // 2. r[0]只是暂存单元，不是哨兵。当j<=0时，插入位臵已找到。 for (i=2;i<= n ; i++) { { r[0]=r[i]; for(i=d+1;i<=n;i++) j=i-1; if ( r[i] < r[i-d]) //需将r[i]插入有序增量子表 while ( r[0].key<r[j].key) { r[0] = r[i]; //暂存在R[0] { r[j+1]=r[j]; j=i-d ; j=j-1; while ((j>0) and (r[0] < r[j])) } { r[j+d] = r[j]; //记录后移，查找插入位臵 r[j+1]=r[0]; j=j-d; } } r[j+d] = r[0];//插入 } }

《数据结构(C／C++描述)》-第9章 内排序

中国水利水电出版社
15
16 物料管理
Data Structures: Chapter 9
9.2
插入排序
0 1 10 50 2 20 40 3 30 30 4 40 20 5 50 10
直接插入排序算法分析：
分析: 移动、比较次数可作为衡量时间复杂性的标准 O(n2)
正序时：比较次数
∑
n-1
1 = n-1 j=1
定的。
中国水利水电出版社
5
6 物料管理
Data Structures: Chapter 9
插入排序的数据类型定义如下：
typedef struct elemtype //待排序的数据记录类型
{ keytype key; //数据记录的关键字
anytype otherelem; //数据记录中的其他成份 }datatype;
3. 希尔排序－－缩小增量排序
基本思想： 对待排记录序列先作“宏观”调整，再作 “微观”调整。 所谓“宏观”调整，指的是 “跳跃式”的 插入排序。具体做法为：
中国水利水电出版社
21
22 物料管理
Data Structures: Chapter 9
将记录序列分成若干子序列，分别对每个子序列进 行插入排序。 例如：将 n 个记录分成 d 个子序列： { R[1]，R[1+d]，R[1+2d]，…，R[1+kd] } { R[2]，R[2+d]，R[2+2d]，…，R[2+kd] } … { R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d] }
中国水利水电出版社
7
9.2
8 物料管理
Data Structures: Chapter 9

数据结构(C语言版)-内部排序

数据结构
主讲人： 主讲人：米晓红 hongxiaomi@
1
第十章
内部排序
10.1 10.2 10.3 10.4 10.5 10.7
基本概念 插入排序 快速排序 选择排序 归并排序 讨论
2
10.1 基本概念
•术语
记录——结点；文件——线性表； 记录——结点；文件——线性表； ——结点 ——线性表 关键码：能够唯一确定结点的一个或若干域。 关键码：能够唯一确定结点的一个或若干域。 排序码：作为排序运算依据的一个或若干域。 排序码：作为排序运算依据的一个或若干域。 组合排序码： 主关键码，次关键码) 组合排序码：(主关键码，次关键码) 例：(总分数，数据结构分数，大学英语分数) 总分数，数据结构分数，大学英语分数)
•排序：将一个数据元素 或记录 的任意序列，重 排序：将一个数据元素(或记录 的任意序列， 或记录)的任意序列
排成一个按排序码有序的序列。 排成一个按排序码有序的序列。即排序码域的值 具有不减(或不增 的顺序。 或不增)的顺序 具有不减 或不增 的顺序。
3
排序问题：给定一组记录 1 排序问题：给定一组记录r1, r2, …rn，其排序码分别 ， 为k1, k2, …，kn，将这些记录排成顺序为rs1,rs2,…rsn 1 ，将这些记录排成顺序为r r 的一个序列S，满足条件k 1 的一个序列 ，满足条件ks1≤ks2≤…≤ksn 。 2
•稳定与不稳定排序：若记录序列中的任意两个记录 稳定与不稳定排序：
Rx、 Ky； Rx、Ry 的关键字 Kx = Ky；如果在 排序之前和排序之 它们的相对位置保持不变， 后，它们的相对位置保持不变，则这种排序方法是稳定 的排序，否则是不稳定的排序。 的排序，否则是不稳定的排序。

数据结构-9内部排序


7
16
28
36
41
j=4
k=3
L[k]与L[j]比较
22:37
9.2.2 选择排序法
一趟排序算法：
void SelectPass(SqList &L,int i) { RcdType W; int j,k; k=i; // j指示无序序列中第一个记录的位置 for(j=i+1;j<=L.length;j++) if(L.r[k].key>L.r[j].key) k=j; //只记录位置 if(i!=k) // 交换R[j]和R[i]; { w=L.r[i]; L.r[i]=L.r[k]; L.r[k]= w; } // L.r[i]←→ L.r[j]; } // SelectPass

起泡排序 选择排序 插入排序 快速排序 归并排序 堆排序 基数排序
2. 外部排序（External Sort）：在排序进行的过程 中需要对外存进行访问的排序过程。
9.1.4 内排序的特点
大多数排序算法都有两个基本的操作：
（1）比较两个关键字的大小 （2）将记录从一个位置移动到另一个位置
13
27
38
492
491
65
76
22:37
9.2.2 选择排序法 时间复杂度：O(n2) 空间复杂度：O(1) 优点：
算法简单；辅助空间少。
缺点：
效率低；不稳定性排序（可以改进）。
22:37
9.2.3 插入排序
基本思想：依次将记录序列中的每一个记录插入到有序段中，使有 序段的长度不断地扩大。其具体的排序过程可以描述如下：首先将 待排序记录序列中的第一个记录作为一个有序段，将记录序列中的 第二个记录插入到上述有序段中，形成由两个记录组成的有序段， 再将记录序列中的第三个记录插入到这个有序段中，形成由三个记 录组成的有序段，…依此类推，每一趟都是将一个记录插入到前面 的有序段中。 假设当前欲处理第i个记录，则将R[i]这个记录插入到有序R[1..i-1] 段中，从而使有序序列长度增1，直到所有记录都插入到有序段中。 一共需要经过n-1趟就可以将初始序列的n个记录重新排列成按关键 字值大小排列的有序序列。 一趟排序开始 R[i]

数据结构与算法(C++语言版)》第9章 内部排序


插入排序
插入排序
• 以上述静态链表类型作为待排记录序列的存储结构，并设 数组中下标为0的分量为表头结点，并令表头结点记录的关 键码取最大整数MAXNUM。 • 表插入的排序过程是，首先将静态链表中数组下标为1的分 量（结点）和表头结点构成一个循环链表，然后依次将下 标为2～n的分量（结点）按记录关键码非递减有序插入到 循环链表中，算法如以下程序所示。
插入排序
例9-3
• 以关键码序列{52, 43, 68, 89, 77, 16, 24, 52*, 80, 31}为例，表 插入排序的过程如下列图所示。
插入排序
• 从上面的过程可看出，表插入排序与直接插入排序的不同 之处在于，表插入排序以修改2n次指针值来代替记录的移 动，但和关键码的比较次数相同，因此表插入排序的时间 复杂度仍为O(n2)。
i=n
交换排序
• 快速排序 • 快速排序（quick sort）是Hoare于1962年提出的一种分区交 换排序。它采用了一种分而治之的策略，是对冒泡排序的 一种改进。其算法思想是，首先将待排序记录序列中的所 有记录作为当前待排序区域，选取第一个记录的关键码值 为基准（轴值），从待排序记录序列左、右两端开始向中 间靠拢，交替与轴值进行比较，若左侧记录的关键码值大 于轴值，则将该记录移到基准记录的右侧，若右侧记录的 关键码值小于轴值，则将该记录移到基准记录的左侧，最 后让基准记录到达它的最终位置，此时，基准记录将待排 序记录分成了左右两个区域，位于基准记录左侧的记录都 小于或等于轴值，位于基准记录右侧的所有记录的关键码 都大于或等于轴值，这就是一趟快速排序。
例9-5
• 如图所示为冒泡排序的一个示例。冒泡排序的效率分析： ① 若初始序列为“正序”序列，则只需进行一趟排序，在 排序过程中进行n−1次关键码的比较，且不移动记录；② 若 初始序列为“逆序”序列，则需进行n−1趟排序，需进行 2 ∑ (i − 1) = n(n − 1) / 2次比较。因此，总的时间复杂度为O(n2)。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

内部排序：整个排序过程完全在内存中进行，称为内部 排序。 外部排序：由于待排序记录数据量太大，内存无法容纳 全部数据，排序需要借助外部存储设备才能完成，称为 外部排序。 稳定排序和不稳定排序：假设Ki=Kj(1≤i≤n，1≤j≤n， i≠j)，若在排序前的序列中Ri领先于Rj(即i<j)，经过排 序后得到的序列中Ri仍领先于Rj，则称所用的排序方法 是稳定的 ；反之，当相同关键字的领先关系在排序过 程中发生变化，则称所用的排序方法是不稳定的。 在排序过程中，一般进行两种基本操作： （1）比较两个关键字的大小； （2）将记录从一个位置移动到另一个位置。 对于第二种操作，需要采用适当地存储方式，即向量结 构(顺序结构)、链表结构以及记录向量与地址向量结合 的表示方法。
n i 2 n 序
直接插入排序：R[i]按照顺序查找的方式查 找插入(在已排序的有序子序列)位置。 折半插入排序：R[i]按照折半查找的方式查 找插入(在已排序的有序子序列)位置。 不同点：查找插入位置的方式不同
void BinSort (RecordType r[],int length) /*对记录数组r进行折半插入排序，length为数组的长度*/ { for ( i=2 ; i<=length ; ++i ) { x= r[i]; low=1; high=i-1; while (low<=high ) /* 查找插入位置 */ { mid=(low+high) / 2; if ( x.key< r[mid].key ) high=mid-1; else low=mid+1; } for ( j=i-1 ; j>= low; --j ) r[j+1]= r[j]; /* 记录依次向后移动 */ r[low]=x; /* 插入记录 */ } }
最好的情况(关键字在记录序列中顺序有序)： “比较”的次数： 1 n 1 “移动”的次数： 2 2(n 1) 最坏的情况(关键字在记录序列中逆序有序)： n (n 2)(n 1) i “比较”的次数：i 2 2 “移动”的次数： n (i 1) (n 4)(n 1)
算法分析： 采用折半插入排序法，可减少关键字的比较次 数。每插入一个元素，需要比较的次数最大为 折半判定树的深度，如插入第i个元素时，设 i=2j,则需进行log2i次比较，因此插入n-1个元素 的平均关键字的比较次数为O(nlog2n)。 虽然折半插入排序法与直接插入排序法相比 较，改善了算法中比较次数的数量级，但其并 未改变移动元素的时间耗费，所以折半插入排 序的总的时间复杂度仍然是O(n2)。
13 2
42 2
94 0
17 4
05 6
90 1
★希尔排序的逆转数逐渐减少。 ★时间复杂度：O(n1.5)
当di=1时，排序结束，逆转数等于0。虽然此时的希尔排 序仍相当于直接插入排序，但此时逆转数很小，因此移 动次数相对较少，导致效率的提高。
★希尔排序是不稳定的排序方法。
9.3 交换类排序
冒泡排序(相邻比序法) 快速排序法 9.3.1 冒泡排序
d1=4
46
55
13
42
94
17
05
70
d2=2
46
17
05
42
94
55
13
70
d3=1
05
17
13
42
46
55
94
70
05
13
17
42
46
55
70
94
希尔排序算法如下： void ShellInsert(RecordType r[], int length，int delta) /*对记录数组r做一趟希尔插入排序，length为数组的长度,delta 为增量*/ { for(i=1+delta ；i<= length； i++) /* 1+delta为第一个子序列的第二个元素的下标 */ if(r[i].key < r[i-delta].key) { r[0]= r[i]； /* 备份r[i] (不做监视哨) */ for(j=i-delta； j>0 &&r[0].key < r[j].key ； j-=delta) r[j+delta]= r[j]； r[j+delta]= r[0]； } }/*ShellInsert*/ void ShellSort(RecordType r[], int length)
3、选择类
从记录的无序子序列中选择关键字最小或 最大的记录，并将它加入到有序子序列中， 以此方法增加记录有序子序列的长度。
4、归并类
通过归并两个或两个以上的有序子序列， 逐步增加记录有序子序列的长度。
9.2 插入类排序
基本思想：在一个已排好序的记录子集的基础上，每一
步将下一个待排序的记录有序插入到已排好序的记录子集 中，直到将所有待排记录全部插入为止。
48 48 48 48
62 62 35 35
35 35 62 62
77 77 77 77
55 55 55 55
14 14 14 14
9.2.1 直接插入排序
基本操作是将第i个记录插入到前面i-1个已排好序的记录 中，具体过程为：将第i个记录的关键字Ki顺次与其前面 记录的关键字Ki-1，Ki-2，…K1进行比较，将所有关键字 大于Ki的记录依次向后移动一个位置，直到遇见一个关键 字小于或者等于Ki的记录Kj，此时Kj后面必为空位置，将 第i个记录插入空位置即可。
希尔排序的基本思想是：先将待排序记录序列分
割成若干个“较稀疏的”子序列，分别进行直接插入 排序。经过上述粗略调整，整个序列中的记录已经基 本有序，最后再对全部记录进行一次直接插入排序。 具体实现时，首先选定两个记录间的距离d1，在整个 待排序记录序列中将所有间隔为d1的记录分成一组， 进行组内直接插入排序；然后再取两个记录间的距离 d2<d1，在整个待排序记录序列中，将所有间隔为d2的 记录分成一组，进行组内直接插入排序；直至选定两 个记录间的距离dt=1为止，此时只有一个子序列，即 整个待排序记录序列。
直接插入排序算法 假设待排序记录存放在r[1..n]之中，为了提高效率， 我们附设一个监视哨r[0]，使得r[0]始终存放待插入 的记录。
void InsSort(RecordType r[],int length) /*对记录数组r做直接插入排序，length为数组的长度*/ { for ( i=2 ; i<= length ; i++ ) { r[0]=r[i]; j=i-1; /*将待插入记录存放到r[0]中*/ while (r[0].key< r[j].key ) /* 寻找插入位置 j*/ { r[j+1]= r[j]; j=j-1; } r[j+1]=r[0]; /*将待插入记录插入到已排序的序列中*/ } } /* InsSort */
表插入排序
表插入排序是采用链表存储结构进行插入排序的方法。 表插入排序的基本思想是：先在待插入记录之前的有 序子链表中查找应插入位置，然后将待插入记录插入 链表。(静态链表) 优点：减少移动的次数 typedef int KeyType; typedef struct { KeyType key; OtherType other_data; int next; } RecordType1;
内部排序分类
思想：逐步扩大有序子序列的长度：
有序序列区 无序序列区
一趟排序
有序序列区
无序序列区
插入类排序、交换类排序 选择类排序、归并类排序 其它方法
1、插入类
将无序子序列中的一个或几个记录插入 到有序序列中，从而增加记录的有序子 序列的长度。
2、交换类
通过交换无序序列中的记录从而得到其中 关键字最小或最大的记录，并将它加入到 有序子序列中，以此方法增加记录的有序 子序列的长度。
该算法的要点是： ①使用监视哨r[0]临时保存待插入的记录。 ②从后往前查找应插入的位置。 ③查找与移动用同一循环完成。
直接插入排序算法分析： 从空间角度来看，它只需要一个辅助空间r[0]。 从时间耗费角度来看，主要时间耗费在关键字比较和 移动元素上。 直接插入排序方法是稳定的排序方法。(待插入的元素 的比较是从后向前进行的)
第十章
排序
9.1 排序的基本概念 9.2 插入类排序
9.3 交换类排序法
9.4 选择类排序法 9.5 归并排序
9.6 分配类排序
9.7 各种排序方法的综合比较
9.1 排序的基本概念
排序：是计算机内经常进行的一种操作，其目 的是将一组无序的记录序列调整为有序的记录 序列。
排序：有n个记录的序列{R1，R2，…，Rn}，其相应关 键字的序列是{K1，K2， …，Kn }，相应的下标序列为 1，2，…， n。通过排序，要求找出当前下标序列1， 2，…， n的一种排列p1，p2， …，pn，使得相应关键 字满足如下的非递减（或非递增）关系，即：Kp1≤ Kp2≤…≤ Kpn ，这样就得到一个按关键字有序的记录 序列：{Rp1， Rp2， …， Rpn}。
/*对记录数组r做希尔排序，length为数组r的长度,delta 为增量数组，n为delta[]的长度 */
{ for(i=0 ；i<=n-1；++i) ShellInsert(r，Length, delta[i])；
}
算法分析
★逆转数：指在它之前比此关键字大的关键字个数。
关键字 逆转数
46 55 0 0


下面给出了一个完整的直接插入排序实 例。图中大括号内为当前已排好序的记 录子集合。