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

教学目的:掌握排序的基本概念，插入排序和快速排序算法。

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

教学难点:快速排序

教学内容:

一、分拣概述

排序:通过关键字将数据元素的无序序列重新排列成有序序列。

姓名和体重
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记录的顺序改了，据说排序方式不稳定！

内部排序:将待排序的记录存入计算机随机存取存储器的排序过程；

外部排序(External sorting):要排序的记录数量非常大，以至于内存无法一次容纳所有记录的排序过程，在排序过程中需要访问外部内存。

二、插入排序
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，双向插入排序

为了减少排序过程中移动记录的次数，在半插入排序的基础上进行改进:

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

第三，快速排序

1.气泡分类

首先，比较第一条记录的关键字和第二条记录的关键字。如果是逆序，就把两条记录交换一下，然后把第二条记录的关键词和第三条记录的关键词进行比较。直到第n-1条记录和第n条记录的关键字被比较。

然后，执行第二次冒泡排序，并对前n-1条记录执行同样的操作。

...直到某个排序过程中没有记录交换操作。

第一次旅行，第二次旅行快速分类

通过一遍排序将待排序的记录分成两个独立的部分，其中一部分记录的关键字小于另一部分的关键字，这样就可以连续对这两部分记录进行排序，达到整个序列的顺序。

关键字49 38 65 97 76 13 27 49
I J J
经过1次交换27 38 65 97 76 13 49
I J
经过2次交换27 38 97 76 13 65 49
I J J J
经过3次交换27 38 13 97 76 65 49
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

四。摘要

几种类型的简单分析和比较。(时间，复杂度在空)之间

动词 （verb的缩写）家庭作业

实现直插排序、冒泡排序、快速排序。