算法的基本思想： 第6章 内部排序 6.2 气泡排序 将待排序的记录看作是竖着排列的“气泡”，关键字较小 的记录比较轻，从而要往上浮。 对这个“气泡”序列进行n-1遍（趟）处理。所谓一遍（趟 ）处理，就是自底向上检查一遍这个序列，并注意两个 相比较的关键字的顺序是否正确。如果发现顺序不对， 即 “轻”的记录在下面，就交换它们的位置。 显然，处理1遍之后，“最轻”的记录就浮到了最高位置； 处理2遍之后，“次轻”的记录就浮到了次高位置。在作第 二遍处理时，由于最高位置上的记录已是“最轻”的，所 以不必检查。一般地，第i遍处理时，不必检查第i高位置 以上的记录的关键字，因为经过前面i-1遍的处理，它们 已正确地排好序。 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-9

void BubbleSort ( int n , LIST &A ) 第6章 内部排序 6.2 气泡排序（cont.） 算法的实现： void BubbleSort ( int n , LIST &A ) { for ( int i =1; i <= n-1; i++ ) for ( int j =n; j >= i+1; j-- ) if ( A[j].key < A[j-1] ) swap (A[j], A[j-1]) } void swap(records &x, records &y) { records w ; w=x; x=y; y=w; } 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-10

算法（时间）性能分析： 最坏情况（反序）： n (n1) 3n(n1) 移动次数： i13(n-i)  第6章 内部排序 6.2 气泡排序（cont.） 算法（时间）性能分析： 最好情况（正序）： 比较次数：n-1 移动次数：0 时间复杂度： O(n)； 最坏情况（反序）： n-1 比较次数：  (n-i)  i1 n (n1) 2 n-1 移动次数： i13(n-i) 3n(n1) 2   时间复杂度： O(n2)； 平均情况：时间复杂度为O(n2)。 空间复杂度： O(1)。 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-11

快速算法是对气泡排序的改进，改进的着眼点： 第6章 内部排序 6.3 快速排序 快速算法是对气泡排序的改进，改进的着眼点： 在气泡排序中，记录的比较和移动是在相邻单元中进行 的，记录每次交换只能上移或下移一个单元，因而总的 比较次数和移动次数较多。 减少总的比较次数和移动次 •增大记录的比较和移动距 较大记录从前面直接移动到后面 较小记录从后面直接移动到前面 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-12

算法的基本思想： 第6章 内部排序 6.3 快速排序（cont.） 是C.R.A.Hoare 1962年提出的一种划分交换排序。采用的 是分治策略(一般与递归技术结合使用)，以减少排序过程 中的比较次数。 通过一趟排序将要排序的数据分割成独立的两部分，其中 一部分的所有数据都比另外一不部分的所有数据都要小， 然后再按此方法对这两部分数据分别进行快速排序，整个 排序过程可以递归进行，以此达到整个数据变成有序序列 。 分治法的基本思想 分解(划分): 将原问题分解为若干个与原问题相似的子问题； 求解: 递归地求解子问题。若子问题的规模足够小，则直接求解 组合: 将每个子问题的解组合成原问题的解。 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-13

算法的实现步骤： 3 1 4 1 5 9 2 6 5 3 第6章 内部排序 6.3 快速排序（cont.） 设被排序的无序区为A[i],……,A[j] 1. 基准元素选取：选择其中的一个记录的关键字v 作为基准 元素(控制关键字);(怎么选择？) 2. 划分：通过基准元素v 把无序区A[i],……,A[j]划分成左、 右两部分，使得左边的各记录的关键字都小于v ；右边的 各记录的关键字都大于等于v ；(如何划分？) 3. 递归求解：重复(1)~(2)，分别对左边和右边部分递归地进 行快速排序； 4. 组合：左、右两部分均有序，整个序列有序。 3 1 4 1 5 9 2 6 5 3 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-14

基准元素的选取是任意的，但不同的选取方法对算法性能 影响很大； 一般原则：是每次都能将表划分为规模相等的两部分（最 第6章 内部排序 6.3 快速排序（cont.） 基准元素的选取： 3 1 4 1 5 9 2 6 5 3 基准元素的选取是任意的，但不同的选取方法对算法性能 影响很大； 一般原则：是每次都能将表划分为规模相等的两部分（最 佳情况）。此时，划分次数为log2n，全部比较次数nlog2n ，交换次数(n/6)log2n 。 设 FindPivot( i , j)是求A[i].key,…,A[j].key的基准元素 v=A[k]，返回其下标k 。 v =(A[i].key，A[(i+j)/2].key, A[j].key的中值 ) v =从A[i].key到A[j].key 最先找到的两个不同关键字中 的最大者。（若A[i].key,…A[j].key之中至少有两个关 字不相同）优点：若无两个关键字不同，则A[i]到A[j] 已有序，排序结束。 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-15

int FindPivot( int i, int j ) /* 设A是外部数组 */ 第6章 内部排序 6.3 快速排序（cont.） int FindPivot( int i, int j ) /* 设A是外部数组 */ /*若A[i],…A[j]的关键字全部相同，则返回0； 否则，左边两个不同关键字中的较大者的下标。*/ { keytype firstkey = A[i].key ; /* 第1个关键字的值A[i].key */ /* 从左到右查找不同的关键字 */ int k ; for ( k=i+1 ; k<=j; k++ ) /* 扫描不同的关键字 */ if ( A[k].key > firstkey ) /* 选择较大的关键字 */ return k ; else if ( A[k].key < firstkey ) return i ; return 0 ; 3 1 4 1 5 9 2 6 5 3 } 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-16

(2) 测试l 和 r：若l < r，则转(3)；否则(l > r, 即 l= r +1)转(4) 第6章 内部排序 6.3 快速排序（cont.） 无序区划分（分割）： 设被排序的无序区为A[i],……,A[j] (1) 扫描: 3 1 4 1 5 9 2 6 5 3 令游标 l 从左端(初始时l = i )开始向右扫描，越过关键 字小于v 的所有记录，直到遇到A[l].key≥v； 又令游标 r 从右端(初始时 r = j )开始向左扫描，越过关 键字大于等于v 的所有记录，直到遇到A[r].key<v； (2) 测试l 和 r：若l < r，则转(3)；否则(l > r, 即 l= r +1)转(4) (3) 交换：交换A[l ]和A[r]，转( 1 )；(目的是使 l 和 r 都至少 向其前进方向前进一步) (4)此时A[i],…A[j]被划分成为满足条件的两部分A[i],…A[l -1] 和A[l ],…,A[j]。 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-17

int Partition ( int i , int j , keytype pivot ) 第6章 内部排序 6.3 快速排序（cont.） int Partition ( int i , int j , keytype pivot ) /*划分A[i],…,A[j]，是关键字 < pivot 的在左子序列， 关键字≥pivot 的在右子序列，返回有子序列的起始下标*/ { int l , r ; do{ for( l = i ; A[l].key < pivot ; l++ ) ； for( r = j ; A[l].key >= pivot ; r--) ； if( l < r ) swap(A[l],A[r]); } while( l <= r ); return l ; } 3 1 4 1 5 9 2 6 5 3 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-18

快速排序的实现：/*对外部数组A 的元素A[i],…,A[j]进行快速排序*/ 第6章 内部排序 6.3 快速排序（cont.） 快速排序的实现：/*对外部数组A 的元素A[i],…,A[j]进行快速排序*/ void QuickSort ( int i , int j ) { keytype pivot; int k; //关键字大于等于pivot的记录在序列中的起始下标 int pivotindex ; //关键字为pivot的记录在数组A中的下标 pivotindex = FindPivot ( i , j ); if( pivotindex != 0 ) { //递归终止条件 pivot=A[pivotindex].key; k=Partition ( i , j , pivot ); QuickSort ( i , k-1); QuickSort ( k , j ); } } //对数组A[1],…,A[n]进行快速排序可调用QuickSort(1,n)实现 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-19

第6章 内部排序 6.3 快速排序（cont.） 示例 v =3 3 1 4 1 5 9 2 6 5 3 v =2 v =5 2 1 1 4 5 9 3 6 5 3 v =4 v =9 1 1 2 4 3 3 9 6 5 5 v =6 3 3 4 5 6 5 9 5 5 6 1 1 2 3 3 4 5 5 6 9 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-20

快速排序（时间）性能分析 第6章 内部排序 6.3 快速排序（cont.） 最好情况： 每一次划分后，划分点的左侧子表与右侧子表的长度 同，则有，为O(nlog2n)。 T(n)≤2T(n/2)＋n ≤2(2T(n/4)＋n/2)＋n＝4T(n/4)＋2n ≤4(2T(n/8)＋n/4)＋2n＝8T(n/8)＋3n ……… ≤nT(1)＋nlog2n＝O(nlog2n) 时间复杂度为O(nlog2n) 空间复杂度为O(log2n) 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-21

  （ 1 n i ） 快速排序（时间）性能分析 1 n(n 1)  O(n2) 2 时间复杂度为O(n2) 第6章 内部排序 6.3 快速排序（cont.） 快速排序（时间）性能分析 最坏情况： 每次划分只得到一个比上一次划分少一个记录的子序 （另一个子序列长度为1），则有 n1 i   （ 1 n i ） 1 n(n 1)  O(n2) 2 时间复杂度为O(n2) 空间复杂度为O(n) 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-22

快速排序（时间）性能分析 如下: 38 13 50 27 49 55 时间复杂度为O(nlog2n) 空间复杂度为O(log2n) 65 第6章 内部排序 6.3 快速排序（cont.） 快速排序（时间）性能分析 平均情况： 快速排序的递归执行过程可以用递归树描述。 例如，序列 {38, 27, 55, 50, 13, 49, 65}的快速排序递归 如下: 38 13 50 27 49 55 时间复杂度为O(nlog2n) 空间复杂度为O(log2n) 65 2012-1-4 哈工大计算机科学与技术学院 张岩 Slide 6-23