第八章内排序2Shell排序又称为“缩小增量排序”，1959年由提出总的排序码比较次数将达if(left<right){//如果序列中只有0或1个记录，就不用排序分割后使得L中所有记录位于轴值左边，R中记录位于轴值右边，即轴值已位于正确位置//依次找出剩余记录中的最大记录，即堆顶“delta=2”的Shell排序if(right<=left)//如果子序列中只有0或1个记录，就不需排序希尔排序是一种不稳定的排序方法elseArray[k]=TempArray[index2--];classQuickSorter:publicSorter<Record,Compare>{//快速排序类elseInsertSort(&Array[left],right-left+1);直接选择排序：直接从剩余记录中线性查找最大(小)记录template<classRecord,classCompare>ModMerge(Array,TempArray,left,right,middle);//进行归并if(right-left+1>THRESHOLD){把数组暂时复制到临时数组时，将第二个子数组中元素的顺序颠倒了一下。形式化描述567分析9快速排序11在n个元素的序列中,对一个对象定位所需时间为O(n)。08162125*2549该思想是解决问题的重要方法之一ModifiedInsertSort(RecordArray[],intn,intdelta)while(index1<=middle&&index2<=right){//若长度小于等于阈值，采用直接插入排序首先，从待排序序列S中任意选择一个记录k作为轴值inti,j,index1,index2;VoidShellSorter<Record,Compare>::Sort(RecordArray[],intn)if(i<j){Array[i]=Array[j];i++;}//i指针向右移动一步(2534)(4532)(7812)(34’64)while(Compare::gt(Array[j],TempRecord)&&(j>i))j--;其中n—文件长度；13left08161718192021222324(25344532781234’64)2627while(index1<=middle)//只剩左序列，可以直接复制Array[i++]=TempArray[index1++];while(index2<=right)//与上个循环互斥，直接复制剩余的右序列Array[i++]=TempArray[index2++];}归并排序性能分析30313233基本思想//若长度小于等于阈值，采用直接插入排序RecordTempRecord;//存放轴值的临时变量08162125*2549T(n)=cn+2T(n/2)//c是一个常数“delta=2”的Shell排序//若长度小于等于阈值，采用直接插入排序intPartition(RecordArray[],intleft,intright);//分割,返回轴值位置if(left<right){//如果序列中只有0或1个记录，就不用排序return(left+right)/2;//选择中间纪录作为轴值if(Array[j]<Array[j-delta])交换0号与1号记录for(intj=0;j<delta;j++)while(index1<=middle)//只剩左序列，可以直接复制基于最大（小）堆来实现，效率更高(霍尔)1962.#defineTHRESHOLD9或16或28最大递归调用层次数与递归树的高度一致,理想情况为log2(n+1)。363738394041再见…