站内搜索

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

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

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

教学难点: 快速排序算法

授课内容:

一、排序概述

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

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

 

四、总结

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

五、作业

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

 

  • 上一篇:数据结构教程 第三十五课 实验七 查找
  • 下一篇:数据结构教程 第三十三课 哈希表(二)