论坛交流
首页办公自动化| 网页制作| 平面设计| 动画制作| 数据库开发| 程序设计| 全部视频教程
应用视频: Windows | Word2007 | Excel2007 | PowerPoint2007 | Dreamweaver 8 | Fireworks 8 | Flash 8 | Photoshop cs | CorelDraw 12
编程视频: C语言视频教程 | HTML | Div+Css布局 | Javascript | Access数据库 | Asp | Sql Server数据库Asp.net  | Flash AS
当前位置 > 文字教程 > C语言程序设计教程
Tag:新手,函数,指针,数据类型,对象,Turbo,入门,运算符,数组,结构,二级,,tc,游戏,试题,问答,编译,视频教程

插入排序,快速排序

文章类别:C语言程序设计 | 发表日期:2008-9-24 14:45:57

本课主题: 插入排序,快速排序

教学目的: 把握排序的基本概念,插入排序、快速排序的算法

教学重点: 插入排序、快速排序的算法

教学难点: 快速排序算法

授课内容:

一、排序概述

排序:将一个数据元素的无序序列重新排列成一个按要害字有序的序列。

姓名

年龄

体重

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、折半插入排序

在直接插入排序中,为了找到插入位置,采用了顺序查找的方法。为了提高查找速度,可以采用折半查找,这种排序称折半插入排序。

3、2-路插入排序

为减少排序过程中移动记录的次数,在折半插入排序的基础上加以改进:

49

38

65

97

78

13

27

49

...

 


i=1

49

 

 

 

 

 

 

 

 

first

 

 

 

 

 

 

 

i=2

49

 

 

 

 

 

 

38

 

final

 

 

 

 

 

 

first

i=3

49

65

 

 

 

 

 

38

 

 

final

 

 

 

 

 

first

i=4

49

65

97

 

 

 

 

38

 

 

 

final

 

 

 

 

first

i=5

49

65

76

97

 

 

 

38

 

 

 

 

final

 

 

 

first

i=6

49

65

76

97

 

 

13

38

 

 

 

 

final

 

 

first

 

i=7

49

65

76

97

 

13

27

38

 

 

 

 

final

 

first

 

 

i=8

49

49

65

76

97

13

27

38

 

 

 

 

 

final

first

 

 

三、快速排序

1、起泡排序

首先将第一个记录的要害字和第二个记录的要害字进行比较,若为逆序,则将两个记录交换之,然后比较第二个记录和第三个记录的要害字。直至第n-1个记录和第n个记录的要害字进行过比较为止。

然后进行第二趟起泡排序,对前n-1个记录进行同样操作。

...直到在某趟排序过程中没有进行过交换记录的操作为止。

49

38

38

38

38

13

13

38

49

49

49

13

27

27

65

65

65

13

27

38

38

97

76

13

27

49

49

 

76

13

27

49

49

 

 

13

27

49

65

 

 

 

27

49

78

 

 

 

 

49

97

 

 

 

 

 

初始

第一趟

第二趟

第三趟

第四趟

第五趟

第六趟

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

 

 

 

 

 

 

 

 

 

 

四、总结

几种排序的简单分析与比较。(时间、空间复杂度)

五、作业

实现直接插入排序、起泡排序、快速排序算法。

视频教程列表
文章教程搜索
 
C语言程序设计推荐教程
C语言程序设计热门教程
看全部视频教程
购买方式/价格
购买视频教程: 咨询客服
tel:15972130058