数据结构第九章内部排序资料.ppt

第九章 内部排序;　　将n个性质相同的数据元素按关键字值从小到大或从大 到小排为有序序列。;　注意 　　当按次关键字进行排序时，由于可能存在关键字值相同 的元素，因而排序结果不惟一。;　举例;　举例;　插入排序;　简单的内部排序法　　O(n2);　折半插入排序法;　　设对数据元素序列R1,R2,…,Rn进行排序，则：;⑵依次逐个将Ri（i=2,3,…,n）插入已有的按关键字值有序;⑵依次逐个将Ri（i=2,3,…,n）插入已有的按关键字值有序;⑵依次逐个将Ri（i=2,3,…,n）插入已有的按关键字值有序;⑵依次逐个将Ri（i=2,3,…,n）插入已有的按关键字值有序;⑵依次逐个将Ri（i=2,3,…,n）插入已有的按关键字值有序;⑵依次逐个将Ri（i=2,3,…,n）插入已有的按关键字值有序;⑵依次逐个将Ri（i=2,3,…,n）插入已有的按关键字值有序;49;　算法;　　}//if;　　　　　　元素的移动，最少　次，最多　　次。;并??要　　　　的辅助存储空间。;　改进思路;　　在直接插入排序法中，关键字值间的比较主要用于确定;　举例;　　与直接插入排序法相比，折半插入排序法减少了关键字;　　直接插入排序法在待排数据元素个数较少时效率较高，;⑴设置辅助数组sorted[n]，将R1保存至sorted[0]；;　举例;　举例;　举例;　举例;　举例;　举例;　举例;　　与直接插入排序法相比，二路插入排序法中关键字值间;　　如果在插入的过程中不改变数据元素的存储位置，则不;⑴设置辅助数组addr[n+1]，其中addr[0]记录结果序列中排;　入过程中不对数据元素进行移动，而只改变addr数组中相;　举例;　举例;　举例;　举例;　举例;　举例;　举例;　举例;　举例;　　与直接插入排序法相比，表插入排序法通过修改2n次指;插入排序，待整个序列中的元素基本有序时，再对全体元素;　举例;　举例;　举例;　举例;　举例;　举例;　举例;　举例;　举例;　举例;　举例;　举例;　　在希尔排序中，关键字较小的元素能跳跃式地前移，从;　快速排序法;⑴对相邻的两个数据元素的关键字值进行比较，若为逆序，;　举例;　举例;三趟;四趟;五趟;六趟;　　　　　　元素的移动，最少　次，最多　　　次。;并需要　　　　的辅助存储空间。;⑴若s=t ，即序列中仅一个元素，则排序完成；;　键字值的元素，若该元素在枢轴之后，则交换两者位置；;　值的元素，若该元素在枢轴之前，则交换两者位置；;49;49;49;49;则可减少元素移动次数。;49;　算法;　　st[high]=st[low];;　if (lowhigh){;　QSort(st,1,LENGTH);;　　快速排序法平均时间复杂度为O(knlogn)，经验证明，;　树形选择排序法;n-i+1 (i=1,…,n-1) 个元素中选择一个关键字值最小的，;　举例;　举例;　举例;　举例;　举例;　举例;　举例;　举例;　举例;键字值间的比较，　　　次元素的移动。;空间。;⑴先对n个元素的关键字值进行两两比较，然后在其中的;　举例;　举例;　中的对应关键字值改为∞，并修改从该结点到根的路径上;　举例;　举例;∞;∞;∞;∞;∞;　　由此可见，树形选择排序的时间复杂度为O(nlogn)，;⑴将含n个待排元素的初始序列看作一棵完全二叉树的层序;将该元素的关键字值与其左、右孩子的关键字值进;　举例;　举例;　举例;　进行“筛选”，使剩余元素重又构成一个大顶堆；;　举例;　举例;　举例;　举例;　举例;　举例;　举例;49;　算法;　　　if(jmst[j+1].keyst[j].key){//右孩子键值更大;　　　if(jmst[j+1].keyst[0].key){//右孩子键值较大;　for(i=LENGTH/2;i=1;--i);　　堆排序法的时间主要用于反复筛选，除构造初始堆外，;　多路归并排序法;⑴对数据元素序列R1,…,R ?n/2?进行排序；;　举例;　举例;　举例;　举例;49;⑴对st[1..m]排序，m=LENGTH/2；;　思路细化;⑴设置辅助数组temp；;　算法;void Merge(SortTable st,int i,int j,int k){;　　　　　　　　　　　　　　　　　　　　　　　元素的;　　排序有时也会按多 个关键字值进行！;　举例;　　可能的排序结果有两种：;问题：;　以前我常用的排序方法;　以前我常用的排序方法;　以前我常用的排序方法;　以前我常用的排序方法;　以前我常用的排序方法;　以前我常用的排序方法;　以前我常用的排序方法;　以前我常用的排序方法;　以前我常用的排序方法;　以前我常用的排序方法;　以前我常用的排序方法;　以前我常用的排序方法;　以前我常用的排序方