排序基本概念汇总课件.ppt

《排序基本概念汇总课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章排序9.1排序基本概念9.2插入排序9.3交换排序9.4选择排序9.5归并排序9.6基数排序9.7内部排序总结9.8有关排序算法的C语言源程序习题九9.1排序基本概念排序(sorting)又称分类，意指把一批杂乱无章的数据序列重新排列成有序序列。排序是程序设计中一种重要运算。在很多领域中有广泛的应用。譬如，在查找时，若文件的记录按关键字预先排好顺序，可以采用折半查找方法提高查找效率。折半查找的平均查找长度数量级为O(lbn)，而顺序查找的平均查找长度数量级为O(n)。又如，建立二叉排序树的过程本身就是一个排序过程。日常生活中的各类竞赛活动，

2、如歌唱大奖赛等，还有各种升学考试录取工作均离不开排序。按待排序的记录的数量多少，排序过程中涉及的存储介质不同，排序方法分为两大类：内部排序和外部排序。内部排序是指待排序的记录存放在计算机内存之中；外部排序是指待排序的记录数量很大，以至于内存容纳不下而存放在外存储器之中，排序过程需要访问外存。本章主要讨论内部排序。外部排序在10.4节讨论。排序的依据可以是记录的主关键字，也可以是次关键字，甚至是若干数据项的组合。为了讨论方便把排序所依据的数据项统称排序关键字，简称关键字。假设含有n个记录的序列为｛R1，R2，…，Rn｝，其相应的关键字序列为｛K1，

3、K2，…，Kn｝，所谓排序就是将记录按关键字非递减(或非递增)的顺序重新排列起来。在待排序的记录中若有多个相同的关键字，在用某种方法排序之后，这些关键字相同的记录相对先后次序不变，则称这种排序方法是稳定的；否则是不稳定的。本章所介绍的内部排序方法包括插入排序、交换排序、选择排序、归并排序和基数排序。前四类排序是通过比较关键字的大小决定记录先后次序，也称为比较排序。基数排序是不经关键字比较的排序方法。为了讨论方便，在此把排序关键字假设为整型。记录的结构定义：typedefstruct/*记录结构*/{intkey;/*排序关键字域*/intoth;

4、/*其他域，根据需要自己设定*/}node;进行排序的向量结构如下：noder[MAXSIZE]其中MAXSIZE是一常量，应该足够大。若记录总数为n，则MAXSIZE>n。在本章各排序方法中，约定第一个记录存放在r[1]之中。9.2插入排序9.2.1直接插入排序直接插入排序(straightinsertionsort)是一种最简单的排序方法。它的基本操作是将一个记录插入到一个长度为m(假设)的有序表中，使之仍保持有序，从而得到一个新的长度为m＋1的有序表。算法思路：设有一组关键字｛K1，K2，…，Kn｝；排序开始就认为K1是一个有序序列；让K2

5、插入上述表长为1的有序序列，使之成为一个表长为2的有序序列；然后让K3插入上述表长为2的有序序列，使之成为一个表长为3的有序序列；依次类推，最后让Kn插入上述表长为n-1的有序序列，得一个表长为n的有序序列。例9.1设有一组关键字序列｛55，22，44，11，33｝，这里n=5，即有5个记录。如图9.1所示。请将其按由小到大的顺序排序。图9.1直接插入排序示例在具体实现Ki向前边插入时，有两种方法。一种方法是让Ki与K1，K2，…顺序比较；另一方法是Ki与Ki-1，Ki-2，…倒着比较。这里选用后一种方法。用一维数组r做存储结构，n表示记录个数。

6、则算法如下：算法9.1voidstinsort(noder[ ]，intn)｛for(i=2；i<=n；i++)/*共进行n-1趟插入*/｛r[0]=r[i]；/*r[0]为监视哨，也可做下边循环结束标志*/j=i-1；while(r[j].key>r[0].key)｛r[j+1]=r[j]；j--；｝r[j+1]=r[0]；/*将r[0]即原r[i]记录内容，插到r[j]后一位置*/｝｝/*sinsort*/此算法外循环n-1次，在一般情况下内循环平均比较次数的数量级为O(n)，所以算法总时间复杂度为O(n2)。由于比较过程中，当Kj与K0相等

7、时并不移动记录，因此直接插入排序方法是稳定的。直接插入排序也可用单链表做存储结构，当某结点i的关键字Ki与前边有序表比较时，显然先与K1比较，再与K2比较……即从链表表头结点开始向后逐一比较更合适。另外，直接插入排序在原关键字序列基本有序或n值较小时，它是一种最常用的排序方法，它的时间复杂度接近于O(n)。但是，当待排序的关键字无序、n值又较大时，此方法就不再适用。9.2.2折半插入排序当直接插入排序进行到某一趟时，对于r[i].key来讲，前边i-1个记录已经按关键字有序。此时不用直接插入排序的方法，而改为折半查找，找出r[i].key应插的位

8、置，然后插入。这种方法就是折半插入排序(binaryinsertionsort)。算法如下：算法9.2voidbinasort(node