答是要 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; ir[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;ir[i].key)high=m-1; else if(r[m].key=high+1){r[j+1]=r[j]; j--; }; //移动数据 r[high+1]=temp; //插入 }// if }//for } 内排序(cont’d) 2、插入排序 (1) 直接插入排序
2、插入排序(2)改进插入排序之一:二路插入 4938659776132749 ■■■■A 4949 97132738 final first
内排序(cont’d) 2、插入排序 (2) 改进插入排序之一：二路插入 49 38 65 97 76 13 27 49 Final 49 First 38 First 65 Final 97 Final 76 97 Final 13 First 13 27 First 49 65 76 97 Final
2、插入排序(3)改进插入排序之二:希尔排序 算法思想: 先将待排纪录分成若干子列分别用直 接插入法排序,再对全体纪录用直接插 入法排序。 理论根据:直接排序序列越短越好,源 序列的排序度越好效率越高
算法思想： 先将待排纪录分成若干子列分别用直 接插入法排序，再对全体纪录用直接插 入法排序。 理论根据：直接排序序列越短越好，源 序列的排序度越好效率越高。 内排序(cont’d) 2、插入排序 (3) 改进插入排序之二：希尔排序
2、插入排序()改进插入排序之二:希尔排序 4938659776132749554 趟排序结果: 13275544938659776 二趟排序结果: 134 38274955659776 三趟排序结果: 4132738449556576
内排序(cont’d) 2、插入排序 (3) 改进插入排序之二：希尔排序 49 38 65 97 76 13 27 49 55 4 一趟排序结果： 13 27 49 55 4 49 38 65 97 76 二趟排序结果： 13 4 49 38 27 49 55 65 97 76 三趟排序结果： 4 13 27 38 49 49 55 65 76 97
AsF contd 2、插入排序(4)辅助地址表的插入排序 算法思想: 直接插入排序需要移动结点数据,如果结点数 据比较大,需要移动的内存就比较多。如果建 立一个辅助地址表,每个单元都指向一个结点, 然后对地址表按照结点关键字进行排序,将会 减少数据移动的数量
算法思想： 直接插入排序需要移动结点数据，如果结点数 据比较大，需要移动的内存就比较多。如果建 立一个辅助地址表，每个单元都指向一个结点， 然后对地址表按照结点关键字进行排序，将会 减少数据移动的数量 内排序(cont’d) 2、插入排序 (4) 辅助地址表的插入排序
2、插入排序(4辅助地址表的插入排序 void insort(RECTYPErl, int n, int t t是辅助地址表,每个单元是r中结点的下标 Int temp. I p for(i=0;itemp. key) ti计+1]}=t;j-;}∥寻找插入位置的同时,移动数据 ti+1]=temp;∥插入
void insort(RECTYPE r[], int n, int t[]) {//t是辅助地址表，每个单元是r中结点的下标 int temp, i, j; for(i=0;i=0&&r[t[j]].key>r[temp].key) { t[j+1]=t[j]; j--; } //寻找插入位置的同时，移动数据 t[j+1]=temp; //插入 } } } 内排序(cont’d) 2、插入排序 (4) 辅助地址表的插入排序