08级第10章排序A【荐】.pptVIP

实验三 排序和查找 第10章 内部排序 10.1 概述 4. 什么叫内部排序？什么叫外部排序？ 6. 顺序存储（顺序表）的抽象数据类型如何表示？ 7. 内部排序的算法有哪些？ 10.2 插入排序 1) 直接插入排序 例1：关键字序列T= （21，25，49，25*，16，08），请写出直接插入排序的具体实现过程。 直接插入排序算法的实现： 2） 折半插入排序 3） 2-路插入排序 4）表插入排序 例：关键字序列 T=(21，25，49，25*，16，08）， 请写出表插入排序的具体实现过程。 表插入排序的算法 表插入排序算法分析： 5）希尔（shell）排序 例：关键字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04），请写出希尔排序的具体实现过程。 时间效率： 原始序列： 256，301，751，129，937，863，742，694，076，438 希尔排序算法（其中某一趟的排序操作） 对前页程序中间for循环的理解： 10.3 交换排序 1) 冒泡排序 冒泡排序的算法分析 * 第9章? 作业 9.3 9.8 9.31 9.33 （周二交） 第10章作业预告： 10.1 10.6 10.8 10.25 10.42 实验报告：18周五截止 第3次上机时间：下周四晚（12月17号） 自行设计一个方案来体现排序及查找功能。 写成“实验指导书”的形式网上或邮件提交 例1：02级通2王道新：日程安排管理程序 例2：02级通5莫劲夫：歌词有哪些信誉好的足球投注网站 例3：02级通2余蕾： 个人理财管理 关于实验报告要求： ①参加“种子杯”比赛的同学，可以用赛题撰写报告； 其他同学建议以 “Huffman编/译码器的设计与实现”或接近商业软件的内容为主题撰写报告。 ②交报告截止时间：18周五之前按班提交打印的纸质文档给任课教师； ③ 报告格式请按严蔚敏习题集P75的“实习报告规范”撰写； 正文一律用小四号仿宋，附录源码一律用5号或小五号字体； 文档封面一律用： 《数据结构》课程实验报告 题目：XXXXXX 班级： 姓名： 学号： 指导教师： 华中科技大学电信系 2009年12月 10.1 概述 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 1. 什么是排序？ 将一组杂乱无章的数据按一定的规律顺次排列起来。 2. 排序的目的是什么？ 存放在数据表中 按关键字排序 3.排序算法的好坏如何衡量？ 时间效率——排序速度（即排序所花费的全部比较次数） 空间效率——占内存辅助空间的大小 稳定性——若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。 ——便于查找！ ——若待排序记录都在内存中，称为内部排序； ——若待排序记录一部分在内存，一部分在外存，则称为外部排序。 注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。 5.待排序记录在内存中怎样存储和处理？ ① 顺序排序——排序时直接移动记录； ② 链表排序——排序时只移动指针； ③ 地址排序——排序时先移动地址，最后再移动记录。 注：地址排序中可以增设一维数组来专门存放记录的地址。 注：大多数排序算法都是针对顺序表结构的(便于直接移动元素) Typedef struct { //定义每个记录（数据元素）的结构 KeyType key ; //关键字 InfoType otherinfo; //其它数据项 }RecordType，node ; //例如node.key表示其中一个分量 Typedef struct { //定义顺序表L的结构 RecordType r [ MAXSIZE +1 ]; //存储顺序表的向量 //r[0]一般作哨兵或缓冲区 int length ; //顺序表的长度 }SqList ,L; //例如L.r或L.length表示其中一个分量 # define MAXSIZE 20 //设记录数不超过20个（本章都如此假设） typedef int KeyType ; //设关键字为整型量（int型） 若r数组是表L中的一个分量且为node类型， 则r中某元素的key分量表示为：r[i].key