排序的基本概念插入排序交换排序选择排序归并排序基数排序.ppt

排序的基本概念 插入排序 交换排序 选择排序 归并排序 基数排序 各种方法的比较 什么是排序(Sorting)？ 简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。 排序是计算机中经常遇到的操作。 排序的分类 排序算法的稳定性 关键字相同的记录在排序过程中保持前后次序不变的排序称稳定排序，否则称不稳定排序。 排序的时间效率: 通常用算法执行中的数据比较次数与数据移动次数来衡量。 排序的空间效率：在算法执行时所需的附加存储空间多少来衡量。 插入排序(Insert Sorting) 基本思想 : 将第i个记录插入在前i-1个有序的记录中，使前i个记录有序。 时间性能：直接插入排序算法由两重循环组成，外循环为n-1趟排序；内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。 稳定性:稳定的排序。 （关键字相同的记录不会交换次序） 希 尔 排 序 1959年由D.L. Shell提出，又称缩小增量排序(Diminishing-increment sort) 。 基本思想：在排序中，每趟不断调整子序列的大小, 从而减少比较次数, 提高时间效率。 设计一个增量是序列 di(i=1,2,…), 其中nd1 d2 d2 ….. (通常d1=n/2 di+1=di/2),每趟将数据表分成di组, 分别对各组进行直接插入排序, 直到最后全部记录在一组为止。 稳定性:不稳定的排序。 （关键字相同的记录会交换次序） 交换排序 ( Exchange Sort ) 基本思想：在待排序子序列 中，两两比较相邻记录的关键字，若逆序，则交换。 稳定性:稳定的排序。 （关键字相同的记录不会交换次序） 快速排序 (Quick Sort) 基本思想是任取待排序子序列中的一个记录 (例如取第一个) 作为基准, 按照该记录关键字的大小, 将整个子序列划分为左右两个子序列： 快速排序的算法分析 快速排序的算法分析 稳定性:不稳定的排序。 （关键字相同的记录会交换次序） 选择排序(Selection Sort) 基本思想 :在子序列中选择具有最小(或最大)关键字的记录, 若它不是这子序列中的第一位，则将它调入到第一位上。 时间性能：直接选择排序算法由两重循环组成，外循环为n-1趟排序；内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。 直接选择排序的算法分析 稳定性:不稳定的排序。 （关键字相同的记录会交换次序） 堆排序 (Heap Sort) 堆 排 序 堆排序是一种树型选择排序。 基本思想:将待排序的子序列k1, k2, ... ,ki 构造成堆, 从而选择出关键字最大(或最小)记录. 堆排序分为两个步骤： 1、根据初始状态，形成初始堆。 2、通过一系列的记录交换和重新调整 进行排序。 时间性能：堆排序算法分两部分，一是整个序列初建堆；二是n-1趟的交换和重建堆。 堆排序的算法分析 稳定性:不稳定的排序。 （关键字相同的记录会交换次序） 归并排序 (Merge Sort) 基本思想:通过对两个有序记录序列的合并来实现排序。 时间性能：每一趟归并需将一个数据表的所有记录归并到另一个数据表中，则一趟归并的时间效率为O(n)。归并排序共需约log2n趟，则总的时间效率为 T(n)=O(nlog2n) 基数排序(Radix Sort) 多关键字有序:在数据表 {R1,R1,..., Rn}中，每个记录Ri含d个关键字(Ki1,Ki2,..., Kid)。若对序列中的任意两个记录Ri和Rj都有 (Ki1,Ki2,..., Kid) (Kj1,Kj2,..., Kjd) 则称序列对关键字(Ki1,Ki2,..., Kid)有序，且K1称为最高位关键字，Kd称为最低位关键字。 基 数 排 序 基本原理:采用“分配”和“收集”两种运算, 用对多关键字进行排序的思想实现对单关键字进行排序。 此时可将单关键字K看成是一个子关键字组：(Ki1,Ki2,..., Kid) 排序过程：设关键字共有d位，让j= d, d-1,...,1, 依次执行d次“分配”与“收集”。 时间性能：每一趟要进行“分配”和“收集”两步操作，“分配”是将n个结点分配到各队列中 T=O(n) ； “收集”是将r个队列中各非空队列收集 T=O(r) 。 若各关键字最大位数为d, 排序共需d趟，则总的时间效率为 ：T(n)=O(d(n+r)) head[0] head[1