第十章内部排序

1、第十章 内部排序主要内容10.1 概述10.2 插入排序10.3 快速排序10.4 选择排序10.5 归并排序10.6 基数排序10.7 各种内部排序方法的比较讨论排序概念 所谓排序，就是要整理文件中的记录，使之按关键字递增增(或递减减)次序排列起来。 NBA成绩表；奖学金评定综合分；内部排序内部排序 外部排序外部排序 将欲处理的数据整个存放到内部存将欲处理的数据整个存放到内部存储器中排序，数据可被随机存取储器中排序，数据可被随机存取 交换式排序交换式排序 选择式排序选择式排序 插入式排序插入式排序 借助外部的辅助存储器（比如：硬盘），由借助外部的辅助存储器（比如：硬盘），由于数据是存在外存中

2、，故数据不可随机被于数据是存在外存中，故数据不可随机被存取存取 排序的分类归并排序归并排序 基数排序基数排序 比较标准 空间复杂度 时间复杂度 稳定性稳定稳定 不稳定不稳定 排序过后能使值相同的数据保排序过后能使值相同的数据保持原顺序中的相对位置持原顺序中的相对位置 排序过后不能使值相同的数据保持原顺序排序过后不能使值相同的数据保持原顺序493256492727324949562732494956基本操作大多数排序算法都有两个基本的操作：比较两个排序码的大小；改变指向记录的指针或移动记录本身。 注意： 第(2)种基本操作的实现依赖于待排序记录的存储方式。#define MAXSIZE 20 /

3、一个用作示例的小顺序表的最大长度一个用作示例的小顺序表的最大长度typedef int KeyType; /定义关键字类型为整数类型定义关键字类型为整数类型typedef struct KeyType key; /关键字关键字 InfoType otherinfo; /其它数据项其它数据项RedType; /记录类型记录类型typedef struct RedType rMAXSIZE+1; /r0赋闲或用作哨兵单元赋闲或用作哨兵单元 int length; /顺序表长度顺序表长度SqList;10.2 插入排序 直接插入排序 折半插入排序 2-路插入排序 表插入排序 希尔排序基本思想：基本思

4、想：顺序顺序地把待排序的数据元素按其值的大小地把待排序的数据元素按其值的大小插入插入到已排序数据元素子集合的到已排序数据元素子集合的适当位置适当位置有序序列有序序列无序序列无序序列一、直接插入排序12578630941256783094直接插入排序子集合的数据元素个数子集合的数据元素个数从从只有只有一一个个数据元素数据元素开始开始逐次逐次增大增大。当当子集合子集合大小大小等于等于原集合原集合时排序完毕。时排序完毕。直接插入排序 64647 789896 62424556464 89896 62424557 76464 6 62424557 764648989 242489895 57 7898

5、96 6初始序列初始序列: :第一次排序第一次排序: :第二次排序第二次排序: :第三次排序第三次排序: :556 67 764648989 2424第四次排序第四次排序: :556 67 724246464 第五次排序第五次排序: :Temp 6j896476jjj557 764648989 24246 6第三次排序第三次排序: :Temp 689647low6二、折半插入二、折半插入 基本思想：在 查找插入位置时，使用折半查找算法。mhigh 三、2-路插入排序 基本思想：增设同类型数组d,视为循环向量。以d1为中心，原数列中比d1小的往前插，比d1大的往后插。 原数列：49 38 65

6、97 76 13 27 49 d数组： 49d1first final3865 97final76final13first27first9749final四、表插入排序key:49 38 65 97 76 13 27 49 基本思想：l 把待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序；l 小组的个数逐次缩小；l 当完成了所有数据元素都在一个组内的排序后排序过程结束。l 希尔排序又称作缩小增量排序。 五、希尔排序增量序列为：增量序列为：5 5，3 3，1 1void ShellSort(SqList &L, int dlta ,int t) /按增量序列按增量序列dlt

7、a0.t-1对顺序表对顺序表L作希尔排序作希尔排序 for(k=0; kai+1，则交换两个数据元素，否则不交换。 当完成一趟交换以后，最大的元素将会出现在数组的最后一个位置。1.依次重复以上过程，当第n-1趟结束时，n个数据元素集合中次小的数据元素将被放置在a1中，a0中放置了最小的数据元素。起泡排序493865977613279797973849271376653849276513384927133849271338271376766549382713特点：特点：1.n个数排序共需进行n-1趟比较2.第i趟共需要进行n-i次比较void BubbleSort(SqList &L) for(

8、i=1;in; i+) change=FALSE; for(j=1; jL.rj+1.key) change=TRUE;L.rjL.rj+1; if(!change) return; 共进行共进行n-1n-1趟排序，趟排序，共进行共进行n(n-1)/2n(n-1)/2次比较次比较T(n)=O(nT(n)=O(n2 2) )二、快速排序算法思想：指定枢轴(通常为第一个记录) 通过一趟排序将以枢轴为中心，把待排记录分割为独立的两部分，使得左边左边记录的关键字小于小于枢轴值，右边右边记录的关键字大于大于枢轴值1.对左右两部分两部分记录序列重复上述过程，依次类推，直到子序列中只剩下一个记录或不含记录为

9、止。27 38 13 49 76 97 65 4949 38 65 97 76 13 27 49i27 38 65 97 76 13 49 4927 38 49 97 76 13 65 49jiiijjijj27 38 13 97 76 49 65 49ijii j27 38 13jjlow=s; high=t; pivotkey=L.rlow.key;从high开始往前找第一个关键字小于pivotkey的记录，与枢轴记录交换从low开始往后找第一个关键字大于pivotkey的记录，与枢轴记录交换重复上述两步直到low= =high为止1. 此时枢轴记录所在的位置i=low=high27 38

10、 13 49 76 97 65 49T(n)=O(nlog2n)10.4 选择排序一、直接选择排序 基本思想：从待排序的数据元素集合中选取最小的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置上数据元素的集合中选取最小的数据元素并将它与原始数据元素集合中的第二个数据元素交换位置；1. 如此重复，直到数据元素集合中只剩一个数据元素为止。 直接选择排序149238365497576613727849ki=1jkjjjjkjjk1349直接选择排序149238365497576613727849i=kjjjjjj1349k k2共进行共进行n-1趟排序，趟排序，n(

11、n-1)/2次比较次比较T(n)=O(n2)对对n个记录的关键字两两比较，共进行个记录的关键字两两比较，共进行n/2次，如此重复次，如此重复直到最后找出最小记录，此过程可以用有直到最后找出最小记录，此过程可以用有n个叶子的完全个叶子的完全二叉树表示；二叉树表示；将叶子结点中最小关键字改为将叶子结点中最小关键字改为MAXINT，然后该叶子与其，然后该叶子与其左左/右兄弟关键字比较，依次修改从叶子到根的路径上各右兄弟关键字比较，依次修改从叶子到根的路径上各结点的关键字值，结点的关键字值， 则根结点为次小记录；则根结点为次小记录；重复重复2，直到叶子结点均为，直到叶子结点均为MAXINT为止。为止。

12、a0a116211616632521212549251663950808082121 若用一个一维数组存放满足此关系的序列，把这个一维数若用一个一维数组存放满足此关系的序列，把这个一维数组看成是一棵完全二叉树，则堆对应的完全二叉树中所有非组看成是一棵完全二叉树，则堆对应的完全二叉树中所有非终端结点的值均大于或均小于其左右孩子的值。终端结点的值均大于或均小于其左右孩子的值。大大顶顶堆堆大大根根堆堆堆排序方法：堆排序方法：由一个无序的序列建成一个堆由一个无序的序列建成一个堆输出堆顶的最小值输出堆顶的最小值剩余的元素建成一个新的堆剩余的元素建成一个新的堆1. 1.重复重复2 2和和3 3093811

13、962783小小顶顶堆堆小小根根堆堆308547122436915349 38 65 97 76 13 27 49输出输出1313后后, ,用用序列中最后一序列中最后一个记录代替根个记录代替根结点结点筛筛选选为为堆顶元素与它的左右子树根结点比较堆顶元素与它的左右子树根结点比较l 若右子树根若右子树根 左子树根左子树根 堆顶堆顶 根结点与根结点与右子树根右子树根交换交换l 若左子树根若左子树根 右子树根右子树根 堆顶堆顶 根结点与根结点与左子树根左子树根交换交换这个从堆顶到叶子的调整过程称为这个从堆顶到叶子的调整过程称为筛选筛选1338497697276549973849762765492738

14、4976496597对一个无序序列建立堆也是筛选过程对一个无序序列建立堆也是筛选过程,筛选从筛选从n/2个记录开始。个记录开始。49 38 65 97 76 13 27 4976274913496538974997657649273813建立大顶堆建立大顶堆493865764927971349766549382797134997657649273813497665493827971349276549387697134965274938769713496527493876971349132749387697651349274938769765134927493876976549132749387

15、697654949273813769765494927381376976549132738497697654938271349769765建建大顶堆大顶堆，排序，排序结果为结果为从小到大从小到大493827134976976549273813497697654913382749769765T(n)=O(nlog2n)10.5 归并排序 基本思想： 将一个具有n个待排序记录的序列看成是n个长度为1的有序序列; 然后进行两两归并，得到n/2个长度为2的有序序列; 再进行两两归并，得到n/4个长度为4的有序序列;1. 不断重复归并直至得到一个长度为n的有序序列为止。归并排序过程 (49) (38)

16、(65) (97) (76) (13) (27)(38 49) (38 49 65 97)(65 97)(13 76)(27) (13 27 38 49 65 76 97)(13 27 76)10.6 基数排序不通过关键字之间的比较进行排序不通过关键字之间的比较进行排序 一、多关键字排序一、多关键字排序(1,1),(2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4)(1,1),(1,3),(2,4),(2,3),(3,2),(3,4),(4,4),(4,3)(1,1),(1,3),(2,3),(2,4),(3,2),(3,4),(4,3),(4,4)(1,1),(

17、2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4)(1,1),(3,2),(1,3),(2,3),(4,3),(2,4),(4,4),(3,4)(1,1),(1,3),(2,3),(2,4),(3,2),(3,4),(4,3),(4,4)排序思想排序思想 基数排序是按组成关键字的各位的值进行分配和收集，与前面介绍的排序方法不同，它无需进行关键字之间的比较。 设关键字有d 位，每位的取值范围为 r (称为基数)，则需要进行d 趟分配与收集，需要设立 r 个队列。 例如： 关键字是4位字符串，需要26个队列，4趟分配与收集； 关键字3位十进制数，需要10个队列，3趟分

18、配与收集基数排序过程278109063930589184505269008083 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 278pp109p063p930p589p184p505p269p008p083930063083184505278008109589269 505008109930063269278083184589f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 505008109930269063278589184083f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 008063083109184269278505589930008063183109184269278505589930930063083184505278008109589269 各种排序方法的比较各种排序方法的比较对排序算法应该从以下几个方面综合考虑：对排序算法应该从以下几个方面综合考虑：时间复杂性；时间复杂性；空间复杂性；空间复杂性；稳定性；稳定性；算法简单性；算法简单性；待排序记录个数待排序记录个数n的大小；的大小；记录本身信息量的大小；记录