算法设计与分析-蛮力思想

《算法设计与分析-蛮力思想》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章排序基础广东工业大学计算机学院数据结构3.1排序的概念与分类3.1.1排序的概念3.1.2排序的分类3.2直接插入排序3.3希尔排序3.4基数排序3.4.1多关键字排序3.4.2基数排序第3章排序基础3.1排序的概念与分类含有多个域的数据元素称为记录。用于对记录进行唯一标识的域称为关键字。为了与元素类型ElemType区别，记录类型定义为RecordType。typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项……//其它数据项}RecordType,RcdTyp

2、e;//记录类型3.1.1排序的概念排序是将一组“无序”的记录序列调整为“有序”的记录序列。例如，将下列关键字序列：（175,85,260,63,412,504,840,518,630,950）调整为有序序列：（63,85,175,260,412,504,518,630,840,950）什么是排序假设含n个记录的序列为（r1,r2,…,rn）其相应的关键字序列为（k1,k2,…,kn）这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系kp1≤kp2≤…≤kpn按此固有关系将上式记录序列重新排列为（rp1,rp2,…，rpn）的

3、操作称作排序。记录顺序表的类型定义typedefstruct{RcdType*rcd;//存储空间基址intlength;//当前长度intsize;//存储容量}RcdSqList;//记录的顺序表注意：顺序表的0号单元闲置或用作哨兵。在后面的讨论中，前后文意思清楚的情况下，约定：把“记录的关键字的大小”和“记录的关键字的比较”简称为“记录的大小”和“记录的比较”。将“元素的关键字的大小”和“结点的关键字大小”简称为“元素的大小”和“结点的大小”。3.1.2排序的分类根据在排序过程中涉及的存储器不同，可将排序方法分为两大类：内部排序和外

4、部排序。内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。外部排序指的是大文件的排序，待排序的文件无法一次装入内存，将待排序的记录存储在外存储器上，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。内部排序的分类内部排序方法分为五类：交换排序、选择排序、插入排序、归并排序和基数排序。其中交换排序、选择排序和插入排序是一个逐步扩大记录的有序序列长度的过程。有序序列区无序序列区有序序列区无序序列区排序的介绍交换排序是对无序区中记录的关键字两两进行比较，若逆序则交换，直到关键字之间不存在逆序为止。冒

5、泡排序和快速排序是交换排序中最典型的两个方法。选择排序是在无序区中选出关键字最小的记录，置于有序区的最后，直到全部记录有序。简单选择排序和堆排序是选择排序中最典型的两个方法。2134521345排序的介绍插入排序是将无序区中的一个记录插入至有序区，使得有序区的长度加1，直到全部记录有序。直接插入排序和希尔排序是插入排序中最具代表性的两个方法。归并排序是不断将两个或两个以上有序区合并成一个有序区，直到全部记录有序。基数排序是和前面所述各类排序方法完全不同的一种排序方法，不需要进行记录关键字的比较。21345排序算法的时间复杂度分类内部排序方

6、法按时间复杂度分为三类：简单的排序方法，时间复杂度为O(n2)；先进的排序方法，时间复杂度为O(nlogn)；基数排序，时间复杂度为O(n)。希尔排序的算法时间复杂度与增量序列有关，还涉及到一些数学上尚未解决的难题，其算法时间复杂度不属于以上类别。每一种排序方法都有各自的优缺点，适合于不同的应用场合。为方便起见，若非特意强调，排序的实施均为非递减有序排序。直接插入排序假如8个记录的关键字序列为（56,68,25,45,90,38,10,72）,每一趟的排序过程可参看下图：第i趟插入排序将记录L.rcd[i+1]插入到有序区L.rcd[1.

7、.i]中，插入前需要找到插入位置，移动记录空出插入位置。45[]456890算法实现分析查找插入位置从有序区的位置1到i，判断是否为记录L.rcd[i+1]的插入位置j，代码为：j=1;while(L.rcd[j].keyj){L.rcd[k+1]=L.rcd[k];k-

8、-;}//从后到前移动记录若将判断插入位置的次序改为从i到1，则可将上述两步的代码合并为：L.rcd[0]=L.rcd[i+1];j=i;while(j>0&&L.rcd[0].key