数据结构34a
上一篇 /
下一篇 2010-07-04 21:17:45
第三十四课
本课主题: 插入排序,快速排序
教学目的: 掌握排序的基本概念,插入排序、快速排序的算法
教学重点: 插入排序、快速排序的算法
教学难点: 快速排序算法
授课内容:
一、排序概述
排序:将一个数据元素的无序序列重新排列成一个按关键字有序的序列。
姓名
|
年龄
|
体重
|
1李由
|
57
|
62
|
2王天
|
54
|
76
|
3七大
|
24
|
75
|
4张强
|
24
|
72
|
5陈华
|
24
|
53
|
上表按年龄无序,如果按关键字年龄用某方法排序后得到下表:
姓名
|
年龄
|
体重
|
3七大
|
24
|
75
|
4张强
|
24
|
72
|
5陈华
|
24
|
53
|
2王天
|
54
|
76
|
1李由
|
57
|
62
|
注意反色的三条记录保持原有排列顺序,则称该排序方法是稳定的!
如果另一方法排序后得到下表:
姓名
|
年龄
|
体重
|
4张强
|
24
|
72
|
3七大
|
24
|
75
|
5陈华
|
24
|
53
|
2王天
|
54
|
76
|
1李由
|
57
|
62
|
原3,4,5记录顺序改
变,则称该排序方法是不稳定的!
内部排序:待排序记录存放在计算机随机存储器中进行的排序过程;
外部排序:待排序记录的数量很大,以致内存一次不能容纳全部记
录,在排序过程中尚需对外存进行访问的排序过程。
二、插入排序
1、直接插入排序
基本操作是将一个记录插入到已排好序的有序表中,从而得到一个新
的、记录数增1的有序表。排序过程:
38
|
49
|
65
|
97
|
76
|
13
|
27
|
49
|
...
|
|
38
|
49
|
65
|
76
|
97
|
13
|
27
|
49
|
...
|
|
13
|
38
|
49
|
65
|
76
|
97
|
27
|
49
|
...
|
|
13
|
27
|
38
|
49
|
65
|
76
|
97
|
49
|
...
|
|
13
|
27
|
38
|
49
|
49
|
65
|
76
|
97
|
...
|
|
2、折半插入排序
在直接插入排序中,为了找到插入位置,采用了顺序查找的方法。为
了提高查找速度,可以采用折半查找,这种排序称折半插入排序。
收藏
举报
TAG: