数据结构-排序.ppt

《数据结构-排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构数据结构(C++语言版)--排序排序的基本概念1交换类排序33选择类排序34插入类排序32目录归并排序35小结36排序：将数据元素的一个任意序列，重新排列成一个按关键字有序的序列。概念例：将关键字序列：52,49,80,36,14,58,61,23调整为：14,23,36,49,52,58,61,80一般情况下，假设含n个记录的序列为{R1,R2,…,Rn}，其相应的关键字序列为{K1,K2,…,Kn}R1,R2,R3,R4,R5,R6,R7,R8K1,K2,K3,K4,K5,K6,K7,K8这些关键字相互之

2、间可以进行比较，即在它们之间存在着这样一个关系(在次讨论升序)：Kp1≤Kp2≤…≤KpnKp1≤Kp2≤Kp3≤Kp4≤Kp5≤Kp6≤Kp7≤Kp8按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…,Rpn}的操作称作排序。Rp1,Rp2,Rp3,Rp4,Rp5,Rp6,Rp7,Rp8若Ki为记录Ri的主关键字，则排序结果惟一。若Ki为记录Ri的次关键字，则排序结果可以不惟一（因为会有相同的关键字）。例：设排序前的关键字序列为：52,49,80,36,14,58,36,23若排序后的关键字序列为：14,23

3、,36,36,49,52,58,80，则排序方法是稳定的。若排序后的关键字序列为：14,23,36,36,49,52,58,80，则排序方法是不稳定的。内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序(本章不讨论)。内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列的过程。有序序列区无序序列区有序序列区无序序列区经过一趟排序排序方法分类：1)、插入排序：直接插入排序、折半插入排序、

4、希尔排序2)、交换排序：冒泡排序、快速排序3)、选择排序：简单选择排序、堆排序＊4)、归并排序：2-路归并排序＊5)、基数排序基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：依次将无序子序列中的一个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。通

5、过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。基数排序是一种基于多关键字排序的思想，将单关键字按基数分成“多关键字”进行排序的方法。排序的基本概念1交换类排序33选择类排序34插入类排序32目录归并排序35小结36插入排序一趟直接插入排序的基本思想：有序序列R[1..i-1]R[i]无序序列R[i..n]有序序列R[1..i]无序序列R[i+1..n]实现“一趟插入排序”可分三步进行：3．将R[i]插入（复制）到相应的位置上。2．记录后移一个位置；1．在有序区中查找R[i]的插入位置，简单排序

6、方法直接插入排序初始状态4938659776132749R0R1R2R3R4R5R6R7R8i=2i=33849659776132749i=43849659776132749i=5384965769713274976i=6384965769713274913i=7384965769713274927i=838496576971327494949386597761327493849387趟排序1趟排序2趟排序voidInsertSort(SqList&L){//对顺序表L作直接插入排序。for(i=2;i<=L.len

7、gth;++i)if(L.r[i].key

8、=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置比较次数和移动次数均约为：T(n)=O(n²)算法评价时间复杂度：比较次数：移动次数：0最好的情况：待排序记录按关键字从小到大排列（正序）比较次数：移动次数：最坏的情况：待排序记录按关键字从大到小排列（逆序）一般情况：待排序记录是随机的，取平均值。空间复杂度：S(n)