Question

数据结构教程第三十四课插入排序，快速排序

Answer 1

教学目的： 掌握排序的基本概念，插入排序、快速排序的算法

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

教学难点： 快速排序算法

授课内容：

一、排序概述

排序：将一个数据元素的无序序列重新排列成一个按关键字有序的序列。

姓名 年龄 体重
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

四、总结

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

五、作业

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