第十章10排序.ppt

3．堆排序的基本思想 初始堆已经建立接着，可以按如下方法进行堆排序：将堆中第一个结点（二叉树根结点）和最后一个结点的数据进行交换（k1与kn），再将k1~kn-1重新建堆，然后k1和kn-1交换，再将k1~kn-2重新建堆，然后k1和kn-2交换，如此重复下去，每次重新建堆的元素个数不断减1，直到重新建堆的元素个数仅剩一个为止。这时堆排序已经完成，则排序码k1，k2，k3，…，kn已排成一个有序序列。 例 13 27 38 49 65 76 50 97 97 27 38 49 65 76 50 13 输出：13 27 49 38 97 65 76 50 13 输出：13 97 49 38 27 65 76 50 13 输出：13 27 38 49 50 27 65 76 97 13 输出：13 27 65 49 50 27 38 76 97 13 输出：13 27 38 49 65 50 27 38 76 97 13 输出：13 27 38 76 65 50 27 38 49 97 13 输出：13 27 38 49 50 65 76 27 38 49 97 13 输出：13 27 38 49 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 97 76 27 38 49 50 13 输出：13 27 38 49 50 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 76 65 97 27 38 49 50 13 输出：13 27 38 49 50 65 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 76 97 65 76 27 38 49 50 13 输出：13 27 38 49 50 65 76 97 将记录序列分成若干子序列，分别对每个子序列进行插入排序。 其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。 例如：将 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] } 例如： 16 25 12 30 47 11 23 36 9 18 31 第一趟希尔排序，设增量 d =5 11 23 12 9 18 16 25 36 30 47 31 第二趟希尔排序，设增量 d = 3 9 18 12 11 23 16 25 31 30 47 36 第三趟希尔排序，设增量 d = 1 9 11 12 16 18 23 25 30 31 36 47 例如，n=8，数组array[ ]的八个元素分别为：91，67，35，62，29，72，46，57。给出希尔排序算法的执行过程。 void ShellInsert ( SqList L, int dk ) { for ( i=dk+1; i=n; ++i ) if ( L.r[i].key L.r[i-dk].key) { L.r[0] = L.r[i]; // 暂存在R[0] for (j=i-dk; j0(L.r[0].keyL.r[j].key); j-=dk) L.r[j+dk] = L.r[j]; // 记录后移，查找插入位置 L.r[j+dk] = L.r[0]; // 插入 } // if } // ShellInsert void ShellSort (SqList L, int dlta[], int t) { // 增量为dlta[]的希尔排序 for (k=0; kt; ++t) ShellInsert(L, dlta[k]); //一趟增量为dlta[k]的插入排序 } // ShellSort 10.3 快 速 排 序 一、起(冒)泡排序 二、一趟快速排序 三、快速排序 四、快速排序的时间分析 一、起(冒)泡排序 　　假设在排序过程中，记录序列R[1..n]的状态为： 第 i 趟起泡排序 无序序列R[1..n-i+1] 有序序列 R[n-i+2..n] n-i+1 无序序列R[1..n-i] 有序序列 R[