排序 排序就是要整理文件中的记录,使得它按关 键字递增(或递减)的次序排列起来 当待排序记录的关键字均不相同时,则排序 结果唯一,否则排序结果不唯一。 内部排序与外部排序 内部排序可分为:插入排序、交换排序、选 择排序、归并排序和分配排序。 评价一个排序算法好坏的标准有以下几方面: 算法执行时所需要的时间。 执行算法所需要的附加空间。 算法的复杂程度
排序 • 排序就是要整理文件中的记录，使得它按关 键字递增（或递减）的次序排列起来。 • 当待排序记录的关键字均不相同时，则排序 结果唯一，否则排序结果不唯一。 • 内部排序与外部排序。 • 内部排序可分为：插入排序、交换排序、选 择排序、归并排序和分配排序。 • 评价一个排序算法好坏的标准有以下几方面： –算法执行时所需要的时间。 –执行算法所需要的附加空间。 –算法的复杂程度
插入排序 插入排序是将待排序的记录按其关键字的大 小插入到前面已经排好序的文件中的适当位 置上,直到全部插完为止 下面介绍两种典型的插入排序方法 直接插入排序 希尔排序
插入排序 • 插入排序是将待排序的记录按其关键字的大 小插入到前面已经排好序的文件中的适当位 置上，直到全部插完为止。 • 下面介绍两种典型的插入排序方法。 –直接插入排序 –希尔排序
直接插入排序 ·设原始文件的记录关键字为45,33,14,88, 62,其排序过程如下: 初始状态5 88 第一趟排序3 88 第二趟排序14 2228 第三趟排序
直接插入排序 • 设原始文件的记录关键字为45，33，14，88， 62，其排序过程如下：
直接插入排序方法 直接插入排序的方法是:先把原始文件的第 二个记录的关键字与第一个记录的关键字进 行比较,然后按照比较结果将第二个记录放 到相对第一个记录的合适位置上 再取第三个记录的关键字与前两个关键字进 行比较,并把第三个记录插入到相对前两个 记录的合适位置上 依此下去,直到最后一个记录,这样就完成 了排序
直接插入排序方法 • 直接插入排序的方法是：先把原始文件的第 二个记录的关键字与第一个记录的关键字进 行比较，然后按照比较结果将第二个记录放 到相对第一个记录的合适位置上。 • 再取第三个记录的关键字与前两个关键字进 行比较，并把第三个记录插入到相对前两个 记录的合适位置上。 • 依此下去，直到最后一个记录，这样就完成 了排序
希尔排序 ·设原始文件的记录关键字为52,41,45,85, 17,30。增量依次取3、1。其排序过程如下: 视始关字5445:5 Du 增里为3第一超排序52173054145 增里为1第一她种序17
希尔排序 • 设原始文件的记录关键字为52，41，45，85， 17，30。增量依次取3、1。其排序过程如下：