第10章 排序.ppt

《第10章 排序.ppt》由会员分享，可在线阅读，更多相关《第10章 排序.ppt（73页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2021/12/6,1,第10章 排序,本章知识要点：基本概念插入排序交换排序选择排序归并排序基数排序外部排序,2021/12/6,2,10.1 基本概念,排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。作为排序依据的数据项称为“排序码”，也即数据元素的关键码。为了便于查找，通常希望计算机中的数据表是按关键码有序的。如有序表的折半查找，查找效率较高。还有，二叉排序树、B-树和B+树的构造过程就是一个排序过程。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可能不

2、唯一，这是因为具有相同关键码的数据元素，这些元素在排序结果中，它们之间的的位置关系与排序前不能保持。,2021/12/6,3,若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。 排序分为两类：内排序和外排序。 内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。 外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。,2021/12/6,4,10.2 插入排序,10.2.1 直接插入排序 设有n个记录，存放在数组r中，重新安排记录在数组中的存放顺序，使得按关键码有序。即r1.keyr2.keyrn.key 先来看看向有序表中插入一个记录的方法： 设，r1.keyr2.keyrj-1.key，将rj插入，重新安排存放顺序，使得r1.keyr2.keyrj.key，得到新的有序表，记录数增。,