5.排序算法分析 (1)时间复杂度 ●对n个记录排序,所需比较关键字的次数; 最好情况;最坏情况;平均情况 ●对n个记录排序,所需移动记录的次数; 最好情况;最坏情况;平均情况 (2)空间复杂度 排序过程中,除文件中的记录所占的空间外, 所需的辅助存储空间的大小。 6.内排序方法 (1)对顺序表的排序 ●插入排序:直接插入排序; 折半插入排序;2-路插入排序;表插入排序; 希尔(She11)排序; ●选择排序:简单选择/选择排序; 树形选择排序;堆排序
5.排序算法分析 (1)时间复杂度 ● 对n个记录排序，所需比较关键字的次数； 最好情况；最坏情况；平均情况 ● 对n个记录排序，所需移动记录的次数； 最好情况；最坏情况；平均情况 (2)空间复杂度 排序过程中，除文件中的记录所占的空间外， 所需的辅助存储空间的大小。 6.内排序方法 (1)对顺序表的排序 ● 插入排序：直接插入排序； 折半插入排序；2-路插入排序；表插入排序； 希尔(Shell)排序； ● 选择排序：简单选择/选择排序； 树形选择排序；堆排序
●归并排序 2-路归并排序 k-路归并排序 ●交换排序 冒泡排序:单向冒泡排序,双向冒泡排序 快速排序 ●基数排序 多关键字排序 最高位优先法 最低位优先法 链式基数排序 (2)对单链表的排序 直接插入,简单选择,冒泡排序,基数排序
● 归并排序 2-路归并排序 k-路归并排序 ● 交换排序 冒泡排序：单向冒泡排序，双向冒泡排序 快速排序 ● 基数排序 多关键字排序 最高位优先法 最低位优先法 链式基数排序 (2)对单链表的排序 直接插入,简单选择,冒泡排序,基数排序
10.2插入排序 算法基本思想 将待排序的记录插入到已排序的子文件中去,使得插入之后 得到的子文件仍然是有序子文件。插入一个记录,首先要对有序 子文件进行査找,以确定这个记录的插入位置。按查找方式的不 同,插入排序又可以分为线性插入排序和折半插入排序,前者使 用顺序查找,后者使用折半査找。 1.直接插入排序(线性插入排序) 设待排序的文件为(r[1],r[2],,r[n]) 关键字为(r[1].key,r[2].key,,r[n].key) 首先,将初始文件中的记录r[1]看作有序子文件; 第1遍:将r[2]插入有序子文件中:若r[2].key<r[1].key 则r[2]插在r[1]之前;否则,插在r[1的后面。 第2遍:将记录r[3]插入前面已有2个记录的有序子文件中, 得到3个记录的有序子文件 以此类推,依次插入r[4],.,r[n],最后得到n个记录的递 增有序文件
10.2 插入排序 算法基本思想 将待排序的记录插入到已排序的子文件中去，使得插入之后 得到的子文件仍然是有序子文件。插入一个记录，首先要对有序 子文件进行查找，以确定这个记录的插入位置。按查找方式的不 同，插入排序又可以分为线性插入排序和折半插入排序，前者使 用顺序查找，后者使用折半查找。 1.直接插入排序(线性插入排序) 设待排序的文件为(r[1],r[2],...,r[n]) 关键字为(r[1].key,r[2].key,...,r[n].key) 首先,将初始文件中的记录r[1]看作有序子文件； 第1遍：将r[2]插入有序子文件中：若r[2].key<r[1].key， 则r[2]插在r[1]之前；否则，插在r[1]的后面。 第2遍：将记录r[3]插入前面已有2个记录的有序子文件中， 得到3个记录的有序子文件。 以此类推，依次插入r[4],...,r[n],最后得到n个记录的递 增有序文件
例.直接插入排序,设K0为"监视哨” KO Kl K2 K3 K4 K5 K6 初始关键字 43)2189154328 (43后移) 第1遍(趟)排序后:21(2143)89154328 (不后移) 第2遍排序后:89(214389)154328 (89,43,21后移) 第3遍排序后 15(15214389)4328 (89后移) (89,43,43后移)43(1521434389)28 第4遍排序后:4 第5遍排序后:28(152128434389)
例. 直接插入排序, 设K0为"监视哨” K0 K1 K2 K3 K4 K5 K6 初始关键字： ( 43 ) 21 89 15 43 28 (43后移) ┌─┘ ↓ 第1遍(趟)排序后：21 ( 21 43 ) 89 15 43 28 (不后移) │ ↓ 第2遍排序后： 89 ( 21 43 89 ) 15 43 28 (89,43,21后移) ┌──────┘ ↓ 第3遍排序后： 15 ( 15 21 43 89 ) 43 28 (89后移) ┌─┘ ↓ 第4遍排序后： 43 ( 15 21 43 43 89 ) 28 (89,43,43后移) ┌──────┘ ↓ 第5遍排序后： 28 ( 15 21 28 43 43 89)
直接插入排序算法 void InsertSort (RecType r[, int n) //对数组r[1.n]中的n个记录作插入排序 I int i, j for(i=2; i=n: i++) r[0]=r[i]; //待插记录r[订]存入监视哨中 j=i-1 //从r[i1]开始向左扫描 while(rlo]. key<rLj]. key) r[j+1]=r[j; //记录后移 /继续向左扫描 r[j+1]=r[0]; //插入记录r[0],即原r[i]
直接插入排序算法 void InsertSort(RecType r[],int n） // 对数组r[1..n]中的n个记录作插入排序 { int i,j； for (i=2；i<=n；i++) { r[0]=r[i]； //待插记录r[i]存入监视哨中 j=i-1； //从r[i-1]开始向左扫描 while(r[0].key<r[j].key) { r[j+1]=r[j]； //记录后移 j--； //继续向左扫描 } r[j+1]=r[0]； //插入记录r[0],即原r[i] } }