数据结构-排序问题、希尔和归并排序.ppt

折半插入排序 void BiInsertionSort ( SqList L ) { } // BInsertSort 在 L.r[1..i-1]中折半查找插入位置； for ( i=2; i=L.length; ++i ) { } // for L.r[0] = L.r[i]; // 将 L.r[i] 暂存到 L.r[0] for ( j=i-1; j=high+1; --j ) L.r[j+1] = L.r[j]; // 记录后移 L.r[high+1] = L.r[0]; // 插入 折半插入排序 low = 1; high = i-1; while (low=high) { } m = (low+high)/2; // 折半 if (L.r[0].key L.r[m].key) high = m-1; // 插入点在低半区 else low = m+1; // 插入点在高半区 折半插入排序性能分析 1）折半插入排序所需附加存储空间和直接插入排序相同，从时间上来看，折半插入排序减少了关键字的比较次数，但是移动次数不变。 2）折半插入排序的时间复杂度为o(n2)。 3）折半插入排序是一个稳定的排序方法。 希尔排序 Shell在1959年提出，又称为缩小增量排序。 基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。 所谓“宏观”调整，指的是，“跳跃式”的插入排序。 希尔排序 将记录序列分成若干子序列，分别对每个子序列进行插入排序。 例如：将 n 个记录分成 d 个子序列： { R[1]，R[1+d]，R[1+2d]，…，R[1+kd] } { R[2]，R[2+d]，R[2+2d]，…，R[2+kd] } … { R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d] } 其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。 希尔排序 dk=5 1 2 3 4 5 6 7 8 9 10 65 97 76 13 27 49 55 04 49 38 第一趟 1 2 3 4 5 6 7 8 9 10 49 55 04 49 38 65 97 76 13 27 希尔排序 dk=3 第二趟 1 2 3 4 5 6 7 8 9 10 49 55 04 49 38 65 97 76 13 27 1 2 3 4 5 6 7 8 9 10 49 38 27 49 55 65 97 76 13 04 希尔排序 dk=1 第三趟 1 2 3 4 5 6 7 8 9 10 49 38 27 49 55 65 97 76 13 04 1 2 3 4 5 6 7 8 9 10 27 38 49 49 55 65 97 76 04 13 希尔排序 算法描述举例 int d[]={5,3,1}; 1 2 3 4 5 6 7 8 9 10 38 65 97 76 13 27 49 55 04 49 38 65 97 76 13 27 49 55 04 49 j i j i j i j i j i 第一趟 L.r[0].key= 13 27 49 55 04 dk=d[0]=5 希尔排序 算法描述举例 int d[]={5,3,1}; 1 2