数据结构(第九章-排序)

《数据结构(第九章-排序)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第9章排序主要内容9.1插入排序9.2交换排序9.3选择排序9.4归并排序9.5基数排序9.5线性表的排序算法排序（Sorting）排序（Sort）是指将数据元素按照指定关键字值的大小递增（或递减）次序重新排列。为什么要学排序：排序应用相当的普遍，是很常用的运算，一般数据处理工作25%的时间都在进行排序比如，学生的成绩按学号排序排序是计算机的一个重要功能，占有了计算机大量的时间比如，文件夹下的文件按名称、类型、大小和时间排序引言基本概念数据元素：又称记录，是数据的基本单位，由数据项构成。数据序列（datalist）：是待排序的数据元素的有限集

2、合。关键字项：用来标识记录的数据项。关键字：记录中关键字项的值称为该记录的关键字。例：标识一个学生就必须用学号的数值做关键字引言排序的含义：对含有多个记录的文件进行整理，最终使得各个记录按关键字递增(或递减)的次序排列起来，这个整理的过程称为排序。其确切的定义如下：假设含n个记录的序列为{R1，R2，．．．．．．Rn},其相应的关键字序列为{K1，K2，．．．．．．Kn}则需确定1，2，…，n的一种排列在：Ri1，Ri2，．．．．．．Rin，使其相应的关键字满足Ki1≤Ki2≤．．．．．．≤Kin（或Ki1≥Ki2≥．．．．．．≥Kin）的关系排序定

3、义引言稳定性：稳定性排序不稳定性排序数据交换性：内部排序外部排序排序的分类引言当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不惟一。在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。排序的稳定性引言按照排序过程中使用内外存的不同将排序方法分为内排序和外排序。

4、若排序过程全部在内存中进行，则称为内排序；若排序过程需要不断地进行内存和外存之间的数据交换，则称为外排序。内排序大致可分为五类：插入排序、交换排序、选择排序、归并排序和分配排序。内排序和外排序引言排序插入排序（直插排序、二分排序、希尔排序）交换排序（冒泡排序、快速排序）选择排序（直选排序、树型排序、堆排序）归并排序（二路归并排序、多路归并排序）分配排序（多关键字排序、基数排序）内排序算法的分类引言排序过程主要是对记录的关键字进行比较和记录的移动过程。因此排序的复杂性可以以算法执行中的数据比较次数及数据移动次数来衡量：当一种排序方法使排序过程在最坏或平

5、均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好。分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。排序的复杂性引言插入排序（insertionsort）基本思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的关键字依次与有序表元素的关键字进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。插入排序的分类：直接插入排序（Straightinsertionsort）二分插入排序（Bin

6、aryinsertionsort）希尔排序（ShellSort/diminishinginsertionsort）9.1插入排序例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。它的直接插入排序的执行过程如图所示：直接插入排序举例9.1插入排序直接插入排序直接插入排序思考两个问题：为什么要选取无序记录序列中的第一个记录：选取无序记录序列中的第一个记录进行插入，可以为有序记录序列中记录的移动腾出空间。如何将该记录插入到有序记录序列中：将记录插入到有序记录序列中的过程如下：将待插记录r[i]的关键字依次与有序区中记录r[j](j=

7、i-1,i-2,…,1)的关键字进行比较，若r[j]的关键字大于r[i]的关键字，则将r[j]后移一个位置;若r[j]的关键字小于或等于r[i]的关键字，则查找过程结束，j+1即为r[i]的插入位置。将r[i]插入到该位置。9.1插入排序直接插入排序直接插入排序算法描述算法描述：已知记录数组r[n]，在排序的中间某一时刻，记录数组分为两部分：r[0],r[1],……r[i-1]为有序，而r[i],……,r[n-1]为无序，直接插入排序将从无序区中选取第一个记录(r[i])插入到有序区的适当位置，使得r[0],…,r[i]为新的有序区。9.1插入排序直

8、接插入排序直接插入排序特殊举例9.1插入排序直接插入排序直接插入排序算法实现publicclassArray