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;i<n;计+)t=i,初始化辅助地址表 for(i=l; i<n; 1++) fif(r[t[i. key<r[t[i-1].key) fF=i-1; temp=t[ while(i=o&&rt[ill. key>temp. 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<n;i++) t[i]=i; //初始化辅助地址表 for(i=1;i<n;i++) {if(r[t[i]].key<r[t[i-1]].key) { j=i-1; temp=t[i]; while(j>=0&&r[t[j]].key>r[temp].key) { t[j+1]=t[j]; j--; } //寻找插入位置的同时，移动数据 t[j+1]=temp; //插入 } } } 内排序(cont’d) 2、插入排序 (4) 辅助地址表的插入排序