神马文学网第三十四课 插入排序、快速排序
来源：百度文库 编辑：神马文学网 时间：2024/04/29 05:12:07
教学目的： 掌握排序的基本概念，插入排序、快速排序的算法
教学重点： 插入排序、快速排序的算法
教学难点： 快速排序算法
授课内容：
一、排序概述
排序：将一个数据元素的无序序列重新排列成一个按关键字有序的序列。
姓名年龄体重
1李由5762
2王天5476
3七大2475
4张强2472
5陈华2453
上表按年龄无序，如果按关键字年龄用某方法排序后得到下表：
姓名年龄体重
3七大2475
4张强2472
5陈华2453
2王天5476
1李由5762
注意反色的三条记录保持原有排列顺序，则称该排序方法是稳定的！
如果另一方法排序后得到下表：
姓名年龄体重
4张强2472
3七大2475
5陈华2453
2王天5476
1李由5762
原3,4,5记录顺序改变，则称该排序方法是不稳定的！
内部排序：待排序记录存放在计算机随机存储器中进行的排序过程；
外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
二、插入排序
1、直接插入排序
基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。排序过程：
3849659776132749...
3849657697132749...
1338496576972749...
1327384965769749...
1327384949657697...
2、折半插入排序
在直接插入排序中，为了找到插入位置，采用了顺序查找的方法。为了提高查找速度，可以采用折半查找，这种排序称折半插入排序。
3、2－路插入排序
为减少排序过程中移动记录的次数，在折半插入排序的基础上加以改进：
4938659778132749...
i=149
first
i=249 38
final first
i=34965 38
final first
i=4496597 38
final first
i=549657697 38
final first
i=649657697 1338
final first
i=749657697 132738
final first
i=84949657697132738
finalfirst
三、快速排序
1、起泡排序
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。直至第n-1个记录和第n个记录的关键字进行过比较为止。
然后进行第二趟起泡排序，对前n-1个记录进行同样操作。
...直到在某趟排序过程中没有进行过交换记录的操作为止。
49383838381313
38494949132727
65656513273838
977613274949
7613274949
13274965
274978
4997
初始第一趟第二趟第三趟第四趟第五趟第六趟
2、快速排序
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
初始关键字4938659776132749
i jj
1次交换之后273865977613 49
i i j
2次交换之后2738 9776136549
i jj
3次交换之后2738139776 6549
ii j
4次交换之后273813 76976549
ij j
完成一趟排序2738134976976549
初始状态4938659776132749
一次划分2738134976976549
分别进行132738
结束 结束 49657697
4965 结束
结束
有序序列1327384949657697
四、总结
几种排序的简单分析与比较。（时间、空间复杂度）
五、作业
实现直接插入排序、起泡排序、快速排序算法。
教学重点： 插入排序、快速排序的算法
教学难点： 快速排序算法
授课内容：
一、排序概述
排序：将一个数据元素的无序序列重新排列成一个按关键字有序的序列。
姓名年龄体重
1李由5762
2王天5476
3七大2475
4张强2472
5陈华2453
上表按年龄无序，如果按关键字年龄用某方法排序后得到下表：
姓名年龄体重
3七大2475
4张强2472
5陈华2453
2王天5476
1李由5762
注意反色的三条记录保持原有排列顺序，则称该排序方法是稳定的！
如果另一方法排序后得到下表：
姓名年龄体重
4张强2472
3七大2475
5陈华2453
2王天5476
1李由5762
原3,4,5记录顺序改变，则称该排序方法是不稳定的！
内部排序：待排序记录存放在计算机随机存储器中进行的排序过程；
外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
二、插入排序
1、直接插入排序
基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。排序过程：
3849659776132749...
3849657697132749...
1338496576972749...
1327384965769749...
1327384949657697...
2、折半插入排序
在直接插入排序中，为了找到插入位置，采用了顺序查找的方法。为了提高查找速度，可以采用折半查找，这种排序称折半插入排序。
3、2－路插入排序
为减少排序过程中移动记录的次数，在折半插入排序的基础上加以改进：
4938659778132749...
i=149
first
i=249 38
final first
i=34965 38
final first
i=4496597 38
final first
i=549657697 38
final first
i=649657697 1338
final first
i=749657697 132738
final first
i=84949657697132738
finalfirst
三、快速排序
1、起泡排序
首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。直至第n-1个记录和第n个记录的关键字进行过比较为止。
然后进行第二趟起泡排序，对前n-1个记录进行同样操作。
...直到在某趟排序过程中没有进行过交换记录的操作为止。
49383838381313
38494949132727
65656513273838
977613274949
7613274949
13274965
274978
4997
初始第一趟第二趟第三趟第四趟第五趟第六趟
2、快速排序
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
初始关键字4938659776132749
i jj
1次交换之后273865977613 49
i i j
2次交换之后2738 9776136549
i jj
3次交换之后2738139776 6549
ii j
4次交换之后273813 76976549
ij j
完成一趟排序2738134976976549
初始状态4938659776132749
一次划分2738134976976549
分别进行132738
结束 结束 49657697
4965 结束
结束
有序序列1327384949657697
四、总结
几种排序的简单分析与比较。（时间、空间复杂度）
五、作业
实现直接插入排序、起泡排序、快速排序算法。
第三十四课 插入排序、快速排序
选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
第三十六课 选择排序、归并排序
快速排序
算法连载（2）--快速排序与插入排序的比较 - Compower Studio - CSD...
第三十七课 实验八 排序实验
快速排序算法
快速排序--C语言
java快速排序法
快速排序算法
快速排序算法
冒泡 直接插入 希尔排序 效率比拼
采用部分快速排序算法实现数组的部分排序
算法设计与分析 2.81 快速排序
采用部分快速排序算法实现数组的部分排序 - eaglet的专栏 - CSDN博客
采用部分快速排序算法实现数组的部分排序 - eaglet - 博客园
希尔排序
数据结构排序
饮食排序
堆排序
随机排序
随机排序
钙质排序
饮食排序