数据结构-6-排序.ppt

1 6排序 2 主要内容 排序的基本概念简单排序方法选择排序插入排序起泡排序先进排序方法快速排序归并排序基数排序 3 6 1排序的基本概念 排序是计算机内经常进行的一种操作 其目的是将一组 无序 的记录序列调整为 有序 的记录序列 例如 将下列关键字序列52 49 80 36 14 58 61 23 97 75调整为14 23 36 49 52 58 61 75 80 97 定义假设含n个记录的序列为 R1 R2 Rn 其相应的关键字序列为 K1 K2 Kn 这些关键字相互之间可以进行比较 即在它们之间存在着这样一个关系 Kp1 Kp2 Kpn按此固有关系将上式记录序列重新排列为 Rp1 Rp2 Rpn 的操作称作排序 4 6 1排序的基本概念 typedefintKeyType 关健字类型为整数typedefstruct KeyTypekey 关键字项infoTypeOtherInfo 其它信息 RcdType 记录类型 5 6 1排序的基本概念 排序分类按待排序记录所在位置内部排序 待排序记录存放在内存外部排序 排序过程中需对外存进行访问的排序按排序依据原则插入排序 直接插入排序 折半插入排序 希尔排序交换排序 冒泡排序 快速排序选择排序 简单选择排序 堆排序归并排序 2 路归并排序基数排序排序稳定性 6 6 1排序的基本概念 按排序所需工作量简单的排序方法 T n O n 先进的排序方法 T n O nlogn 基数排序 T n O d n 排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置 有序序列R 1 i 1 无序序列R i n 有序序列R 1 i 无序序列R i 1 n 排序算法的思想 将待排序列看成是看成是有有序序列和无序序列组成 每次排序都会按照某种原则将无序序列中的某个元素取出 放在有序序列中 这样经n 1次操作就会将无序序列R 1 n 排成有序序列 内部排序的过程是一个逐步扩大记录的有序序列长度的过程 7 基于不同的 扩大 有序序列长度的方法 内部排序方法大致可分下列几种类型 插入类 交换类 选择类 归并类 其它方法 6 1排序的基本概念 8 6 1排序的基本概念 插入类排序将无序子序列中的一个或几个记录 插入 到有序序列中 从而增加记录的有序子序列的长度 交换类排序通过 交换 无序序列中的记录从而得到其中关键字最小或最大的记录 并将它加入到有序子序列中 以此方法增加记录的有序子序列的长度 选择类排序从记录的无序子序列中 选择 关键字最小或最大的记录 并将它加入到有序子序列中 以此方法增加记录的有序子序列的长度 归并类排序通过 归并 两个或两个以上的记录有序子序列 逐步增加记录有序序列的长度 其它类排序 9 6 2插入排序 6 2 1直接插入排序6 2 2二分 折半 插入排序6 2 3希尔排序 10 6 2 1直接插入排序 插入排序过程 整个排序过程为n 1趟插入 即先将序列中第1个记录看成是一个有序子序列 然后从第2个记录开始 逐个进行插入 直至整个序列有序 有序序列R 1 i 1 R i 无序序列R i n 有序序列R 1 i 无序序列R i 1 n 11 49386597761327 i 238 3849 6597761327 i 365 384965 97761327 i 497 38496597 761327 i 576 3849657697 1327 i 613 133849657697 27 i 1 i 7 133849657697 27 27 97 76 65 49 38 27 例 49386597761327 思考 寻找插入位置时 应该从后向前找还是从前向后找 为什么 12 算法名 InsertSort1 输入 无序数组R2 输出 有序数组R3 算法 1 排序趟数i 2 n 2 对于每一趟i 将无序序列的第一个元素R i 插入到有序序列R 1 i 1 中 InsertSort R for i 2 i n i InsertPass R i InsertPass R i R 0 R i for j i 1 j 1 j if R 0 R j R j 1 R j R j 1 R 0 InsertPass R i R 0 R i for j i 1 j 1 InsertSort R for i 2 i n i if R i R i 1 InsertPass R i 13 算法评价时间复杂度若待排序记录按关键字从小到大排列 正序 关键字比较次数 记录移动次数 0 若待排序记录按关键字从大到小排列 逆序 关键字比较次数 记录移动次数 若待排序记录是随机的 取平均值关键字比较次数 记录移动次数 T n O n 空间复杂度 S n O 1 14 6 2 2二分 折半 插入排序 排序过程 用二分查找方法确定插入位置的排序叫 例 i 1 30 1370853942620 i 213 1330 70853942620 i 76 6133039427085 20 i 820 613203039427085 插入位置为S或j 1处 15 算法描述 算法评价与直接插入排序相比 关键字比较次数减少记录移动次数不变时间复杂度 T n O n 空间复杂度 S n O 1 16 6 2 3希尔排序 基本思想 在直接插入排序算法中 如果待排序列已经是按升序有序的 则直接插入排序的时间复杂性是T n O n Shell排序就是利用这个特点 先将记录进行粗略地分组 使整个序列大致按升序有序 这样最后进行直接插入排序时 时间复杂性T n O n 排序过程 先取一个正整数d1 n 把所有相隔d1的记录放一组 组内进行直接插入排序 然后取d2 d1 重复上述分组和排序操作 直至di 1 即所有记录放进一个组中排序为止 17 18 ShellInsert intR intdk 一次增量排序 for i dk 1 i0 ShellSort intR intd intt 一次增量排序 for k 0 k t k ShellInsert R d k 19 希尔排序特点子序列的构成不是简单的 逐段分割 而是将相隔某个增量的记录组成一个子序列希尔排序可提高排序速度 因为分组后n值减小 n 更小 而T n O n 所以T n 从总体上看是减小了关键字较小的记录跳跃式前移 在进行最后一趟增量为1的插入排序时 序列已基本有序增量序列取法无除1以外的公因子最后一个增量值必须为1 20 6 3交换排序 9 3 1冐泡排序9 3 2快速排序 21 6 3 1冒泡排序 排序过程将第一个记录的关键字与第二个记录的关键字进行比较 若为逆序r 1 key r 2 key 则交换 然后比较第二个记录与第三个记录 依次类推 直至第n 1个记录和第n个记录比较为止 第一趟冒泡排序 结果关键字最大的记录被安置在最后一个记录上对前n 1个记录进行第二趟冒泡排序 结果使关键字次大的记录被安置在第n 1个记录位置重复上述过程 直到 在一趟排序过程中没有进行过交换记录的操作 为止 22 4938659776132730 初始关键字 3849657613273097 第一趟 38496513273076 第二趟 384913273065 第三趟 3813273049 第四趟 13273038 第五趟 132730 第六趟 for j 1 jR j 1 交换R j 和R j 1 w R j R j R j 1 R j 1 w BulleSort R for i n i 1 i for j 1 jR j 1 交换R j 和R j 1 w R j R j R j 1 R j 1 w 23 算法评价时间复杂度最好情况 正序 比较次数 n 1移动次数 0最坏情况 逆序 比较次数 移动次数 空间复杂度 S n O 1 T n O n 24 6 3 2快速排序方法 基本思想 首先对无序的记录序列进行 一次划分 之后分别对分割所得两个子序列 递归 进行划分 无序的记录序列 无序记录子序列 1 无序子序列 2 枢轴 一次划分 分别进行划分 25 记录划分 找一个记录 以它的关键字作为 枢轴 凡其关键字小于枢轴的记录均移动至该记录之前 反之 凡关键字大于枢轴的记录均移动至该记录之后 划分过程 对r s t 中记录进行一次划分 附设两个指针low和high 设枢轴记录rp r s pivotkey rp key初始时令low s high t首先从high所指位置向前搜索第一个关键字小于pivotkey的记录 并和rp交换再从low所指位置起向后搜索 找到第一个关键字大于pivotkey的记录 和rp交换重复上述两步 直至low high为止 26 s t low high 设Pivotkey R s 52为枢轴关键字 high 23 low 80 high 14 low 52 R s 52 low high high high low 原序列 52 49 80 36 14 58 61 97 23 75 一次划分后 23 49 14 36 52 58 61 97 80 75 27 递归排序对于上次划分所形成的每个子序列重复进行划分 52 49 80 36 14 58 61 97 23 75 52 23 49 14 36 58 61 97 80 75 14 23 49 36 58 61 97 80 75 36 49 61 97 80 75 36 75 80 97 75 80 80 14 23 36 49 52 58 61 75 80 97 14 28 算法评价时间复杂度最好情况 每次总是选到中间值作枢轴 T n O nlog2n 最坏情况 每次总是选到最小或最大元素作枢轴 T n O n 空间复杂度 需栈空间以实现递归最坏情况 S n O n 一般情况 S n O log2n 29 6 4选择排序 6 4 1简单选择排序6 4 2堆排序 30 6 4 1简单选择排序 有序序列R 1 i 1 无序序列R i n R k 找最小值R k R i R k 与R i 交换 31 选择排序的基本思想 整个排序过程为n趟扫描 即首先在n个记录中选择关键字最小的放在有序子序列的第一个记录位置 然后从剩下的n 1个记录中选择关键字最小的记录放在有序子序列的第二个记录位置 重复此过程 直到最后一个记录例 491 38 65 492 76 13 27 52 32 初始 49386597761327 i 1 13 49 一趟 13 386597764927 i 2 27 38 六趟 132738496576 97 排序结束 13273849657697 33 算法描述 voidSelectSort SqListj 在L r i L length 中选择key最小的记录if L r j key L r k key k j if i k W L r k L r k L r i L r i W 与第i个记录交换 SelectSort 34 算法评价时间复杂度记录移动次数最好情况 0最坏情况 3 n 1 比较次数 空间复杂度 S n O 1 T n O n 简单选择排序 35 6 4 2堆排序 36 6 5归并排序 基本思想 将两个有序表合并成一个有序表的时间复杂性是T n O n 关键 将两个有序表合并成一个有序表的算法 38121518 2514 i j R s t s 1 t 8 m 5 i s j m 1 k s while if SR i SR j TR k SR i i else TR k SR j j k while i m TR k SR i while j n TR k SR j i m j t voidMerge SR TR s m t 37 问题 实际被排序的序列不可能是有序的如果无序序列R s t 的两部分R s s t 2 和R s t 2 1 t 分别按关键字有序 则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列 算法 两类算法自顶向下 递归算法自底向上 迭代算法 38 52 23 80 36 68 14 s 1 t 6 52 23 80 36 68 14 52 23 80 52 23 52 23 52 80 36 68 14 36 68 36 68 14 36 68 14 23 36 52 68 80 23 自顶向下的设计方法 递归算法 39 迭代算法 40 利用数组两相邻有序段归并函数 将存于一个数组中的每len个元素有序的段分别作两两归并 使数组中的元素每2 len个元素有序的函数 算法 一趟归并 voidmergePass SR TR intn intlen inti 1 j while i 2 len n merge SR TR i i len 1 i 2 len 1 i 2 len if i len n 一个长len 另一个不足lenmerge SR TR i i len 1 n 1 41 算法 迭代的归并排序假设初始的对象序列有n个对象 首先把它看成是n个长度为1的有序子序列 先做两两归并 得到n 2个长度为2的归并项 如果n为奇数 则最后一个有序子序列的长度为1 再做两两归并 如此重复 最后得到一个长度为n的有序序列 voidmergeSort R TR n intlen len 1 while len n mergePass R TR len len 2 42 算法评价 两种方法时间复杂度 T n O nlog2n 空间复杂度 S n O n 43 6 6基数排序 关于排序问题的研究排序算法是计算机科学的最基本的算法现在每年仍有排序方面的研究文章出现 主要是基数类的排序算法 理论证明 基于比较的排序算法 其最坏情况下的时间复杂性极限是T n O nlog2n 44 6 6 1桶排序 例 51 31 21 22 52 41 42 53 54 23 32 21 22 23 31 32 41 42 51 52 53 54 45 例对52张扑克牌按以下次序排序 2 3 A 2 3 A 2 3 A 2 3 A两个关键字 花色 面值 2 3 A 并且 花色 地位高于 面值 多关键字排序思路最高位优先法 MSD 先对最高位关键字k1 如花色 排序 将序列分成若干子序列 每个子序列有相同的k1值 然后让每个子序列对次关键字k2 如面值 排序 又分成若干更小的子序列 依次重复 直至就每个子序列对最低位关键字kd排序 最后将所有子序列依次连接在一起成为一个有序序列 6 6 2基数排序 多关键字 46 最低位优先法 LSD 从最低位关键字kd起进行排序 然后再对高一位的关键字排序 依次重复 直至对最高位关键字k1排序后 便成为一个有序序列 MSD与LSD不同特点按MSD排序 必须将序列逐层分割成若干子序列 然后对各子序列分别排序按LSD排序 不必分成子序列 对每个关键字都是整个序列参加排序 并且可不通过关键字比较 而通过若干次分配与收集实现排序 47 链式基数排序基数排序 借助 分配 和 收集 对单逻辑关键字进行排序的一种方法 有的逻辑关键字可以看成由若干个关键字复合而成 例 关键字K的取值范围为 0 999 则可将K看成由三个关键字 k0 k1 k2 组成 其中k0是百位数 k1是十位数 k2是个位数 基数 每位关键字的取值范围 上例的基为10 链式基数排序 用链表作存储结构的基数排序 48 链式基数排序步骤 设关键字K的取值范围为 0 999 设置10个队列 f i 和e