10.3 （交换）快 速 排 序（知识点二） 一、起泡排序 二、一趟快速排序 三、快速排序 四、快速排序的时间分析

假设在排序过程中，记录序列R[1..n]的状态为： 一、起泡排序 　　假设在排序过程中，记录序列R[1..n]的状态为： n-i+1 无序序列R[1..n-i+1] 有序序列 R[n-i+2..n] 比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上 第 i 趟起泡排序 无序序列R[1..n-i] 有序序列 R[n-i+1..n]

for (j = 1; j <= n-i; j++) void BubbleSort(Elem R[ ], int n) { for (i = 1; i <= n-1; i++) } // BubbleSort if (R[j].key > R[j+1].key) { Swap(R[j], R[j+1]); } //if for (j = 1; j <= n-i; j++) 问题？怎样改进 i控制趟数

2. 一般情况下，每经过一趟“起泡”， “i 减一”，但并不是每趟都如此。 1. 起泡排序的结束条件为， 最后一趟没有进行“交换记录”。 2. 一般情况下，每经过一趟“起泡”， “i 减一”，但并不是每趟都如此。 例如: 2 1 3 5 5 1 3 5 7 9 8 9 i=2 i=6 i=7 for (j = 1; j < i; j++) if (R[j+1].key < R[j].key) …

i = n; lastExchangeIndex = 1; void BubbleSort(Elem R[ ], int n) { while (i >1) { } // while } // BubbleSort i = n; lastExchangeIndex = 1; if (R[j].key > R[j+1].key) { Swap(R[j], R[j+1]); lastExchangeIndex = j; //记下进行交换的记录位置 } //if for (j = 1; j < i; j++) i = lastExchangeIndex; // 本趟进行过交换的 // 最后一个记录的位置

算法的时间分析—— 最好的情况（关键字在记录序列中顺序有序）： 只需进行一趟起泡 “比较”的次数： “移动”的次数： n-1 最坏的情况（关键字在记录序列中逆序有序）： 需进行n-1趟起泡 “比较”的次数： “移动”的次数：

二、一趟快速排序（一次划分） 目标： 在无序序列R[s..t]找一个记录，以它的关键字作为“枢轴” 凡其关键字小于枢轴的记录均移动至该记录之前 凡关键字大于枢轴的记录均移动至该记录之后。 致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t]，且 R[j].key≤ R[i].key ≤ R[k].key (s≤j≤i-1) 枢轴 (i+1≤k≤t)。

R[j].key≤ R[i].key ≤ R[k].key 一趟排序之后，记录的无序序列R[s..t]将分割成两部分： R[s…t] 无 序 的 记 录 序 列 一次划分 R[s…i-1] R[i+1…t] 无序记录子序列(1) 枢轴 无序子序列(2) R[j].key≤ R[i].key ≤ R[k].key (s≤j≤i-1) 枢轴 (i+1≤k≤t)。

将 R[high].key 和 枢轴的关键字进行比较，要求R[high].key ≥ 枢轴的关键字 s R[0] 52 t 23 14 52 80 例如 low low low low low high high high high high high 设 R[s]=52 为枢轴 将 R[high].key 和 枢轴的关键字进行比较，要求R[high].key ≥ 枢轴的关键字 将 R[low].key 和 枢轴的关键字进行比较，要求R[low].key ≤ 枢轴的关键字

指针 low 和high的初值分别为： s 和 t， 可见，经过“一次划分” ，将关键字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 指针 low 和high的初值分别为： s 和 t， 之后逐渐减小 high，增加 low，并保证 R[high].key≥52，和 R[low].key<52,否则进行记录的“交换”。

int Partition (RcdType R[], int low, int high) { R[0] = R[low]; pivotkey = R[low].key; // 枢轴 while (low<high) { } while(low<high&& R[high].key>=pivotkey) -- high; // 从右向左搜索 R[low] = R[high]; while (low<high && R[low].key< pivotkey) ++ low; // 从左向右搜索 R[high] = R[low]; R[low] = R[0]; return low; 一次划分

三、快速排序 分别进行快速排序 一次划分 首先对无序的记录序列进行“一次划分”,之后分别对分割所得两个子序列“递归”进行快速排序。 无 序 的 记 录 序 列 一次划分 无序记录子序列(1) 枢轴 无序子序列(2) 分别进行快速排序

第一次调用函数 Qsort 时，待排序记录序列的上、下界分别为 1 和 L.length。 void QuickSort( SqList & L) { // 对顺序表进行快速排序 QSort(L.r, 1, L.length); } // QuickSort

void QSort (RedType & R[], int s, int t ) { // 对记录序列R[s..t]进行快速排序 if (s < t) { } } // QSort pivotloc = Partition(R, s, t); // 对 R[s..t] 进行一次划分 QSort(R, s, pivotloc-1); // 对低子序列递归排序，pivotloc是枢轴位置 QSort(R, pivotloc+1, t); // 对高子序列递归排序 一次划分

int Partition (RcdType R[], int s, int t) { k = R[s]; // 枢轴 while (s<t) { } while(s<t&& R[t].key>=k.key) -- t; // 从右向左搜索 R[s] = R[t]; while (s<t && R[s].key< k.key) ++ s; // 从左向右搜索 R[t] = R[s]; R[s] =k; return s; 一次划分

例：对( 90, 45, 39, 54, 68, 87, 76 ) 进行快速排序，会发现什么特殊情况？ 　 由于枢轴记录的关键字“90”大于其它所有记录的关键字，致使一次划分之后得到的子序列(2)的长度为0，由此可看出，快速排序不适于对原本有序或基本有序的记录序列进行排序。　　

为避免出现枢轴记录关键字为"最大"或"最小"的情况，需在进行一次划分之前，进行“予处理”，即： 先对 R(s).key, R(t).key 和 R[(s+t)/2].key，进行相互比较，然后取关键字为 “三者之中”的记录为枢轴记录。 如果借用起泡排序中设置记录“交换与否”的布尔变量的作法，快速排序也适用于已经有序的记录序列 。 为避免出现枢轴记录关键字为"最大"或"最小"的情况，通常进行的快速排序采用"三者取中"的改进方案，即以 R[s]、R[t] 和 R[(s+t)/2] 三者中关键字介于中值者为枢轴。只要将它和 R[s] 互换，一次划分的算法仍不变。

快速排序的平均时间复杂度为O (nlogn)。 四、快速排序的时间分析 (1) 可以推证： 快速排序的平均时间复杂度为O (nlogn)。 是不稳定排序。 (2) 若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n )。 (3) 在三者取中的前提下，对随机的关键字序列，快速排序是目前被认为是最好的排序方法。 2 为避免出现枢轴记录关键字为"最大"或"最小"的情况，通常进行的快速排序采用"三者取中"的改进方案，即以 R[s]、R[t] 和 R[(s+t)/2] 三者中关键字介于中值者为枢轴。只要将它和 R[s] 互换，一次划分的算法仍不变。

10.4 堆 排 序 （选择类） 简 单 选 择 排 序 堆 排 序

一、简单选择排序 假设排序过程中，待排记录序列的状态为： 有序序列R[1..i-1] 无序序列 R[i..n] 第 i 趟 简单选择排序 从中选出 关键字最小的记录 第 i 趟 简单选择排序 有序序列R[1..i] 无序序列 R[i+1..n]

初 始 [36 25 48 12 65 43 20 58] 12 [25 48 36 65 43 20 58] 12 20 [48 36 65 43 25 58] 20 25 [36 65 43 48 58] 20 25 36 [65 43 48 58] 12 20 25 36 43 [65 48 58] 12 20 25 36 43 48 [65 58] 12 20 25 36 43 48 58 65 直 接 选择 排序 示 例 第一趟 第二趟 第三趟 第四趟 第五趟 第六趟 第七趟

初 始 49 38 65 97 76 13 27 49’ 直 接 选择 排序 示 例 第一趟 13 38 65 97 76 49 27 49’ 第二趟 13 27 65 97 76 49 38 49’ 第三趟 13 27 38 97 76 49 65 49’ 第四趟 13 27 38 49 76 97 65 49’ 第五趟 13 27 38 49 49’ 97 65 76 第六趟 13 27 38 49 49’ 65 97 76 第七趟 13 27 38 49 49’ 65 76 97

简单选择排序的算法描述如下： void SelectSort (Elem R[], int n ) { // 对记录序列R[1..n]作简单选择排序。 for (i=1; i<n; ++i) { // 选择第 i 小的记录，并交换到位 } } // SelectSort j = SelectMinKey(R, i); // 在 R[i..n] 中选择关键字最小的记录 if (i!=j) R[i]←→R[j]; // 与第 i 个记录交换

// P277算法10.9 对顺序表L作简单选择排序。 void SelectSort(SqList &L) { int i,j; RedType t; for (i=1;i<L.length;++i) { // 选择第i小的记录，并交换到位 j=SelectMinKey(L,i); // 在L.r[i..L.length]中选择key最小的记录 if (i!=j) { // 与第i个记录交换 t= L.r[i]; L.r[i]=L.r[j]; L.r[j]=t; }

移动记录的次数: 最小值为 0, 对 n 个记录进行简单选择排序，所需进行的 关键字间的比较次数 总计为： 时间性能分析 　　移动记录的次数: 最小值为 0, 最大值为3(n-1) 。

堆排序的特点是，在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果。 二、堆排序 堆排序的特点是，在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果。 堆排序是在简单选择排序基础上的改进算法。简单选择排序的主要操作是进行关键字的比较，如果能减少比较的次数而又完成排序则就能提高排序的速度。显然在ｎ个关键字中选出最小值，至少要进行ｎ-１次比较；而在剩下的ｎ-１个关键字中选择次小值并非一定要进行ｎ-２次比较，若能利用前面ｎ-１次比较的信息，就可以减少以后各趟选择排序中的比较次数。

堆是满足下列性质的数列{r1, r2, …，rn}： 堆的定义: 堆是满足下列性质的数列{r1, r2, …，rn}： (小顶堆) 或 (大顶堆) 例如: {12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 是小顶堆 {12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49} 不是堆 从堆的定义可以看出，堆实质上是满足如下性质的二叉树：树中任一非叶子结点的关键字均小于或等于它的孩子结点的关键字。

若将该数列视作完全二叉树， 则 r2i 是 ri 的左孩子； r2i+1 是 ri 的右孩子。 ri r2i r2i+1

例如: {12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 12 36 27 65 40 34 98 是堆 81 73 55 49

例如: {12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 12 36 27 65 40 34 14 98 不 是堆 81 73 55 49

不是堆 是大顶堆 （1）96、83、27、38、11、09、25、37、08 （2）15，56，20，60，40，38，29，61 例： T1 是大顶堆 不是堆

堆排序的具体作法是： 将待排序元素序列对应的完全二叉树建成一个“大顶堆”，即先选得一个关键字为最大的记录; 然后与序列中最后一个记录交换(输出); 继续对序列中前n-1记录进行“筛选”，重新将它调整为一个“大顶堆”，再将堆顶（次大）记录和第n-1个记录交换，如此反复直至排序结束。

两个问题: (1) 如何“建堆”？ (2) 如何“筛选”？ 定义堆类型为: typedef SqList HeapType; // 堆采用顺序表表示之 两个问题: (1) 如何“建堆”？ (2) 如何“筛选”？ 由堆的定义得知，二叉树中的非终结点的元素值均大于等于(不小于）它的左右孩子结点的元素值，故而二叉树的根必为序列中的最大值，如果输出根结点（堆顶）这一的最大值后，能够将剩余的元素序列重新调整成一个堆，便可求得次大值，重复执行，就得到一个有序序列，这个过程称为堆排序。 完成堆排序必须解决两个问题： 如何使原始元素序列建成一个堆？ 输出堆顶元素后如何调整出一个新的堆？ 其实建堆的过程也就是将待排序元素序列（一维数组存储）对应的完全二叉树(完全二叉树可用顺序存储)调整形成一个堆，所以解决问题的关键在于如何调整元素间的关系形成堆。

所谓“筛选”指的是，对一棵左/右子树 均为堆的完全二叉树，“调整”根结点 使整个二叉树也成为一个堆。 筛选 堆 堆

例如: 是大顶堆 但在 98 和 12 进行互换之后，它就不是堆了， 因此，需要对它进行“筛选”。 12 12 81 98 73 81 49 比较 12 81 98 比较 73 81 49 64 73 36 27 40 55 64 12 98 12 98 是大顶堆 但在 98 和 12 进行互换之后，它就不是堆了， 因此，需要对它进行“筛选”。

堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。 　堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。 例如： 98 40 55 81 98 49 49 73 81 73 12 36 36 27 27 98 49 40 81 55 73 64 64 12 12 36 建大顶堆 交换 98 和 12，重新调整为大顶堆 { 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 } { 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 }建大顶堆 { 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 }交换 98 和 12 { 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 }重新调整为大顶堆

现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。 建堆是一个从下往上进行“筛选”的过程。 例如: 排序之前的关键字序列为 40 98 81 55 98 49 49 73 81 73 12 36 36 27 27 98 49 40 81 55 73 64 64 12 12 36 现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。 由二叉树的性质5得知二叉树中序号最大的一个非终结点（分支结点）是ｎ／２（下取整），即图中的5号结点36，序号最小的非终结点是序号为１的结点即根结点，对这些点需一一进行调整，使满足堆定义中的条件。 调整过程为：首先把该分支结点元素36与其两个孩子中值大者进行交换（由于只有一个左孩子故12只和36比较），由于36大于12故不用交换，则以36为根的子树即为堆，接着用相同的步骤对第４个元素进行调整直至第一个元素，如果在中间调整过程中，由于交换破坏了以其孩子为根的堆，则要对破坏了的堆进行调整，依此类推，直到父结点大于等于左、右孩子的元素结点，这个调整过程也叫做“筛选”。

建堆是一个从下往上进行“筛选”的过程。 例如: 排序之前的关键字序列为 36 76 12 25 36 65 76 25 48 58 76 73 12 65 36 25 43 98 25 73 58 81 64 12 76 32 12 36

如何由一个无序序列建成一个堆？ 28 25 16 32 18 36 28 25 18 36 16 25 32 16 32 16 28 28 32 36 28 18 36 25 16 18 25

void HeapSort ( HeapType &H ) { for ( i=H.length/2; i>0; --i )//从最后一个父结点开始调整 HeapAdjust ( H.r, i, H.length ); // 建大顶堆 for ( i=H.length; i>1; --i ) { H.r[1]←→H.r[i]; // 将堆顶记录和当前未经排序子序列 // H.r[1..i]中最后一个记录相互交换 HeapAdjust(H.r, 1, i-1); // 对 H.r[1] 进行筛选 }

void HeapAdjust (RcdType &R[], int s, int m) { R[0] = R[s]; // 暂存 R[s] for ( j=2*s; j<=m; j*=2 ) { // j 初值指向左孩子 if ( j<m && R[j].key<R[j+1].key ) ++j; if ( rc.key >= R[j].key ) break; R[s] = R[j]; s = j; } R[s] = R[0]; // 将调整前的堆顶记录插入到 s 位置 void HeapAdjust (RcdType &R[], int s, int m)//s是待筛选的父节点，m除去已输出结点总数 { // 已知 R[s..m]中记录的关键字除 R[s] 之外均 满足堆的特征，本函数自上而下调整 R[s] 的 关键字，使 R[s..m] 也成为一个大顶堆 rc = R[s]; // 暂存 R[s] for ( j=2*s; j<=m; j*=2 ) { // j 初值指向左孩子 （如果j<m,说明一定有右孩子） if ( j<m && R[j].key<R[j+1].key ) ++j; // 左/右“子树根”之间先进行相互比较 // 令 j 指示关键字较大记录的位置 if ( rc.key >= R[j].key ) break; // 再作“根”和“子树根”之间的比较 // 若“>=”成立，则说明已找到 rc 的插 入位置 s ，不需要继续往下调整 R[s] = R[j]; s = j; // 否则记录上移，尚需继续往下调整 } } // HeapAdjust

for ( j=2*s; j<=m; j*=2 ) { // j 初值指向左孩子 R[0] = R[s]; // 暂存 R[s], s=1, m=9 for ( j=2*s; j<=m; j*=2 ) { // j 初值指向左孩子 if ( j<m && R[j].key<R[j+1].key ) ++j; if (R[0] .key >= R[j].key ) break; R[s] = R[j]; s = j; } R[s] = R[0] ; s=2， m=9 j=2*j=4 s=4， m=9 j=j+1=9 s=4， m=9 j=2*j=8 s=9， m=9 j=2*j=18>m s=1， m=9 j=2*s=2 S 98 81 12 R[0] = 12 j S 比较 73 81 49 j S 73 64 36 27 40 j j 55 64 12 98 98 12 void HeapAdjust (RcdType &R[], int s, int m) { // 已知 R[s..m]中记录的关键字除 R[s] 之外均 满足堆的特征，本函数自上而下调整 R[s] 的 关键字，使 R[s..m] 也成为一个大顶堆 rc = R[s]; // 暂存 R[s] for ( j=2*s; j<=m; j*=2 ) { // j 初值指向左孩子 if ( j<m && R[j].key<R[j+1].key ) ++j; // 左/右“子树根”之间先进行相互比较 // 令 j 指示关键字较大记录的位置 if ( rc.key >= R[j].key ) break; // 再作“根”和“子树根”之间的比较 // 若“>=”成立，则说明已找到 rc 的插 // 入位置 s ，不需要继续往下调整 R[s] = R[j]; s = j; // 否则记录上移，尚需继续往下调整 } } // HeapAdjust

堆排序的时间复杂度： 可以证明 堆排序的时间复杂度为O(nlogn) 。 适合大量记录的排序。 需要一个记录大小的辅助存储空间。 方法不稳定。 和选择排序雷同，无论待排序列中的记录是正序还是逆序排列，都不会使堆排序处于“最好”或“最坏”的状态。 1. 对深度为 k 的堆，“筛选”所需进行的关键字 比较的次数至多为2(k-1)； 2. 对 n 个关键字，建成深度为h(=log2n+1)的堆， 所需进行的关键字比较的次数至多 4n； 3. 调整“堆顶” n-1 次，总共进行的关键 字比较的次数不超过 2 (log2(n-1)+ log2(n-2)+ …+log22) < 2n(log2n)