第10章 内部排序

《第10章 内部排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第10章排序从二分查找要求查找表都是有序的而引入排序本章主要内容：10.1概述10.2插入排序10.3快速排序10.4选择排序10.5归并排序10.6基数据排序10.7各种内部排序方法的比较讨论10.8外部排序10.1概述一、定义：P263二、排序方法分类三、存储结构P264四、学习本章内容时应注意以下几方面内容：相应排序算法的基本思想具体算法效率分析优、缺点：如何改进排序方法分类根据不同的标准有不同的分类方式：一、根据排序过程中是否涉及不同存储器之间数据交换分类如下：二、根据排序策略可分类如下：三、根据排序方法的稳定性可分类如下：不

2、稳定的排序法稳定的排序法排序10.2插入排序本节主要内容:10.2.1直接插入排序10.2.2其他插入排序（折半、2-路、表插入等）10.2.3希尔排序10.2.1直接插入排序1、基本思想：示P2652、具体算法：P2653、效率分析：T(n)=O(n2)S(n)=O(1)4、优、缺点：1、直接插入排序的基本思想：从待排序的第二个记录开始，依次将记录插入到前面已排好序的序列中，直到整个记录有序为止。初始关键字：49，38，65，76，13，27i=2:38，49，65，76，13，27i=3:38，49，65，76，13，27i=4:

3、38，49，65，76，13，27i=5:13，38，49，65，76，27i=6:13，27，38，49，65，76麻烦i=7:13，27，38，49，49，65，76？，49，49，49，49，49，49i=2还是：13，27，38，49，49，65，76？10.2.2其他插入排序1、折半插入排序2、2-路插入排序3、表插入排序学生自学1、折半插入排序基本思想：P266具体算法：P267实现效率分析：T(n)=O(n2)减少了比较次数，但移动次数未变S(n)=O(1)优、缺点：减少了比较次数，但未减少移动次数（得改进方法）2、2-

4、路插入排序基本思想：示P267效率分析：T(n)=O(n2)(减少了移动次数,但不能绝对避免移动)S(n)=O(n)优、缺点：待排序记录如下，试用2-路插入排序法进行排序：01234567891011121349分析：开辟同样大小的辅助存储空间d49138265376413527668713121110980L.rd10.2.3希尔排序---缩小增量排序1、基本思想：P271示2、具体算法：P272示3、效率分析：P2724、优、缺点：例：用希尔排序法对以下记录排序：49、38、65、97、76、13、27、55、2、6、1初始状态：

5、49、38、65、97、76、13、27、55、2、6、1取增量d1=5将待排序记录分为5组123541134927385565297676一趟希尔排序12345每组内直接插入排序，得：组内有序位置序号：12345678910111、27、55、2、6、13、38、65、97、76、49取增量d2=3将待排序记录分为3组1556563813492972776第二趟希尔排序(已基本有序)123每组内直接插入排序，得：组内有序位置序号：1234567891011123最后取增量d3=1可得有序表1、2、6、13、27、38、49、55、6

6、5、76、9710.3快速排序（交换排序）本节主要内容：一、起泡排序二、快速排序一、起泡排序1、基本思想：两两依次比较，大的下沉、小的上浮P273示有以下结论：（1）对于含n个记录的一趟起泡排序共需比较n-1次（2）对于n个记录，用起泡排序法排序共需进行n-1趟，且第i趟需比较n-i次（3）若某趟排序过程中无记录交换，则排序结束2、具体算法：示3、效率分析：T(n)=O(n2)4、优、缺点：例1：用起泡排序法对以下记录进行排序：49、38、65、97、76、13、27、49分析：4938659776132749384965977

7、61327493849659776132749384965977613274938496576971327493849657613972749384965761327974938496576132749974938659776132749一趟起泡排序初始状态最大者沉底下一趟只需排的记录起泡排序算法voidBubble_sort(SqList&L){flag=1;/*某趟排序过程中记录交换与否标识*/for(i=1;i

8、<=n-i;j++)/*第i趟排序*/if(L.r[j].key>L.r[j+1].key){L.r[0]=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=L.r[0];flag=1;}}}二、快速排序1