教程数据结构1.6

第

1章数据结构1.1数据结构基本概念与算法

1.2线性表1.3栈和队列1.4树和二叉树

1.5查找1.6排序ABCDEFG姓名学号成绩班级李红976105995机97.6

10658651.6排序排序：是计算机程序设计中一个重要运算，它的功能是将一组任意序列的数据元素，进行按关键字由大到小的顺序（降序）排列或按由小到大的顺序（升序）排列。学号姓名入学成绩住址电话2李洪556六舍53711115王刚553四舍53721114王名567五舍53732113张强549六舎53722211.排序的功能：将一个数据元素的任意序列，重新排成一个按关键字有序的序列。2.内部排序与外部排序

根据排序时数据所占用存储器的不同,可将排序分为两类:

内部排序:整个排序过程完全在内存中进行.

外部排序:由于待排序记录数据量太大,内存无法容纳全部数据,排序需要借助外部存储设备才能完成.3.排序算法评价：算法执行时间，即时间复杂度。

4.稳定性：待排序列中有两个关键字相等的记录，排序前后记录的先后顺序没变该排序方法就是稳定的，否则就是不稳定的1.6排序

1.6.1排序的基本概念

插入排序的基本思想：插入排序三种方法1.直接插入排序2.折半插入排序3.希尔排序1.6排序

1.6.2插入排序1.直接插入排序（稳定排序）思路具体过程时效分析最好情况:初始排序码已经有序。共比较n-1次，移动0次。时间复杂度为O(n2)1.6排序

1.6.2插入排序<例>直接插入排序(升序):趟数ir[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]

(49)39669676112749*

(3949)669676112749*第一遍后(394966)9676112749*第二遍后(39496696)76112749*第三遍后(3949667696)112749*第四遍后(113949667696)2749*第五遍后(11273949667696)49*第六遍后(1127394949*667696)

第七遍后初始voidDirectInsertionSort(inta[],intn){ inti,j,temp; for(i=1;i<n;i++) { temp=a[i]; for(j=i-1;j>=0&&a[j]>temp;j--) a[j+1]=a[j]; a[j+1]=temp;}}P691.直接插入排序思路具体过程时效分析最好情况:初始排序码已经有序。共比较n-1次，移动0次。时间复杂度为O(n2)1.6排序

1.6.2插入排序2、折半插入排序（稳定排序）

折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。例：有6个记录，前5个已排序的基础上，对第6个记录排序。[1527365369]42

lowmidhigh

(42>36,后半)[1527365369]

42

lowhigh

mid

(42<53,前半)

[1527365369]42

highlow(high<low，查找结束，插入位置为low或high+1)[152736425369]

折半插入排序其时间复杂度为O(nlog2n)。1.6排序

1.6.2插入排序3.希尔排序（缩小增量排序）基本思想：将整个无序序列分割成若干个子序列分别进行直接插入排序,待整个序列中的记录”基本有序”时,再对全体记录进行一次直接插入排序。子序列分割：选定两个元素之间距离t，将所有间隔为t的元素分成一组具体实现:

(1)选择一个增量序列t1

，t2，…

，tk,其中tk=1。(2)按增量序列个数k，对序列进行k趟排序。(3)每趟排序，根据对应的增量ti，将序列分割成若干个子序列，分别对各子序列直接插入排序。tk=1时，对全部元素进行一次直接插入排序即可完成。1.6排序

1.6.2插入排序举例:

有一个含有14个数的序列,使用希尔排序进行升序排序

(39,80,76,41,13,29,50,78,30,11,100,7,41,86)取增量：5，3，1t=53980764113295078301110074186(R1,R6,R11)3929100(R2,R7,R12)

80507(R3,R8,R13)

767841(R4,R9,R14)

413086(R5,R10)

1311则子序列：{39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}R1,R2,R3,R4,R5,R6,R7,R8,R9,R10R11,R12,R13,R14t=53980764113295078301110074186子序列：{39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}R1,R2,R3,R4,R5,R6,R7,R8,R9,R10R11,R12,R13,R14(R1,R6,R11)

29

39100(R2,R7,R12)75080(R3,R8,R13)

417678(R4,R9,R14)304186(R5,R10)11

13因此第一趟排序结果如下:

2974130113950764113100807886对每个序列进行直接插入排序:t=3

29741301139507641131008078862930501378

7117610086

41394180子序列：{29，30，50，13，78}，{7，11，76，100，86}，{41，39，41，80}分别对子序列进行直接插入排序1373929114130764150868078100(R1,R4,R7,R10,R13)(R2,R5,R8,R11,R14)(R3,R6,R9,R12)R1R2R3R4R5R6R7R8R9R10R11R12R13R1413293050787117686100

39

414180第二趟最终结果：第一趟排序结果1373929114130764150868078100t=1

序列基本有序，对其进行直接插入排序,第三趟最终结果：7111329303941415076788086100第二趟最终结果：？目前没有找到最好的求增量序列的方法n在某个特定范围内，时间复杂度为O(n1.3)

对待排序记录两两比较关键字，不满足排序顺序则交换，直到满足排序要求。基本思路交换排序种类:冒泡排序快速排序

1.冒泡排序（稳定排序）基本思想：通过相邻元素的交换，逐步将待排序列变成有序。1.6排序

1.6.3交换排序<例>3849657613273097第一趟38496513273076第二趟384913273065第三趟3813273049第四趟13273038第五趟132730第六趟4938659776132730初始关键字n=8384976971397279730971376767627301365276530651313494930492738273830381327第七趟思想：小的浮起，大的沉底。初始已排好序(正序最好)，则只需进行一趟排序,比较次数n-1，移动次数为0。逆序(最坏)，则需进行n-1趟排序,比较次数和移动次数均达到最大。是稳定的排序,时间复杂度为O(n2).

时效分析:voidBubbleSort(inta[],intn){inti,j,temp,flag;for(i=0;i<n-1;i++){flag=1;/*设交换标志，flag=1为未交换*/ for(j=0;j<n-1-i;j++) if(a[j+1]<a[j]) {flag=0;/*已交换*/ temp=a[j]; a[j]=a[j+1]; a[j+1]=temp;} if(flag)break;/*未交换，排序结束*/}}p742.快速排序基本思想：

通过一趟排序将待排记录分割成独立两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再对前、后两部分待排记录重复上述过程，直到整个序列有序止。优点：

通过两个不相邻元素交换，可以一次交换消除多个逆序，加快排序速度。

4939669676112750[273911]49[76

966650]

2739

49[5066]7696

1.6排序

1.6.3交换排序2749*117696665049举例:将（49，49*，66，96，76,11，27，50）进行一趟快速排序4949*669676112750i2749*6696761150i49jj2749*119676665049ji2749*967611665049ji完成一趟排序:初始关键字ijj27391176966650举例:将（49，39，66，96，76,11，27，50）进行一趟快速排序4939669676112750i27396696761150ijj27391196766650ji27399676116650ji完成一趟排序:初始关键字ijj494949*669676112750[2749*11]49

[

76

966650]一次划分之后快速排序的全过程初始关键字分别进行快速排序[11]

27

[49*]

50

[66]

结束结束[

5066]

76

[96]

结束结束112749*4950667696有序序列时效分析:平均时间复杂度为O(nlog2n)。

基本思想：

每次从待排序的记录中选出关键字最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完。选择排序种类:

直接选择排序和堆排序1.6排序

1.6.4选择排序1.直接选择排序

举例:将（49，39，66，49*，76，11，27，96）直接选择排序原序列49396649*76112796i=011396649*7649

2796i=111276649*76493996i=211273949*764966

96

i=311273949*76496696

i=411273949*49

76

6696

i=511273949*4966

76

96

i=611273949*496676

96

时间复杂度是O(n2)1.6排序

1.6.4选择排序a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]例：用选择法对8个数排序（从小到大）输入数组各元素的值for(i=0;i<7;i++)k=ifor(j=i+1;j<8;j++)a[k]>a[j]ynk=j交换a[k]和a[i]输出排好序的8个数i!=kynvoidDirectSelectSort(STUDENTa[],intn)//按入学分数排序{inti,j,k;STUDENTtemp; for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) if(a[k].score>a[j].score) k=j; if(i!=k) { temp=a[k]; a[k]=a[i]; a[i]=temp; } }}P812.堆排序堆定义：n个元素的序列{K1，K2，…，Kn}，当且仅当满足下列关系时，称为堆。

ki≤k2i

ki≤k2i+1

ki≥k2i

ki≥k2i+1

小根堆或大根堆堆结构：将序列对应的一维数组看成一个完全二叉树。在堆中,堆顶元素必为序列中n个元素的最小值(或最大值)。

小根堆251566103070153066702510

大根堆其中:（i=1，2，…，n/2）k1k2k3k4k5k6101566253070...703066152510...1.6排序

1.6.4选择排序举例:一个无序序列(49,39,66,96,76,11,27,50)建小根堆的过程4939966676112750无序序列493950667611279696被筛选后状态,493950117666279666被筛选后状态

4939501176662796

39被筛选后状态

目前的堆中,堆顶元素11为最小值,输出后,重新对n-1个元素重新建一个新堆,新堆中的堆顶是剩余的n-1个元素中的最小值,n个元素中的次最小值.113950497666279649被筛选后建成的堆11395027766649964939501176662796

39被筛选后状态

堆113950277666499611与96交换后情形输出堆顶元素之后,调整剩余元素成为一个新的堆。1139502776664996113950967666492727与96交换后情形1139504976669627

调整后新堆,27为新堆中的最小值剩下7个结点27395049766696输出27,用96替代

11112796504976663996与39换509649766639112796与50换39504976669627

调整后新堆,27为新堆中的最小值11堆排序的时效分析:

时间复杂度为O(nlog2n)，适合规模较大的线性表。查找与排序补充习题讲解1.链表适用于_____查找.A.顺序B.二分法C.顺序,也能二分法D.随机2.对长度为n的线性表进行顺序查找,在最坏情况下所需要的比较次数为____.A.log2nB.n/2C.nD.n+1（05年4月）3.已知一个有序表为(13、18、24、35、46、50、62、83、

90、115、134），当使用二分法查找90的元素时，查找成功的比较次数为______.A.1B.2C.3D.94.在排序算法中，两两比较待排序的记录，当发现不满意顺序要求时，变更他们的相对位置，这就是__排序。BA.希尔排序B.交换排序

C.插入排序D.选择排序ACBB查找与排序补充习题讲解5.设待排序关键码序列为（33、18、9、25、67、82、53、

95、12、70），要按关键码值递增的顺序排序，采取以第一个关键码为分界元素的快速排序法，第一趟排序完成后关键码33被放到了第____个位置。

A.3B.5C.7D.96.希尔排序法属于哪一种类型的排序法______。

A.交换类排序法B.插入类排序法

C.选择类排序法D.建堆排序法7.以下各组序列中，属于堆的是_______.AA.26、34、27、97、66、75B.97、26、34、75、27、66C.27、66、26、97、34、75D.27、75、34、26、97、668.对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是______.(05.4月）D

A.冒泡排序为n/2B.冒泡排序为nC.快速排序为nD.快速排序为n(n-1)/2BBAD:8:在最坏情况下,冒泡排序和快速排序的比较次数都是

n(n-1)/2

查找与排序补充习题讲解填空题：1.在排序方法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素做比较，将其放入已排序的正确位置上的方法，称为_____.（插入排序）2.对于给定的一组关键字（12、2、11、30、8、28、4、10、20、6、18），按照希尔排序（增量为5）算法进行递增排序，第一趟排序后得到的结果是_____.（12、2、11、30、8、28、4、10、20、6、18）12281811