d0{ LL+1=lli while gj>=left & temp <LlD LL+1]temp;
do { L[j+1] = L[j]; j--; } while (j >= left && temp < L[j]); L[j+1] = temp; } }; 16
设待排序元素个数为 currentsize=n,则该算法的主程序执 行n-1趟。排序码比较次数和元素移动次数与元素排序码 的初始排列有关。 最好情况下,排序前元素已按排序码从小到大有序,每趟 只需与前面有序元素序列的最后一个元素比较1次,总的 排序码比较次数为n-1,元素移动次数为0。 最坏情况下,第i趟时第i个元素必须与前面i个元素都做 排序码比较,并且每做1次比较就要做1次数据移动。则总 排序码比较次数KCN和元素移动次数RMN分别为 KCN=∑i=m(n-1)/2≈n2/2 RMN=∑(i+2)=(n+4n-1)/2≈m2/2 平均情况下,排序的时间复杂度为O(m2) 直接插入排序是一种稳定的排序方法。 17
• 设待排序元素个数为currentSize = n, 则该算法的主程序执 行n-1趟。排序码比较次数和元素移动次数与元素排序码 的初始排列有关。 • 最好情况下，排序前元素已按排序码从小到大有序，每趟 只需与前面有序元素序列的最后一个元素比较1次，总的 排序码比较次数为 n-1, 元素移动次数为0。 • 最坏情况下, 第 i 趟时第 i 个元素必须与前面 i 个元素都做 排序码比较, 并且每做1次比较就要做1次数据移动。则总 排序码比较次数KCN和元素移动次数RMN分别为 • 平均情况下，排序的时间复杂度为 O(n 2 )。 • 直接插入排序是一种稳定的排序方法。 − = − = = + = + − = = − 1 1 1 1 2 4 1 2 2 1 2 2 n i n i RMN i n n n KCN i n n n ( ) ( )( )/ / ( )/ / , 2 2 17
折插入排序( Binary Insert Sort) 基本思想是: 设在顺序表中有一个元素序列v0],Ⅴul,…, V|n-1l其中,V0,Ⅵ1,…,V-1是已经排好 序的元素。在插入Ⅴ时,利用折半搜索法寻找 V[a的插入位置
折半插入排序 (Binary Insert Sort) • 基本思想是 : 设在顺序表中有一 个元素序列 V[0], V[1], …, V[n-1]。其中, V[0], V[1], …, V[i-1] 是已经排好 序的元素。在插入V[i] 时, 利用折半搜索法寻找 V[i] 的插入位置。 18
折半插入排序的算法 #include "dataList.h" template <class t void Binarylnsertsort(dataList<t>&l, const int left, const int right)i /剩用折半搜索,在 L Vector[left到 L Vector1中 找 L Vector应插入的位置,再进行插入。 Element<I> temp; int 1, low, high, middle, k; for(i=left+1; i<=right; i++) temp=ll]; low= left; high=1-1 while(ow<=high){∥折半搜索寻找插入位置 middle=(ow+high)/2;∥/取中点
折半插入排序的算法 #include "dataList.h" template <class T> void BinaryInsertSort (dataList<T>& L, const int left, const int right) { //利用折半搜索, 在L.Vector[left]到L.Vector[i-1]中 //查找L.Vector[i]应插入的位置, 再进行插入。 Element<T> temp; int i, low, high, middle, k; for (i = left+1; i <= right; i++) { temp = L[i]; low = left; high = i-1; while (low <= high) { //折半搜索寻找插入位置 middle = (low+high)/2; //取中点 19
if(temp< MIddle])∥插入值小于中点值 high= middle-1;//向左缩小区间 else low= middle+1 否则向右缩小区间 for(k=1-l; k>=low; k--L[k+1=lk]; //成块移动空出插入位置 L[ow]=temp;∥插入
if (temp < L[middle]) //插入值小于中点值 high = middle-1; //向左缩小区间 else low = middle+1; //否则, 向右缩小区间 } for (k = i-1; k >= low; k--) L[k+1] = L[k]; //成块移动,空出插入位置 L[low] = temp; //插入 } }; 20