数据结构 教学课件 作者 晋良颖 7.ppt

《数据结构 教学课件 作者 晋良颖 7.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第7章排序定义待排序的记录的类型如下：#defineN50/*待排序序列中记录的最大个数，可根据需要定义*/typedefstructnode{intkey;/*表示排序关键字*/elemtypeotheritem;/*代表待排序记录中的其他所有数据项*/}RECTYPE;7.1内排序7．1．1内排序的分类1、按排序过程中所需的工作量来分(设待排序结点总数为n)2、按排序过程中所依据的不同原则来分3、按是否改变结点的物理位置分退出图7-1开始排序前：（min，91），67，351，62，29，3

2、52，72，46，31，47，25，73……第一趟：（min，67，91），351，62，29，352，72，46，31，47，25，73……第二趟：（min，351，67，91），62，29，352，72，46，31，47，25，73……第三趟：（min，351，62，67，91），29，352，72，46，31，47，25，73……第四趟：（min，29，351，62，67，91），352，72，46，31，47，25，73……第五趟：（min，29，351，352，62，67，91），72

3、，46，31，47，25，73……第六趟：（min，29，351，352，62，67，72，91），46，31，47，25，73……算法7．1如书第206页所示算法7．2如书第207页所示下面是一组插入排序中，辅助地址表t[i]的变化实例（括号内的部分代表有序子表的地址集合）：i012345r[i].keymin4050201030t[i]0（1）2345初态t[i]0（12）第一趟，插入50t[i]0（312）第二趟，插入20t[i]0（4312）第三趟，插入10t[i]043512第四趟，插

4、入30由辅助地址表得到排序结果为：r[t[i]].keymin1020304050算法7．3如书第209页所示排序结束后，物理重排之前：i12345677r[i].key3514124226503117t[i]32857146i=1调整后：r[i].key1214174226353150t[i]12357648i=4调整后：r[i].key1214172631354250t[i]12345678算法7．4如书第210页所示7．1．3交换排序1、直接交换排序算法7．5如书第211页所示1、对直接交

5、换排序的改进考虑：算法7．6如书第212页所示图7-21、快排序图7-3算法7．7如书第215页所示算法7．8如书第215页所示7．1．4选择排序1、直接选择排序算法7．9如书第216页所示2、直接选择排序的改进考虑图7-41、堆排序图7-5算法7．10如书第221页所示算法7．11如书第221页所示图7-67．1．5合并排序图7-7、算法7．12如书第222页所示算法7．13如书第223页所示算法7．14如书第223页所示算法7．15如书第224页所示算法7．16如书第224页所示图7-8图7

6、-9算法7．17如书第226页所示算法7．18如书第227页所示算法7．19如书第228页所示图7-107．1．6计数排序算法7．20如书第230页所示算法7．21如书第230页所示图7-117．1．6基数排序图7-12图7-13算法7．22如书第234页所示图7-147．1．7各种内排序方法的比较讨论1、按时间复杂度分2、按空间复杂度分3、稳定性表7.17．2外排序7．2．1K路平衡归并总的时间为：s*（n-1）*（k-1）=logkm*（n-1）*（k-1）=logkm/log2k*（n-1

7、）*（k-1）图7-1510个初始归并段的三路平衡归并图7-16算法7．23如书第240页所示算法7．24如书第241页所示算法7．25如书第241页所示7．2．3置换-选择排序图7-177．2．3哈夫曼归并树图7-18图7-19