数据结构 第10 章 排序

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

1、内部排序教学内容1、插入排序（直接插入排序、折半插入排序、希尔排序）；2、交换排序（起泡排序、快速排序）；3、选择排序（直接选择排序、堆排序）；4、归并排序；5、基数排序；排序：将数据元素的一个任意序列，重新排列成一个按关键字有序的序列。10.1概述例：将关键字序列：52,49,80,36,14,58,61,23调整为：14,23,36,49,52,58,61,80若按主关键字排序则结果惟一。若按次关键字排序则结果可以不惟一（因有相同关键字）。设Ki、Kj(1≤i≤n,1≤j≤n,i≠j)分别为记录Ri、Rj的关键字，且Ki=Kj，在排序

2、前的序列中Ri领先于Rj（即i

3、中完成，则称此类排序问题为外部排序。排序方法分类：1)、插入排序：直接插入排序、折半插入排序、希尔排序2)、交换排序：冒泡排序、快速排序3)、选择排序：简单选择排序、堆排序4)、归并排序：2-路归并排序5)、基数排序10.2插入排序有序序列R[1..i-1]R[i]无序序列R[i..n]一趟直接插入排序的基本思想：有序序列R[1..i]无序序列R[i+1..n]实现“一趟插入排序”可分三步进行：3．将R[i]插入（复制）到R[j+1]的位置上。2．将R[j+1..i-1]中的所有记录均后移一个位置；1．在R[1..i-1]中查找R[i]的

4、插入位置，R[1..j].keyR[i].key

5、&L){//对顺序表L作直接插入排序。for(i=2;i<=L.length;++i)if(L.r[i].key

6、

7、SqList&L){for(i=2;i<=L.length;++i){L.r[0]=L.r[i];low=1;high=i-1;while(low<=high){m=(low+high)/2;//折半if(L.r[0].key=high+1;--j)L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//插入}//for}//BInsertSorti=1(30)1370853942620i=76(6133

8、039427085)20…i=820(6133039427085)20lhmmi=820(6133039427085)20lhi=820(6133039427085)20lhi=820(613