数据结构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:

 

评分:0

我来说两句

日历

« 2024-03-28  
     12
3456789
10111213141516
17181920212223
24252627282930
31      

数据统计

  • 访问量: 18517
  • 日志数: 51
  • 建立时间: 2009-04-22
  • 更新时间: 2010-12-09

RSS订阅

Open Toolbar