软件设计师 培训资料 PX11010600011_课件_专题11查找与排序.ppt

11.2 排序算法 (1)插入排序 指将无序序列中的各元素依次插入到已经有序的线性表中。 11.2 排序算法 (2)选择排序 简单选择排序的方法是在所有的记录中选出关键字最小的记录，把它与第一个记录交换存储位置，然后再在余下的记录中选出次小的关键字对应的记录，把它与第二个记录交换，依此类推，直至排序完成。 11.2 排序算法 (3)冒泡排序 冒泡排序的基本思想为：从R1开始，两两比较相邻记录的关键字，即比较Ri和Ri+1(i=1，2，…，n?1)的关键字大小，若逆序(如Ki＞Ki+1)，则交换Ri和Ri+1的位置，如此经过一趟排序，关键字最大的记录被安置在最后一个位置(Rn)上。然后再对前n?1个记录进行同样的操作，则具有次大关键字的记录被安置在第n?1个位置(Rn?1)上。如此反复，进行n?1趟冒泡排序后所有待排序的n个记录已经按关键字由小到大有序。 11.2 排序算法 (3)冒泡排序 改进的冒泡排序： 冒泡排序算法对具有n个记录的待排序序列要执行n?1趟冒泡排序。但从例4-8中我们可以发现，在进行第三趟冒泡排序过程时，已没有记录进行过交换，表明此时记录序列已经“正序”(有序)，后面的3趟冒泡“空跑”——没有发生交换。因此应该对算法4-9加以改进：使之能“记住”每趟冒泡排序过程中是否发生了“交换”，若某一趟冒泡未发生“交换”，表示此时记录序列已经有序，应结束排序过程。 11.2 排序算法 (4)快速排序 在待排序的n个记录中任取一个记录R(通常为第一个)，以该记录的关键字K为准，将所有剩下的n?1个记录划分为两个子序列，第一个子序列中所有记录的关键字均小于或等于K；第二个子序列中所有记录的关键字均大于K。 然后将K所对应的记录R放在第一个子序列之后及第二个子序列之前，使得待排序记录序列成为子序列1R子序列2，完成快速排序的第一趟排序。然后分别对子序列1和子序列2重复上述划分，直到每个子序列中只有一个记录时为止。 11.2 排序算法 (4)快速排序 那么如何实现这个划分呢？需设两个指针i、j，初始时分别指向第一个和最后一个记录，即令i=1，j=n，并将第一个记录的关键字暂存于k(先用第一个记录的关键字k进行划分，称这个记录为控制记录或支点)。 当i＜j时，重复以下操作： (1) 若k≤R[j].key，则j=j?1，即再比较j的前一个记录关键字；否则R[j]与R[i]交换。 (2) 比较k与i指向的记录的关键字，若k≥R[i].key，则与i的后一个记录关键字比较(i=i+1)；否则将R[i]与R[j]交换。 (3) 重复上述过程，直至i=j时，划分结束，i所指示的位置就是控制记录应有的位置。 11.2 排序算法 (4)快速排序 第一趟快速排序过程中记录的交换示意图 11.2 排序算法 (4)快速排序 快速排序全过程示意图 11.2 排序算法 (5)归并排序 归并(merging)就是将两个(或两个以上)的有序表合并成一个新的有序表的操作。 对于一个无序表来说，归并排序把它看成是由n个只包含一个记录的有序表组成的表，然后进行两两归并，最后形成包含n个记录的有序文件。 11.2 排序算法 (5)归并排序 归并(merging)就是将两个(或两个以上)的有序表合并成一个新的有序表的操作。 对于一个无序表来说，归并排序把它看成是由n个只包含一个记录的有序表组成的表，然后进行两两归并，最后形成包含n个记录的有序文件。 11.2 排序算法 (6)堆排序 堆的定义： 若序列k1，k2，…，kn，满足： ki ≤ k2i 且 ki ≤ k2i+1（小根堆）或 ki ≥ k2i 且 ki ≥ k2i+1（大根堆），则称k1，k2，k3，…，kn为一个堆。 将序列按顺序排成一棵完全二叉树， 若二叉树的所有根结点值 = 左右孩子的值称为小根堆 若二叉树的所有根结点值 = 左右孩子的值称为大根堆 11.2 排序算法 (6)堆排序 堆的建立： 11.2 排序算法 (6)堆排序 排序过程： 1.建立初始堆 利用“筛选算法”将无序表调整为堆 2.利用堆进行排序 1)将堆顶与无序表的最后一个记录交换， 2) 利用“筛选算法”将无序表调整为堆。 3)转至1)继续。 专题11 算法（一） 查找与排序 11.1 查找算法 基本概念 查找表：用于查找的数据元素集合称为查找表。查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”