页数:16页文件大小:122.3 KB来源: 程序设计基础与数据结构ppt课件
本课件系统讲解排序运算:先给出排序的定义并区分内部排序与外部排序,指出前四类内部排序基于关键字比较而基数排序基于分布规律;随后逐一讲解简单选择排序与堆排序、直接插入排序、二分插入排序与希尔排序、冒泡排序与快速排序,再介绍归并排序与基数排序,最后给出外部排序中直接归并排序法的两个步骤。
第九章 排序
排序的基本概念
9.1 选择排序:每次从待排序序列中选出关键字值最小(或最大)的元素,把它放到已排序序列的末端,反复进行直到序列中所有元素都排列完为止。
9.1.1 简单选择排序:从所有待排序元素序列中选出关键字值最小的数据元素,将其与原序列中的第一个数据元素交换;然后在剩余元素序列中再选取关键字值最小的元素,与第二个元素交换;依此类推,即每一次都是在 n-i+1 个数据元素中选出关键字值最小的元素,将其与第 i 个数据元素交换。
9.1.2 堆排序:堆排序是对简单选择排序的改进。
9.2 插入排序:每一次排序都是将一个待排序的数据元素按其关键字值的大小插入到已排序序列的适当位置上,使之保持有序。
9.2.1 直接插入排序:将待排序元素插入到已排序序列时,插入位置是采用顺序查找的方法得到的。直接插入排序算法简单,常用于数据量较少或待排序序列基本有序的情况,但当数据量较大时效率不高。
9.2.2 二分插入排序:待排序元素的插入位置是采用二分查找的方法得到的,能比直接插入排序的顺序查找更快地确定插入位置。
9.2.3 希尔排序:希尔(Shell)排序又称缩小增量排序。
9.3 交换排序:基本思想是比较两个相邻数据元素的关键字值,将不满足次序要求的数据元素交换位置,直到所有数据元素都满足次序要求为止。
9.3.1 冒泡排序:以递增序排序为例,在每一趟排序中先比较第一个与第二个元素的关键字,若逆序则交换,接着比较第二个与第三个,如此反复直到最后两个元素,关键字值最大的元素被交换到序列尾端;再对剩余序列作相同操作,使次大元素到达倒数第二的位置,依此类推,直到某趟不出现交换或只剩一个元素为止。
9.3.2 快速排序:快速排序由冒泡排序改进而来,是内部排序众多算法中速度最快的一种。
9.4 归并排序:归并排序是将两个或两个以上的有序序列合并成一个新的有序序列的过程。
9.5 基数排序:基数排序(Radix Sort)的排序过程通过分配和收集完成,又称为桶排序(Bucket Sort)或箱排序(Bin Sort)。
9.6 外部排序:当待排序数据量太多或记录数量太大、无法一次装入内存时,需依赖外部存储装置,通过内外存之间的数据交换来排序,这时使用的是外部排序法。
9.7 小结
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}