数据结构34c-35
上一篇 /
下一篇 2010-07-04 21:26:58
2、快速排序
通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关
键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
初始关键字 | 49 | 38 | 65 | 97 | 76 | 13 | 27 | 49 |
| i | | | | | | j | j |
1次交换之后 | 27 | 38 | 65 | 97 | 76 | 13 | | 49 |
| i | | i | | | | j | |
2次交换之后 | 27 | 38 | | 97 | 76 | 13 | 65 | 49 |
| | | i | | | j | j | |
3次交换之后 | 27 | 38 | 13 | 97 | 76 | | 65 | 49 |
| | | i | i | | j | | |
4次交换之后 | 27 | 38 | 13 | | 76 | 97 | 65 | 49 |
| | | | ij | | j | | |
完成一趟排序 | 27 | 38 | 13 | 49 | 76 | 97 | 65 | 49 |
| | | | | | | | |
初始状态 | 49 | 38 | 65 | 97 | 76 | 13 | 27 | 49 |
一次划分 | 27 | 38 | 13 | 49 | 76 | 97 | 65 | 49 |
分别进行 | 13 | 27 | 38 | | | | | |
| 结束 | | 结束 | | 49 | 65 | 76 | 97 |
| | | | | 49 | 65 | | 结束 |
| | | | | | 结束 | | |
有序序列 | 13 | 27 | 38 | 49 | 49 | 65 | 76 | 97 |
| | | | | | | | |
四、总结
几种排序的简单分析与比较。(时间、空间复杂度)
五、作业
实现直接插入排序、起泡排序、快速排序算法。
回目录上一课下一课
第三十五
课
本课主题:实验七 查找
教学目的:练习顺序查找、折半查找及二叉排序树的实现
教学重点:
教学难点:
授课内容:
顺序查找
折半查找
顺序查找及折半查找
示例
二叉排序树
示例
回目录上一课下一课
收藏
举报
TAG: