第三十四课：插入排序，快速排序（1）
时间：2010-09-21 来源：yuxinlen
第三十四课
本课主题： 插入排序，快速排序
教学目的： 掌握排序的基本概念，插入排序、快速排序的算法
教学重点： 插入排序、快速排序的算法
教学难点： 快速排序算法
授课内容：
一、排序概述
排序：将一个数据元素的无序序列重新排列成一个按关键字有序的序列。
|
姓名 |
年龄 |
体重 |
|
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 |
... |
|
相关阅读 更多 +
