第10章内排序-1（概念+插入排序）

10.1排序的基本概念10.2插入排序10.3交换排序10.4选择排序第10章内排序10.5归并排序10.6基数排序10.7各种内排序方法的比较和选择1/39第10章内排序说明：排序数据中可以存在相同关键字的元素。本章仅考虑递增排序。1、排序的定义10.1排序的基本概念

所谓排序，是整理表中的元素，使之按关键字递增（或递减）有序排列：排序n个元素，R0，R1，…，Rn-1，关键字分别为k0，k1，…，kn-1Ri,0，Ri,1，…，Ri,n-1，使得递增ki,0

≤

ki，1≤…≤ki,n-1

（或递减ki,0≥ki,1≥…≥ki,n-1）2/3910.1排序的基本概念在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外排序。2、内排序和外排序文件内存3/3910.1排序的基本概念3、内排序的分类内排序基于比较的排序算法非比较的排序算法插入排序交换排序选择排序归并排序基数排序4/3910.1排序的基本概念基于比较的内排序算法最快有多快？假设有3个元素(R1，R2，R3)，对应的关键字为(k1，k2，k3)。初始数据序列有3!=6种情况：1，2，31，3，22，1，32，3，13，1，23，2，1

n个元素，初始数据序列有n!种情况5/3910.1排序的基本概念以(R1，R2，R3)=（2，3，1）为例，一种基于比较的排序方法：R1R2R3

231R1<R2为真，不交换R2<R3为假，R2、R2交换R1<R3为假，R1、R3交换总共3次关键字比较R1R2R3

231R1R3R2

213R3R1R2

1236/3910.1排序的基本概念k1≤k2(R1，R2，R3)k2≤k3(R1，R2，R3)①

(R1，R2，R3)k1≤k3(R1，R3，R2)②(R1，R3，R2)③(R3，R1，R2)是是否是否k1≤k3(R2，R1，R3)④

(R2，R1，R3)k2≤k3(R2，R3，R1)⑤(R2，R3，R1)⑥(R3，R2，R1)是否是否否所有可能的初始序列的排序过程构成一个决策树(判定树)：决策树是一棵有n!个叶结点的二叉树。7/3910.1排序的基本概念

决策树可以近似看成是一颗高度为h，叶结点个数为n!的满二叉树。…叶结点层，n!个结点h叶结点个数=n!总结点个数=2n!-1h=log2(总结点个数+1)=log2(n!)≈nlog2n平均关键字比较次数=h-1移动次数也是同样的数量级，即这样的算法最好平均时间复杂度为O(nlog2n)。8/3910.1排序的基本概念

当待排序元素的关键字均不相同时，排序的结果是唯一的。

4、内排序算法的稳定性2431512345张三李四王五刘六陈七张三李四王五刘六陈七9/3910.1排序的基本概念

如果存在有多个关键字相同的元素，经过排序后这些具有相同关键字的元素之间的相对次序保持不变，则称这种排序方法是稳定的。

反之，若具有相同关键字的元素之间的相对次序发生变化，则称这种排序方法是不稳定的。34315123

3534315123

3510/3910.1排序的基本概念若待排序的表中元素已按关键字排好序，称此表中元素为正序；若待排序的表中元素的关键字顺序正好和排好序的顺序相反，称此表中元素为反序。5、正序和反序有一些排序算法与初始序列的正序或反序有关，另一些排序算法与初始序列的情况无关。11/3910.1排序的基本概念typedefintKeyType;

//定义关键字类型typedefstruct

//元素类型{KeyTypekey;

//关键字项

InfoTypedata;

//其他数据项，类型为InfoType}

RecType; //排序的元素类型定义

待排序的顺序表的数据元素类型声明如下：6、

内排序数据的组织12/3910.1排序的基本概念有序区无序区一个一个地插入10.2插入排序基本思路局部有序区局部有序区：其中元素在后面排序中会发生位置的改变。如[3,6,8],1,5,7，其中[3,6,8]为局部有序区全局有序区：其中元素在后面排序中不再发生位置的改变。如[2,4,5],6,8,9，其中[2,4,5]为全局有序区有序区类型13/3910.2插入排序（1）直接插入排序（2）折半插入排序（3）希尔排序主要的插入排序方法：14/3910.2插入排序有序区R[0]

……

R[i-1]无序区R[i]

……

R[n-1]有序区R[0]……

R[i-1]

R[i]无序区R[i+1]

……

R[n-1]一趟排序初始时，有序区只有一个元素R[0]i＝1~n-1，共经过n-1趟排序10.2.1直接插入排序基本思路15/3910.2.1直接插入排序jR[i]j=i-1插入位置一趟直接插入排序：在有序区中插入R[i]的过程有序区R[0..i-1]无序区R[i..n-1]R[j+1]=tmptmp使R[0..i]有序

扩大有序区R[j]大时便后移:找第一个≤tmp的R[j]当R[i].key<R[i-1].key时16/3910.2.1直接插入排序

从R[i-1]向前找第一个小于或等于tmp的元素R[j]，在其后插入tmp97631例如01234有序区97631tmp9>67>63<6

在无序区从后向前查找第一个≤tmp.key的R[j]17/3910.2.1直接插入排序

【例10.1】设待排序的表有10个元素，其关键字分别为（9，8，7，6，5，4，3，2，1，0）。说明采用直接插入排序方法进行排序的过程。18/3910.2.1直接插入排序初始：98765432100123456789i=1：9876543210i=2：98765432109876543210i=3：19/3910.2.1直接插入排序i=3：9876543210i=4：9876543210i=5：987654321001234567899876543210i=6：20/3910.2.1直接插入排序i=6：98765432100123456789i=7：9876543210i=8：9876543210i=9：987654321021/3910.2.1直接插入排序voidInsertSort(RecTypeR[]，intn){inti，j;RecTypetmp;

for(i=1;i<n;i++)

{if(R[i].key<R[i-1].key])//反序时{tmp=R[i];

j=i-1;

do //找R[i]的插入位置

{R[j+1]=R[j];

//将关键字大于R[i].key的元素后移

j--;}while(j>=0&&R[j].key>tmp.key)

R[j+1]=tmp;

//在j+1处插入R[i]}

}}直接插入排序的算法：22/3910.2.1直接插入排序算法分析最好的情况（关键字在元素序列中正序）：如（1,2,3,4,5）“比较”的次数：0“移动”的次数：最好：O(n)23/3910.2.1直接插入排序最坏的情况（关键字在元素序列中反序）：如（5,4,3,2,1）R[i]插入到R[0..i-1]最前面，比较i次，移动i+2次voidInsertSort(RecTypeR[]，intn){inti，j;RecTypetmp;

for(i=1;i<n;i++)

{if(R[i].key<R[i-1].key]) //反序时{tmp=R[i];j=i-1;

do

//找R[i]的插入位置

{R[j+1]=R[j];j--;

//将关键字大于R[i].key的元素后移}while(j>=0&&R[j].key>tmp.key)

R[j+1]=tmp;

//在j+1处插入R[i]}

}}“比较”的次数：“移动”的次数：最坏：O(n2)24/3910.2.1直接插入排序平均情况：比较次数+移动次数平均：O(n2)如R[0..i-1]中插入R[i]，平均插入在中间位置R[i/2]25/3910.2.1直接插入排序10.2.2折半插入排序查找采用折半查找方法，称为二分插入排序或折半插入排序。有序区R[0]……

R[i-1]无序区

R[i]

……

R[n-1]采用折半查找在有序区找到插入的位置基本思路26/3910.2.2折半插入排序在R[low..high]中查找≥R[i].key（k=R[i].key）的最后的位置high

如果R[low..high]不空：mid=(low+high)/2R[low..mid-1]<kR[mid+1..high]≥

kk<R[mid].keyk≥R[mid].key

如果R[low..high]空：R[low..high]R[high+1..*]R[i]如何在R[low..high]中查找插入R[i]的位置？27/3910.2.2折半插入排序voidBinInsertSort(RecTypeR[]，intn){inti，j，low，high，mid;RecTypetmp;

for(i=1;i<n;i++)

{if(R[i].key<R[i-1].key]) //反序时{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; //插入点在右半区

}//在R[0..i-1]中找第一个>R[i]的位置high+1

for(j=i-1;j>=high+1;j--) //元素后移

R[j+1]=R[j];

R[high+1]=tmp; //插入tmp

}}}折半插入排序算法：28/3910.2.2折半插入排序在R[0..i-1]中查找插入R[i]的位置，折半查找的平均关键字比较次数为log2(i+1)-1。平均移动元素的次数为i/2+2。算法分析折半插入排序采用折半查找，查找效率提高，即减少关键字比较次数。但元素移动次数不变，仅仅将分散移动改为集合移动。29/3910.2.2折半插入排序说明：本题为2012年全国考研题对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（）。A.排序的总趟数

B.元素的移动次数C.使用辅助空间的数量

D.元素之间的比较次数30/3910.2.2折半插入排序答案为D。d=n/2将排序序列分为d个组，在各组内进行直接插入排序递减d=d/2，重复②，直到d=110.2.3希尔排序基本思路算法最后一趟对所有数据进行了直接插入排序，所以结果一定是正确的。31/3910.2.3希尔排序

将元素序列分成若干子序列，分别对每个子序列进行直接插入排序。{R[0]，R[d]，R[2d]，…，R[kd]}{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}…{R[d-1]，R[2d-1]，R[3d-1]，…，R[(k+1)d-1]}一趟希尔排序过程例如：将n

个元素分成d

个子序列：相距d个位置的元素分为一组一组一组一组32/3910.2.3希尔排序【例10-2】9876543210初始序列8765943210d=5直接插入排序4321098765d=d/2=243210987650123456789直接插入排序d=d/2=10123456789直接插入排序0123456789注意：对于d=1的一趟，排序前的数据已将近正序！33/3910.2.3希尔排序voidShellSort(RecTypeR[]，intn){inti，j，d;RecTypetmp;

d=n/2;

//增量置初值

while(d>0)

{for(i=d;i<n;i++)

{//对相隔d位置的元素组直接插入排序tmp=R[i];j=i-d;

while(j>=0&&tmp.key<R[j].key)

{R[j+d]=R[j];

j=j-d;

}

R[j+d]=tmp;

}

d=d/2;

//减小增量

}}希尔排序算法：for(i=1;i<n;i++){tmp=R[i];

j=i-1;

while(j>=0&&

t