第10章排序算法
1 第 10 章 排序算法
s101概述 排序的主要目的是便于以后在已排序的集合中查找检 索某一成员 若干概念 关键字 排序 排序的稳定性 内排序 外排序 多键排序
2 §10.1 概述 • 排序的主要目的是便于以后在已排序的集合中查找检 索某一成员 • 若干概念 – 关键字 – 排序 – 排序的稳定性 – 内排序 – 外排序 – 多键排序
s101概述 排序方法进行分类 插入排序 交换排序 选择排序 归并排序 分配排序
3 §10.1 概述 • 排序方法进行分类 – 插入排序 – 交换排序 – 选择排序 – 归并排序 – 分配排序
s101概述 算法的时间复杂性 通常只考虑键值的比较次数和记录的移动次数 评价排序的另一个主要标准是执行算法所需的附加空
4 §10.1 概述 • 算法的时间复杂性 – 通常只考虑键值的比较次数和记录的移动次数 • 评价排序的另一个主要标准是执行算法所需的附加空 间
§102插入排序 插入排序的基本方法是:每步将一个待排序的记录按 其关键字的大小插到前面已经排序的序列中的适当位 置,直到全部记录插入完毕为止
5 §10.2 插入排序 • 插入排序的基本方法是：每步将一个待排序的记录按 其关键字的大小插到前面已经排序的序列中的适当位 置，直到全部记录插入完毕为止
§1021直接插入排序 初始键值序列 [46 5 45 18 62 i=2[46 15 18 3[15 46 58 45 i=4[15 45 46 58] 18 62 i=5[15 45 46 58 ]18 62 =6[15 18 45 i=7[10 18 45 58 =8[10 15 18 45 46 58 62 图10-1直接插入排序过程示例
6 §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直接插入排序过程示例
§1021直接插入排序 可以将插入排序粗略地描述为: SortInsertion(int all, long n) for(i-1; i<n; i++) 将a[插入到a]a[i-1中,并使其保持有序
7 §10.2.1 直接插入排序 •可以将插入排序粗略地描述为： SortInsertion(int a[], long n) { for (i=1; i<n; i++) 将a[i]插入到a[0]—a[i-1]中，并使其保持有序 }
插入排序的程序 int SortInsertion(int all, longan int x for(i-1; K<n; 1++) Xa while (p=o & x<alD alj+1=aljI a[j+1]=X }∥for return o
8 插入排序的程序： int SortInsertion(int a[], long n) { int x, i,,j ; for (i= 1 ; i= 0 && x<a[j]) { a[j+ 1 ] = a[j] ; j-- ; } a[j+ 1 ] = x ; } //for return 0 ; }
§10.22其他插入排序算法 除了直接插入排序外,还有其他形式的插入排序,如折半插入 排序、表插入排序和希尔排序等。 它们是对直接插入排序的改进。改进的关键点是,如何尽快地 找到插入位置
9 §10.2.2 其他插入排序算法 •除了直接插入排序外，还有其他形式的插入排序，如折半插入 排序、表插入排序和希尔排序等。 •它们是对直接插入排序的改进。改进的关键点是，如何尽快地 找到插入位置
§10.3交换排序 所谓交换,就是根据记录集中两个记录键值的比较结果来对换 这两个记录在序列中的位置 ·交换排序的特点是:将键值较大的记录向记录集的一端移动, 键值较小的记录向另一端移动
10 §10.3 交换排序 •所谓交换，就是根据记录集中两个记录键值的比较结果来对换 这两个记录在序列中的位置 •交换排序的特点是：将键值较大的记录向记录集的一端移动， 键值较小的记录向另一端移动