《内排序(精简版)》由会员分享，可在线阅读，更多相关《内排序(精简版)（89页珍藏版）》请在金锄头文库上搜索。
1、王桂平 信息学院信息技术教研室数据结构与算法第7章 内排序2信息学院信息技术教研室内排序知识点7.1 排序问题的基本概念排序问题的基本概念 7.1.1 补充：用系统函数实现排序补充：用系统函数实现排序 7.2 三种三种O(nO(n2 2) )的简单排序算法的简单排序算法 7.2.1 插入排序法插入排序法 7.2.2 冒泡排序法冒泡排序法 7.2.3 直接选择排序法直接选择排序法 7.2.4 简单排序算法的时间代价对比简单排序算法的时间代价对比 7.3 ShellShell排序排序 7.4 基于分治法的排序基于分治法的排序 7.4.1 快速排序快速排序 7.4.2 归并排序归并排序3信息学院信息
2、技术教研室排序无处不在 : 在计算机应用软件计算机应用软件中经常需要对所管理的各种数据进行处数据进行处 理理，排序排序往往是这些数据处理中需要用到的核心运算核心运算。 : 排序例子排序例子1 1：资源管理器资源管理器。一级排序4信息学院信息技术教研室: 排序例子排序例子2 2：ExcelExcel提供的排序功能提供的排序功能，最多可以选择3个 关键字关键字(也就是最多可以进行三级排序最多可以进行三级排序)，每个关键字都 可以选择是增序还是减序。二 级 排 序5信息学院信息技术教研室: 排序例子排序例子3 3：回收站的排序功能回收站的排序功能，可以对已删除的文件 按删除日期删除日期、修改时间等属
3、性进行排序，当需要还原还原 文件时文件时，按删除日期排序按删除日期排序将给用户提供重要的参考。6信息学院信息技术教研室日常生活中的排序例子: 以上例子是排序在计算机常用软件中的经典应用。 : 日常生活中的排序例子日常生活中的排序例子：kk2 2 kkn n，则前者称为增序增序，或者称为降序降序。: 在要求不很严格的情况下，也称不减序列为增序称不减序列为增序，称不增称不增 序列为降序序列为降序。12信息学院信息技术教研室正序和逆序: 如果待排序序列正好符合排序要求待排序序列正好符合排序要求，则称这样的序列为“ “正正 序序” ”序列序列。 : 如果把待排序序列逆转过来，也正好符号排序要求，则称
4、这样的序列为“ “逆序逆序” ”序列序列。说明说明 (1) 如无特殊说明，本章在介绍各种排序算法时一般是对序对序 列进行不减或增序排序列进行不减或增序排序，序列中的每个记录只有一个域序列中的每个记录只有一个域 ，且为整数，这个域充当排序码，且为整数，这个域充当排序码。 (2) 考虑到C+中数组下标都是从0开始计起的，本章讨论的 大部分序列的下标也从序列的下标也从0 0开始计起开始计起。因此，我们讨论的序 列为R R = = r r0 0, , r r1 1, , , , r rn n-1-1 。13信息学院信息技术教研室稳定和不稳定的排序算法: 如果存在多个具有相同排序码的记录，采用某种排序算
5、法 进行排序后这些记录的相对次序仍然保持不变这些记录的相对次序仍然保持不变，则这样的 排序算法称为是稳定的稳定的(stable)，否则称为不稳定的不稳定的。: 在某些应用领域中，可能要求尽量不要改变相同排序码的尽量不要改变相同排序码的 记录的原始输入顺序记录的原始输入顺序，这就需要采用稳定的排序算法。14信息学院信息技术教研室排序算法的时间复杂度: 排序算法太多了，因此有的时候就需要在多个排序算法之需要在多个排序算法之 间进行取舍间进行取舍。评价一种排序算法的好坏主要是通过空间复评价一种排序算法的好坏主要是通过空间复 杂度和时间复杂度两方面来衡量杂度和时间复杂度两方面来衡量，尤其是时间复杂度。
6、 : 算法的时间复杂度一般通过排序过程中记录的比较记录的比较和交换交换 次数来衡量。(比较比较和交换交换往往是排序算法中的基本运算基本运算): 一般而言，自然是排序所需的时间越短的算法越好。但是 ，有些算法的运行时间依赖于原始输入记录的情况，记录 的数量、排序码和记录的大小、输入记录的原始有序程度输入记录的原始有序程度 。 : 因此评价排序算法往往要从以下3个方面来考虑： 头文件中声明的，因此使用 qsort函数必须包含这个头文件。qsortqsort函数的原型函数的原型为 ：它有四个参数，其含义为： basebase：参与排序的元素存储空间的首地址，它是空指针类型； numnum：参与排序的
7、元素个数； widthwidth：参与排序的每个元素所占字节数(宽度)； 第四个参数为一个函数指针，这个函数需要用户自己定义，用来 实现排序时实现元素之间的大小关系比较。compare函数的两个 参数都是空指针类型，在实现时必须强制转换成参与排序的元素在实现时必须强制转换成参与排序的元素 类型的指针类型的指针。void qsort( void *base, int num, int width, int ( *compare )(const void *elem1, const void *elem2 ) );17信息学院信息技术教研室如果是按从小到大的顺序从小到大的顺序(即升序)排序，com
8、pare函数的返回值返回值 的含义为： 1) 当第第1 1个参数所指向的元素小于第个参数所指向的元素小于第2 2个参数所指向的元素个参数所指向的元素，返 回值 0 0；如果需要按从大到小的顺序从大到小的顺序(降序)排序，compare函数的返回值 具有相反的含义：当第当第1 1个元素大于第个元素大于第2 2个元素，则返回值个元素，则返回值 0 0。18信息学院信息技术教研室1) 对基本数据类型的数组排序:如果数组元素是intint型，且按从小到大的顺序按从小到大的顺序(升序)排 序，compare函数可以编写成：这样如果在qsort函数实现排序的过程中调用compare函数比较 67和89这两
9、个元素，compare函数的返回值为-22，即 0。int compare( const void *elem1, const void *elem2 ) return *(int *)elem1 - *(int *)elem2; 19信息学院信息技术教研室: 另外，compare函数也可以编写成(按从小到大顺序排序) ：int compare( const void *elem1 , const void *elem2 ) return( *(int *)elem1 *(int *)elem2 ) ? 1 : 0; 20信息学院信息技术教研室: compare函数定义好以后，就可以用下面的代
10、码段实现一 个整型数组的排序：对char、double等其他基本数据类型数组的排序，只需把上述 compare函数中的int改写成其他类型即可。int num100; /输入100个数组元素的值 qsort( num, 100, sizeof(num0), compare );/调用qsort函数进行排序21信息学院信息技术教研室2) 对结构体或类对象进行一级排序: 所谓对结构体(或类对象)一级排序一级排序，是指对结构体中的某一对结构体中的某一 个成员的大小关系排序个成员的大小关系排序。 : 例如，假设一个student结构，包含：name、age、score等 成员；另外有一个student
11、型的数组s，里面有若干个元素。 现在要对这些元素以其以其ageage成员的大小关系从大到小的顺序成员的大小关系从大到小的顺序( 升序)排序。compare函数可编写成：int compare( const void *elem1 , const void *elem2 ) return (student *)elem1-age - (student *)elem2-age; qsort函数： qsort( s, 10, sizeof(s0), compare ); 22信息学院信息技术教研室3) 对结构体或类对象进行二级排序: 二级排序：先按第1个成员的大小关系排序，如果第一个成 员大小相等，
12、再按第二个成员的大小关系进行排序。 : 例如，前面的student数组s，可以先按age成员从小到大的 顺序排序，如果age成员大小相等，再按score成员从小到大 的顺序排序。 compare函数： int compare( const void *elem1 , const void *elem2 ) student *p1 = (student *)elem1; student *p2 = (student *)elem2; if( p1-age != p2-age ) return p1-age p2-age; else return p1-score p2-score; qsort函
13、数：qsort( s, 10, sizeof(s0), compare ); 也就说，如果两个元素s1和s1的age成员不等，compare返回的是它 们age成员的大小关系；如果它们的age成员大小相等，返回的是它们 的score成员的大小关系。23信息学院信息技术教研室例例7.1 7.1 快乐的蠕虫快乐的蠕虫( (The Happy Worm)The Happy Worm) 题目来源：Asia 2004, Tehran (Iran), Sharif Preliminary 题号：ZOJ2499，POJ1974题目描述：题目描述： 有一只快乐的蠕虫居住在一个mn大小的网格中。在网格的某 些位
14、置放置了k块石头。网格中的每个位置要么是空的，要么放 置了一块石头。当蠕虫睡觉时，它在水平方向或垂直方向上躺 着，把身体尽可能伸展开来。蠕虫的身躯既不能进入到放有石 块的方格中，也不能伸出网格外。而且蠕虫的长度不会短于2个 方格的大小。 本题的任务是给定网格，要计算蠕虫可以在多少个不同的位置 躺下睡觉。qsort函数应用例子24信息学院信息技术教研室输入描述：输入描述： 输入文件的第1行为一个整数t，1t11，表示测试数据的个数。 每个测试数据的第1行为3个整数：m，n和k，0m，n， k200000，接下来有k行，每行为两个整数，描述了一块石头的 位置（行和列，最左上角位置为最左上角位置为(
15、1,1)(1,1)）。输出描述：输出描述： 对每个测试数据，输出占一行，为一个整数，表示蠕虫可以躺着 睡觉的不同位置的数目。第一种输入方式25信息学院信息技术教研室样例输出：样例输出： 9 8样例输入：样例输入： 2 5 5 6 1 5 2 3 2 4 4 2 4 3 5 1 5 5 10 1 2 1 5 2 4 2 5 3 1 3 3 3 5 4 3 4 5 5 1 思考思考：这两个测试数据计算结果 是怎么得来的？26信息学院信息技术教研室分析：分析： 首先要理解题目的意思。题目中有两句话很关键：“当蠕虫睡觉时，当蠕虫睡觉时， 它在水平方向或垂直方向上躺着，把身体尽可能伸展开来它在水平方向或垂直方向上躺着，把身体尽可能伸展开来”，“而且蠕而且蠕 虫的长度不会短于虫的长度不会短于2 2个方格的大小个方格的大小”。这两句话要结合起来理解。样例 输入中的网格如下图所示，“”表示空的方格，“”表示石头。如果只 凭第2句话，则仅在第1列，蠕虫就可以在3个位置上躺着，分别是头 在(1,1)、(2,1)、(3,1)这3个位置躺着，身躯在垂直方向上向下伸展开 来；但加上第1句话，则这3个位置都是一样的，因为蠕虫在第1列上 躺着，它的身躯会尽可能伸展开来身躯会尽可能伸展开来，占满第1列所有4个空格。
