《数据结构教学课件:第九讲 内部排序1》由会员分享,可在线阅读,更多相关《数据结构教学课件:第九讲 内部排序1(24页珍藏版)》请在金锄头文库上搜索。
1、内部排序内部排序一、定义一、定义 (略)(略)二、相关术语二、相关术语是不是就是排序比较时要不要那个等号造成的?排序方法分类:排序方法分类:插入排序插入排序:直接插入排序,折半插入排序,希尔排序希尔排序交换排序:交换排序:冒泡排序,快速排序快速排序选择排序:选择排序:简单选择排序,堆排序堆排序归并排序归并排序基数排序基数排序还有上百种没有列入教材的算法例如:有30个同学的某门课成绩如下:78,89,65,89,66,98,81,71,69,73现在让你自己想个办法让它们从小到大排好序输出出来。有个人想了个办法这样:开一个有100个单元的数组,然后把30数据根据它们的数值,让对应单元加1For
2、I=1;I=30;I+; scanf(“%d”,x) ax+; 然后把数组里不等于0的地方输出出来,计数值是多少就输出几个这样做比我们知道的算法速度如何?直接插入排序直接插入排序初始状态:“58”已经是有序的,虽然只有一个数。初始:折半插入排序和直接插入原理相似,只是每次查找合适位置时采用的是折半查找的方法。意想不到的算法之一:希尔排序意想不到的算法之一:希尔排序例如:总表分成三个子表希尔排序实例希尔排序实例增量序列假设为增量序列假设为5,3,1组内实行直接插入排序缩小分组增量值每个组内进行直接插入排序最后,将分组增量值修改为1完全演变为直接插入排序明天,声明一个数组,循环输入数,用直接插入法排序后输出