10_新教案第十章内部排序概论.ppt

下载文档 降价啦

3
0
约6.14千字
约 31页
2017-03-16 发布于湖北
举报
版权申诉
保障服务

10_新教案第十章内部排序概论.ppt

1、本文档共31页，可阅读全部内容。
2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。

10_新教案第十章内部排序概论

* * 10.1 概述 10.2 插入排序 10.2.1 直接插入排序 10.2.2 希尔排序 10.3 交换排序 10.3.1 起泡排序 10.3.2 快速排序第十章内部排序 10.5 归并排序 10.4 选择排序 10.4.1 简单选择排序 10.4.2 堆排序基本术语将一个数据元素(记录)的任意序列,重新排列成一个按关键字有序的序列。 - 排序 - 稳定性内部排序/外部排序基本操作 - 约定 ● 概述关键字相同的记录在排序过程中是否保持前后次序不变。排序过程全在内存中进行 (1)比较关键字的大小;(2)移动记录。 #define MAXSIZE 20 typedef int KeyType; typedef struct{ KeyType key; InfoType otherinfo; }RedType; typedef struct{ RedType r[MAXSIZE+1]; int length; }SqList; 10.2 插入排序直接插入排序 ● 直接插入排序 ●基本思想:每次将一个记录插入到已排好序的有序表中,直到记录全部插入为止。例1:已知待排序的记录的初始排列如下 R(49), R(38), R(65), R(97), R(76) ,R(13), R(27), R(49*) R(49) R(38) R(49) R(38) R(49) R(65) R(38) R(49) R(65) R(97) R(38) R(49) R(65) R(76) R(97) R(13) R(38) R(49) R(65) R(76) R(97) R(13) R(27) R(38) R(49) R(65) R(76) R(97) R(13) R(27) R(38) R(49) R(49*) R(65) R(76) R(97) 10.2 插入排序算法 ● 直接插入排序 ●算法 void InsertSort(SqList L) { for(i=2;i=L.length;++i) if LT(L.r[i].key, L.r[i-1].key){ 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+1]=L.r[0]; } } 例子 R(49) [0] [1] [2] [3] [4] [5] [6] [7] [8] R(49) R(38) R(65) R(97) R(76) R(13) R(27) R(49*) 2 3 4 5 6 7 8 R(49) R(38) R(65) R(97) R(76) R(13) R(27) R(49*) R(38) R(49) R(38) R(49) R(65) R(97) R(76) R(13) R(27) R(49*) R(65) R(49) R(38) R(49) R(65) R(97) R(76) R(13) R(27) R(49*) R(97) R(49) R(38) R(49) R(65) R(76) R(97) R(13) R(27) R(49*) R(76) R(49) R(13) R(38) R(49) R(65) R(76) R(97) R(27) R(49*) R(13) R(49) R(13) R(27) R(38) R(49) R(65) R(76) R(97) R(49*) R(27) R(49) R(13) R(27) R(38) R(49) R(49*) R(65) R(76) R(97) R(49*) R(49) R(49) R(65) R(97) R(76) R(13) R(27) R(49*) R(38) R(38) R(49) R(65) R(97) R(76) R(13) R(27) R(49*) R(38) i 稳定的排序方法 10.2 插入排序算法效率