答是要 7.1排序的基本概念 7.2内部排序 内部排序的分类 插入排序 交换排序 选择排序字 合并排序 计数排序 基数排序 内部排序方法比较 7.3外部排序字
内容提要 7.1 排序的基本概念 7.2 内部排序 • 内部排序的分类 • 插入排序 • 交换排序 • 选择排序 • 合并排序 • 计数排序 • 基数排序 • 内部排序方法比较 7.3 外部排序
7序的差水线念 1、排序:按照结点中的某项值对集合中结点进 行升序或降序的推列 2、关键字:排序时参照的数据项,有主次之分 3、稳定性:如果排序操作使等值结点的相对位置( 主要是指前后关保持不变,则排序是 稳定的,否如是不稳定的。 4、内部排序:排序序列放在内存中 5、外部排序:需要对外存进行访问
1、排 序：按照结点中的某项值对集合中结点进 行升序或降序的排列。 2、关 键 字：排序时参照的数据项，有主次之分 3、稳 定 性：如果排序操作使等值结点的相对位置( 主要是指前后关系)保持不变，则排序是 稳定的，否则是不稳定的。 4、内部排序：排序序列放在内存中 5、外部排序：需要对外存进行访问 7.1 排序的基本概念
1、内部排序的分类 间升度来分序的结点数量为m (1).,简单的序方法,O(m2) (2).先进的排序方法,Onog2n) (3).基数排序,O(n) 儿)序过程中所依据的原则来分 (1).插入排序 (2).交换排序 (3,选择排序 (4.合并排序 接照是否改变结点的物理位置来分 (1).物理重排 (2).不改变结点位置的排序,包括:链地址法,利用辅助地 址表排序,计数排序等
7.1 内排序 1、内部排序的分类 I.按照时间复杂度来分(排序的结点数量为n) (1).简单的排序方法，O(n2 ) (2).先进的排序方法，O(nlog2n) (3).基数排序，O(dxn) II.按照排序过程中所依据的原则来分 (1).插入排序 (2).交换排序 (3).选择排序 (4).合并排序 III.按照是否改变结点的物理位置来分 (1).物理重排 (2).不改变结点位置的排序，包括：链地址法，利用辅助地 址表排序，计数排序等
2、插入排序(1)直接插入排序 算法思想: (1)已知顺序存储的待排序序列a1a2a2,…,an (2)假设A是a1a2,,a序列,并已经有序,则待 排序列是Aka1…,,排序的基本操作是:将 ak+1有序插入到A中,这样循环往复,直到排 序完毕 (3)开始A={a1 (4)将a+1有序插入到A中的操作:先找到插入 位置,然后移动数据留出空间,再将a+1插入
算法思想： (1)已知顺序存储的待排序序列a1 ,a2 ,a3 ,….,an (2)假设Ak是a1 ,a2 ,..,ak序列，并已经有序，则待 排序列是Akak+1,…,an ,排序的基本操作是：将 ak+1有序插入到Ak中，这样循环往复，直到排 序完毕。 (3)一开始Ak={a1} (4)将ak+1有序插入到Ak中的操作：先找到插入 位置，然后移动数据留出空间，再将ak+1插入 内排序(cont’d) 2、插入排序 (1) 直接插入排序
2、插入排序(1)直接插入排 void insort( RECTYPE r,intn)∥升序排序 (RECTYPE temp; int i, j, low, hight, m for(i-l; i<n; i++) r[O]已经有序,从r[1开始 f ifr[i key<ri-1.key) 准备插入 i low=0; high=1-1 折半查找法,寻找插入位置 while(low<-high) i m=(low+high)/2 if(rm). key>r[i]. key )high=m-1 else if(r[m). key<r[i]. key) low-m+1 else (high=m; break; i i//while r[应该插在high+1的位置上 temp=r[i];∥保存r[,同时留出移动数据的空间 j=i-l;whil(-high+1){ri+1- Fru; J-}∥移动数 high+l=temp /插入 i// if )//for
void insort(RECTYPE r[], int n) //升序排序 {RECTYPE temp; int i, j, low, hight, m; for(i=1;i<n;i++) //r[0]已经有序，从r[1]开始 { if(r[i].key<r[i-1].key) //准备插入 { low=0; high=i-1; //折半查找法，寻找插入位置 while(low<=high) { m=(low+high)/2; if(r[m].key>r[i].key)high=m-1; else if(r[m].key<r[i].key) low=m+1; else {high=m; break;} }//while //r[i]应该插在high+1的位置上 temp=r[i]; //保存r[i]，同时留出移动数据的空间 j=i-1; while(j>=high+1){r[j+1]=r[j]; j--; }; //移动数据 r[high+1]=temp; //插入 }// if }//for } 内排序(cont’d) 2、插入排序 (1) 直接插入排序