数据结构教程第三十四课插入排序，快速排序
敬业的IT人
互联网
佚名
2008-1-4 15:24:38
教学目的： 掌握排序的基本概念，插入排序、快速排序的算法
教学重点： 插入排序、快速排序的算法
教学难点： 快速排序算法
授课内容：
一、排序概述
排序：将一个数据元素的无序序列重新排列成一个按关键字有序的序列。
姓名年龄体重1李由57622王天54763七大24754张强24725陈华2453上表按年龄无序，如果按关键字年龄用某方法排序后得到下表：
姓名年龄体重3七大24754张强24725陈华24532王天54761李由5762注意反色的三条记录保持原有排列顺序，则称该排序方法是稳定的！
如果另一方法排序后得到下表：
姓名年龄体重4张强24723七大24755陈华24532王天54761李由5762原3,4,5记录顺序改变，则称该排序方法是不稳定的！
内部排序：待排序记录存放在计算机随机存储器中进行的排序过程；
外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
二、插入排序
1、直接插入排序
基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。排序过程：
3849659776132749...
3849657697132749...
1338496576972749...
1327384965769749...
1327384949657697...2、折半插入排序
在直接插入排序中，为了找到插入位置，采用了顺序查找的方法。为了提高查找速度，可以采用折半查找，这种排序称折半插入排序。
3、2－路插入排序
为减少排序过程中移动记录的次数，在折半插入排序的基础上加以改进：
4938659778132749...
i=149 first i=249 38 final firsti=34965 38 final firsti=4496597 38 final firsti=549657697 38 final firsti=649657697 1338 final first i=749657697 132738 final first i=84949657697132738 finalfirst
三、快速排序
1、起泡排序
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。直至第n-1个记录和第n个记录的关键字进行过比较为止。
然后进行第二趟起泡排序，对前n-1个记录进行同样操作。
...直到在某趟排序过程中没有进行过交换记录的操作为止。
493838383813133849494913272765656513273838977613274949 7613274949 13274965 274978 4997 初始第一趟第二趟第三趟第四趟第五趟第六趟2、快速排序
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
初始关键字4938659776132749 i jj1次交换之后273865977613 49 i i j 2次交换之后2738 9776136549 i jj 3次交换之后2738139776 6549 ii j 4次交换之后273813 76976549 ij j 完成一趟排序2738134976976549 初始状态4938659776132749一次划分2738134976976549分别进行132738 结束 结束 49657697 4965 结束 结束 有序序列1327384949657697
四、总结
几种排序的简单分析与比较。（时间、空间复杂度）
五、作业
实现直接插入排序、起泡排序、快速排序算法。
- 最新文章
- 数据结构教程第三十五课实验七查找[01-04]
- 数据结构教程第三十六课选择排序，归并排序[01-04]
- 数据结构教程第三十七课实验八排序实验[01-04]
- 数据结构教程第三十八课文件概念，顺序文件[01-04]
- 数据结构教程第三十九课索引文件[01-04]
- 无向图转换[01-04]
- 相关文章
