【精品数据结构】排序算法.pptVIP

第 10 章 排序算法 §10.1 概述 排序的主要目的是便于以后在已排序的集合中查找检索某一成员 若干概念 关键字 排序 排序的稳定性 内排序 外排序 多键排序 §10.1 概述 排序方法进行分类 插入排序 交换排序 选择排序 归并排序 分配排序 §10.1 概述 算法的时间复杂性 通常只考虑键值的比较次数和记录的移动次数 评价排序的另一个主要标准是执行算法所需的附加空间 §10.2 插入排序 插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。 §10.2.1 直接插入排序 初始键值序列 [46] 58 15 45 90 18 10 62 i=2 [46 58] 15 45 90 18 10 62 i=3 [15 46 58] 45 90 18 10 62 i=4 [15 45 46 58] 90 18 10 62 i=5 [15 45 46 58 90] 18 10 62 i=6 [15 18 45 46 58 90] 10 62 i=7 [10 15 18 45 46 58 90] 62 i=8 [10 15 18 45 46 58 62 90] ? 图 10?1直接插入排序过程示例 §10.2.1 直接插入排序 可以将插入排序粗略地描述为： ? SortInsertion(int a[], long n) { for (i=1; in; i++) 将a[i]插入到a[0]—a[i-1]中，并使其保持有序 } 插入排序的程序： int SortInsertion(int a[], long n) { int x, i,,j; ? for (i=1; in; i++) { x=a[i]; j=i-1; while (j=0 xa[j]) { a[j+1] = a[j]; j--; } a[j+1] = x; } //for return 0; } §10.2.2 其他插入排序算法 除了直接插入排序外，还有其他形式的插入排序，如折半插入排序、表插入排序和希尔排序等。 它们是对直接插入排序的改进。改进的关键点是，如何尽快地找到插入位置。 §10.3 交换排序 所谓交换，就是根据记录集中两个记录键值的比较结果来对换这两个记录在序列中的位置 交换排序的特点是：将键值较大的记录向记录集的一端移动，键值较小的记录向另一端移动。 §10.3.1 冒泡排序 设初始记录集为 20 30 10 45 33 22 55 50 则第一趟冒泡的过程为： 20 30 10 45 33 22 55 50 //20与30比较，未交换 20 10 30 45 33 22 55 50 //30与10比较，交换 20 10 30 45 33 22 55 50 //30与45比较，未交换 20 10 30 33 45 22 55 50 //45与33比较，交换 20 10 30 33 22 45 55 50 //45与22比较，交换 10 30 33 22 45 55 50 //45与55比较，未交换 20 10 30 33 22 45 50 55 //55与50比较，交换 §10.3.1 冒泡排序 每趟的结果 10 20 30 22 33 45 50 55 //第2趟 10 20 22 30 33 45 50 55 //第3趟 10 20 22 30 33 45 50 55 //第4趟 10 20 22 30 33 45 50 55 //第5趟 10 20 22 30 33 45 50 55 //第6趟 10 20 22 30 33 45 50 55 //第7趟 10 20 22 30 33 45 50 55 //第8趟 §10.3.3 快速排序 (一)基本思想 基本思想是：在待排序的n个记录中任取一个记录（例如就取第一个记录），以该记录的键值为标准，将所有记录分为两组（一般都是无序的），使得第一组中各记录的键值均小于或等于该键值，第二组中各记录的键值均大于该键值。然后把该记录就排在这两组的中间（这也是该记录最终的位置）。此称为一趟分割，对所分成的两组再分别重复上述方法，直到所有记录都排在适当