第10章 内部排序0610

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

1、第十章内部排序东华理工学院程朋根本章内容:掌握内部排序的各种酸法和性能分析∑10.1概述∑10.2插入排序∑10.3快速排序∑10.4选择排序∑10.5归并排序∑10.7内部排序比较∑本章重点东华理工学院程朋根10.1概述∑排序（Sorting）：将一组数据元素的任意系列，重新排列程一个按关键字的有序的序列（无序到有序）∑排序结果与关键字有关¾主关键字：任何一组数据元素的无序序列，排序后的结果是唯一的¾次关键字：排序结果不唯一∑根据数据量大小的不同，排序可以分为两种：¾内部排序:在计算机的随机存储器中进行排序（内存）¾外部排序：数据量大、内存放不下，需要外存操作返回东华理工学院程

2、朋根∑排序过程的两种基本操作：¾比较关键字大小¾记录移位∑记录的移动方式与其存储结构有关：¾顺序存储时，移动记录¾连式存储时，修改指针¾记录本身存储在一组连续的存储单元，并设置各存储位置的地址向量，排序时移动地址向量，排序结束后，按地址向量中的值调准记录的位置东华理工学院程朋根10.2插入排序∑插入排序的基本思想是：每一趟将一个待排的记录，按其关键字的大小插入到已经排好的子文件中适当位置上，直到全部记录插入完成为止。∑常用的两种插入排序：¾直接插入排序、希尔排序东华理工学院程朋根∑1）直接插入排序¾基本思想：将一个记录插入到已排好序的有序表中，有n个记录的插入排序要进行n-1趟排

3、序；第i趟排序是在含有i-1个记录的有序表中插入第i个记录后变成含有i个记录的有序表东华理工学院程朋根直接插入排序算法10.1¾VoidInsertSort(SqList&L){//对顺序表L作直接插入排序。for(i=2;i<=L.length;++i)ifLT(L.r[i].key,L.r[i-1].key){//将L.r[i]插入有序子表L.r[0]=L.r[i];//复制为哨兵for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];//记录后移L.r[j+i]=L.r[0];//插入到正确位置}¾}//InsertS

4、ort东华理工学院程朋根∑时间复杂度：¾最好为正序，比较次数为n-1¾最坏为逆序，时间复杂度为∑i=(n+2)(n-1)/2;2¾平均约n/4¾时间复杂度为O(n2)东华理工学院程朋根折半插入排序10.2∑基本思想是在一个有序表中进行查找和插入¾VoidBInsertSort(SqList&L){//对顺序表L作折半插入顺序for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]Low=1;high=i-1;While(low<=high){//在r[low..high]中折半查找有序插入的位置m=(low+high)/2

5、;//折半ifLT(L.r[0].key,L.r[m].key)high=m-1;//插入点在低半区elselow=m+1;//插入点在高半区}//whilefor(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//插入}//for¾}//BInsertSort，时间复杂度为O(n2)东华理工学院程朋根∑2）希尔排序¾基本思想：选择一个记录间隔值d，把全部记录按此间隔值从第一记录起进行分组，所有相距为d的记录作为一组，先在各组内进行排序，然后缩小间距d重新分组，再进行组内排序，直到间隔值为１¾D的取值:d

6、=n/2;di+1=di/2东华理工学院程朋根希尔排序算法10.4~5¾VoidShellInsert(SqList&L,intdk){//对顺序表L作一趟希尔插入排序。本算法和一趟直接插入排序相比，作了以下修改：//1、前后记录位置的增量是dk，而不是1；//2、r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。for(i=dk+1;i<=L.length;++i)ifLT(L.r[i].key,L.r[i-dk].key){//需将L.r[i]插入有序增量子表L.r[0]=L.r[i];//暂存在L.r[0]for(j=i-dk;j>0&<(L.r[0].ke

7、y,L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];//记录后移，查找插入位置L.r[j+dk]=L.r[0];//插入}¾}//ShellInsert//跟算法10.1一致，只是j的步长为dk而不是1东华理工学院程朋根¾VoidShellSort(SqList&L,intdlta[],intt){//按增量序列dlta[0..t-1]对顺序表L作希尔排序。for(k=0;k