排序计算机软件基础
4.5 直接插入排序
4.6 交换排序
4.7 选择排序
4.8 多关键字排序
主要内容：
教学目的与要求通过本部分相关内容的学习，使同学们熟练掌握几种排序的思想及算法的具体实现；了解每种算法的各种性能；根据具体问题的实际情况，能选择合适的排序算法进行排序。
本节课内容的说明
内容,直接 插入排序、交换排序
要求,掌握两种排序的基本思想及算法实现，
了解两种排序算法各自的主要性能指标。
重点,两种排序的基本思想及算法实现。
难点,稳定性的概念、排序算法的具体实现。
一,基本思想将整个数据表（ n个记录）看成是由无序表和有序表两个部分组成，每趟排序时将无序表中的一个记录插入到有序表中的恰当位置，最终使整个数据表有序排列。
个记录插入到有序表 的恰当位置 。初始状态时，有序表中仅有第一个记录，排序共需进行 n-1趟，最终使整个数据表有序排列。
4.5 直接插入排序
1．如果有 n个元素，初始状态下有序表中多少个元素，无序表中多少个元素？
2．如果有 n个元素，最多需要多少趟的插入操作？
开动脑筋
知识回顾
设有一个有序排列的整型顺序线性表 a，任意给定一个元素 x，将其插入到线性表 a中，
使得其依然有序。
找到插入位置，元素后移，插入元素，表长加 1
线性表,2,4,6,8,10
插入 7,i
从后往前找找位置的同时，元素后移
，,6，
：
10，8，，
i
7
计算机软件基础
例,对于关键字序列 {38,20,46,38,74,91，
12,25}进行直接插入排序，写出排序过程中每趟排序的结果。
初始状态 [38] [20 46 38 74 91 12 25]

计算机软件基础
例,对于关键字序列 {38,20,46,38,74,91，
12,25}进行直接插入排序，写出排序过程中每趟排序的结果。
初始状态 [38] [20 46 38 74 91 12 25]
第一趟 [20 38] [46 38 74 91 12 25]

第一趟排序详细过程计算机软件基础
例,对于关键字序列 {38,20,46,38,74,91，
12,25}进行直接插入排序，写出排序过程中每趟排序的结果。
初始状态 [38] [20 46 38 74 91 12 25]
第一趟 [20 38] [46 38 74 91 12 25]
第二趟 [20 38 46] [38 74 91 12 25]

第二趟排序详细过程计算机软件基础
例,对于关键字序列 {38,20,46,38,74,91，
12,25}进行直接插入排序，写出排序过程中每趟排序的结果。
初始状态 [38] [20 46 38 74 91 12 25]
第一趟 [20 38] [46 38 74 91 12 25]
第二趟 [20 38 46] [38 74 91 12 25]
第三趟 [20 38 38 46] [74 91 12 25]

第三趟排序详细过程计算机软件基础
例,对于关键字序列 {38,20,46,38,74,91，
12,25}进行直接插入排序，写出排序过程中每趟排序的结果。
初始状态 [38] [20 46 38 74 91 12 25]
第一趟 [20 38] [46 38 74 91 12 25]
第二趟 [20 38 46] [38 74 91 12 25]
第三趟 [20 38 38 46] [74 91 12 25]
第四趟 [20 38 38 46 74] [91 12 25]

计算机软件基础
例,对于关键字序列 {38,20,46,38,74,91，
12,25}进行直接插入排序，写出排序过程中每趟排序的结果。
初始状态 [38] [20 46 38 74 91 12 25]
第一趟 [20 38] [46 38 74 91 12 25]
第二趟 [20 38 46] [38 74 91 12 25]
第三趟 [20 38 38 46] [74 91 12 25]
第四趟 [20 38 38 46 74] [91 12 25]
第五趟 [20 38 38 46 74 91] [12 25]

计算机软件基础
例,对于关键字序列 {38,20,46,38,74,91，
12,25}进行直接插入排序，写出排序过程中每趟排序的结果。
初始状态 [38] [20 46 38 74 91 12 25]
第一趟 [20 38] [46 38 74 91 12 25]
第二趟 [20 38 46] [38 74 91 12 25]
第三趟 [20 38 38 46] [74 91 12 25]
第四趟 [20 38 38 46 74] [91 12 25]
第五趟 [20 38 38 46 74 91] [12 25]
第六趟 [12 20 38 38 46 74 91] [25]

计算机软件基础
例,对于关键字序列 {38,20,46,38,74,91，
12,25}进行直接插入排序，写出排序过程中每趟排序的结果。
初始状态 [38] [20 46 38 74 91 12 25]
第一趟 [20 38] [46 38 74 91 12 25]
第二趟 [20 38 46] [38 74 91 12 25]
第三趟 [20 38 38 46] [74 91 12 25]
第四趟 [20 38 38 46 74] [91 12 25]
第五趟 [20 38 38 46 74 91] [12 25]
第六趟 [12 20 38 38 46 74 91] [25]
第七趟 [12 20 25 38 38 46 74 91]

某趟排序，将 list[i]插入 有序表 list[1]~list[i-1]中。
计算机软件基础二,算法描述
算法功能,实现将一个长度为 n的线性表 list上的所有元素按关键字升序排列。
void insertsort (ElemType list[],int n)
{int i,j;
for (i=2;i<=n;i++) /*外循环控制排序的总趟数 */
{ list[0]=list[i];
j=i-1;
while (list[0].key< list[j].key)
/*在有序表中寻找插入位置 */
{ list[j+1]=list[j];
j--;
}
list[j+1]=list[0];
}
} /*insersort*/
//第 i趟排序所做的操作
li
j i-1;
il (list[0].ke list[j].k )
/*在有序表中寻找插入位置 */
{ li t[j 1] list[j];
j--;
}
li t[j+1] li t[0];
}
list[0]的作用用于 保存 待插记录 list[i]的值，以免在后移过程中被覆盖而丢失。
作为,监视哨,，防止数组下标越界。
0 1 2 3 4 5 6 7 8
12 20 38 38 46 74 91 12 25
稳定性,稳定的
时间复杂度,Ｏ (n2)
最快的情况,正序
最慢的情况,逆序三,算法分析
4.6 交换排序交换排序是通过对数据表中的记录进行两两比较,次序不符合要求就交换的方法实现数据表的有序排列 。
目前有两种较为常用的交换排序方法：冒泡排序和快速排序 。 本节重点介绍 其中的冒泡排序方法 。
计算机软件基础

一,基本思想将待排序的 n个记录看作按纵向排列，每趟排序时 自下至上 对排序范围中每对相邻记录进行比较
，若次序不符合要求（逆序）就交换。每趟排序结束时都能使排序范围内关键字 最 小 的记录象气泡一样,冒”（上升）到表上端 的对应位置。重复此过程，依次将关键字最小、次小、第三小 … 的各个记录“冒”到表上端的第一个、第二个、第三个,…
位置上，直至整个表有序排列。
4.6.1 冒泡排序计算机软件基础

注：在关键字序列中存在两个相同的关键字 38，
因此在后面一个 38的下面加下划线以示区别。注意通过此实例分析排序方法的稳定性,
例 1,对关键字序列 {91,38,20,46,38,74,12}
进行冒泡排序，写出排序过程中每趟排序的结果。
冒泡排序示例 ----以升序为例第一趟
91
38
20
46
38
74
12i
12
20
12
91
12
74
12
38
46
38
12
12
12
74
38
46
20
38
91
12
46
38
38
i
20
20 3891
第二趟 第三趟
12
74
46
38
20
91
38
第四趟
12
74
46
91
20
38
38
第五趟
12
74
91
46
20
38
38
第六趟
12
91
74
46
20
38
n~2 n~4n~3 n~6n~5 n~7
计算机软件基础思考：冒泡排序算法的稳定性如何？
结论：对于任意一组记录，经验证都可以得到与上例相同的结果。故冒泡排序算法具有稳定性。
分析：两个 38排序前和排序后的相对次序没有发生变化。

排序过程分析：
第 1趟：将第 n个到第 2个元素和其前面的元素比较，若逆序则进行交换；
第 2趟：将第 n个到第 3个元素和其前面的元素比较，若逆序则进行交换；
……………….
第 i趟：将第 n个到第 i+1个元素和其前面的元素比较，若逆序则进行交换；
若数据表中共有 n个元素，最多需进行 n-1趟排序。
计算机软件基础二,算法描述下面的冒泡排序算法实现将一个长度为 n的线性表 list上的所有元素按关键字升序排列。
void bubblesort(ElemType list[],int n)
{int i,j;
list temp;
for(i=1;i<n;i++) //外循环控制排序的总趟数
for(j=n;j>i;j--) //内循环控制一趟排序的进行
if(list[j].key< list[j-1].key)
//相邻元素比较,若逆序就交换
{temp= list[j];
list[j]= list[j-1];
list[j-1]=temp;
}
} /*bubblesort*/
计算机软件基础例 2,对于关键字序列 {38,20,46,38,74,91,12，
25}进行冒泡排序，写出排序过程中每趟排序的结果。
初态 第 1趟 第 2趟 第 3趟 第 4趟 第 5趟 第 6趟 第 7趟
38 12 12 12 12 12 12 12
20 38 20 20 20 20 20 20
46 20 38 25 25 25 25 25
38 46 25 38 38 38 38 38
74 38 46 38 38 38 38 38
91 74 38 46 46 46 46 46
12 91 74 74 74 74 74 74
25 25 91 91 91 91 91 91

问题：排序进行到 3趟后，整个数据表即已经有序排列。后面的各趟排序还有必要进行吗？
计算机软件基础
分析：
算法的缺陷：
在数据表已排列有序的情况下,不能提前结束排序过程 。
解决办法,
在冒泡排序算法中加入一个 flag标志 变量控制在数据表已经有序的情况下提前结束排序 。
flag=1 表明数据表 无序,下一趟排序仍需进行
flag=0 表明数据表 有序,排序过程应结束

问题：如何让 flag变量的值正确反映数据表的状态？
1,flag的初值应如何正确设置？
2,当某趟排序结束时，如何确定数据表的最新状态（有序 /无序）？
flag的 初值 应置为 1，保证排序第一趟顺利进行；
若某趟排序过程未发生任何一次逆序交换的操作，
则表明数据表所有记录的顺序均符合要求，即数据表有序 （ flag的值应为 0） ；否则，说明数据表仍无序 （ flag
的值应为 1）,下一趟排序仍需进行。

计算机软件基础计算机软件基础
void bubblesort(ElemType list[],int n)
{int i,j,flag; //加入 flag变量用于控制排序的趟数
ElemType temp;
i=1;
while //外循环控制排序的总趟数
{
for(j=n;j>i;j--) //内循环控制一趟排序的进行
if(list[j].key<list[j-1].key) //相邻元素进行比较,逆序就交换
{
temp=list[j];
list[j]=list[j-1];
list[j-1]=temp; }
i++;}
} /*bubblesort*/
改进后的冒泡排序算法：

flag=1;
flag=0;
flag=1;
((i<n)&&(flag==1))
冒泡排序算法的执行效率与数据表的初态有关。当数据表初态升序排列时效率最高，排序只需进行一趟，
时间复杂度为 O(n)；当数据表初态降序排列时效率最低，
需进行 n-1趟排序且每次比较都要进行交换，时间复杂度为 O(n2)。
经证明，冒泡排序算法具有 稳定性,其平均时间复杂度为 O(n2)。
三,算法分析

计算机软件基础
课后思考题：
能否对改进后的冒泡排序算法进一步地进行优化，使之执行效率更高？
提示：
传统的冒泡排序算法中，经过每一趟排序，待排记录范围都 只是缩减 1个记录 。但实际上，有的时候经过一趟排序待排记录范围可以缩减不止 1个记录的位置。
在一趟冒泡的过程中，有可能只是在 待排序范围的后端进行记录的交换，而其前端记录已经按关键字有序排列，
由此可以在算法中设置一个指示,最后一个进行交换的记录的位置 "的变量。
计算机软件基础
1
2
3
4
7
5
8
6
初态计算机软件基础
1
2
3
4
7
5
8
6
1
2
3
4
7
5
8
6
初态 第 1趟计算机软件基础
1
2
3
4
7
5
6
8
1
2
3
4
7
5
8
6
初态 第 1趟计算机软件基础
1
2
3
4
7
5
6
8
1
2
3
4
7
5
8
6
初态 第 1趟计算机软件基础
1
2
3
4
7
5
6
8
1
2
3
4
7
5
8
6
初态 第 1趟计算机软件基础
1
2
3
4
5
7
6
8
1
2
3
4
7
5
8
6
初态 第 1趟计算机软件基础
1
2
3
4
5
7
6
8
1
2
3
4
7
5
8
6
初态 第 1趟计算机软件基础
1
2
3
4
5
7
6
8
1
2
3
4
7
5
8
6
初态 第 1趟计算机软件基础
1
2
3
4
5
7
6
8
1
2
3
4
7
5
8
6
初态 第 1趟计算机软件基础
1
2
3
4
5
7
6
8
1
2
3
4
7
5
8
6
初态 第 1趟计算机软件基础
1
2
3
4
5
7
6
8
1
2
3
4
7
5
8
6
初态 第 1趟计算机软件基础
1
2
3
4
5
7
6
8
1
2
3
4
7
5
8
6
初态 第 1趟计算机软件基础
1
2
3
4
5
7
6
8
1
2
3
4
7
5
8
6
发生逆序交换的最后一个记录位置初态 第 1趟计算机软件基础
1
2
3
4
5
7
6
8
1
2
3
4
7
5
8
6
1
2
3
4
5
7
6
8
传统算法第 2趟排序的范围初态 第 1趟 第 2趟计算机软件基础
1
2
3
4
5
7
6
8
1
2
3
4
7
5
8
6
1
2
3
4
5
7
6
8
实际上第 2趟排序的范围初态 第 1趟 第 2趟计算机软件基础
1
2
3
4
5
7
6
8
1
2
3
4
7
5
8
6
1
2
3
4
5
7
6
8
实际上第 2趟排序的范围初态 第 1趟 第 2趟计算机软件基础
在算法中设置一个指示
,最后一个进行交换的记录的位置,的变量可以有效地提高算法的效率。
课后练习题：
给定一组关键字序列 {19,26,92，
87,11,43,87,21}，分别用冒泡排序和直接插入排序方法进行排序，写出每趟排序后关键字的排列结果。
计算机软件基础
[38] 20 46 38 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
计算机软件基础
[38] 20 46 38 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
20
计算机软件基础
38 20 46 38 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
20
计算机软件基础
38 38 46 38 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
20
计算机软件基础
38 38 46 38 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
20
计算机软件基础
20 38 46 38 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
20
计算机软件基础
[20 38] 46 38 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
20
第一趟排序结束返回计算机软件基础
[20 38] 46 38 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
计算机软件基础
20 38 46 38 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
46
计算机软件基础
20 38 46 38 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
46
计算机软件基础
[ 20 38 46] 38 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
46
返回第二趟排序结束计算机软件基础
[ 20 38 46] 38 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
计算机软件基础
20 38 46 38 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
38
计算机软件基础
20 38 46 46 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
38
计算机软件基础
20 38 46 46 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
38
计算机软件基础
20 38 38 46 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
38
计算机软件基础
[20 38 38 46] 74 91 12 25
r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8]r[0]
38
返回第三趟排序结束