DS13_排序a_陈越主编_数据结构

1、1第7章 排序7.1 引子排序排序是很常见的一类问题（是很常见的一类问题（并不局限于排序本身）并不局限于排序本身）例例7.1 有有1亿个亿个随机给出的浮点数，请找出其中随机给出的浮点数，请找出其中最大的最大的1万个万个。方法方法1：简单选择法简单选择法 总比较次数为总比较次数为N-1+(N-2)+(N-10000)次。当次。当N为为1亿时，大约为亿时，大约为1万亿万亿次次。“分而治之分而治之”方法方法2： 比如，以比如，以1百万为一个块，分为百万为一个块，分为100块块，分别对这，分别对这100块数据进行排序。块数据进行排序。由于只需要得到最大的由于只需要得到最大的1万个数，故万个数，故每块每

2、块排完后可以排完后可以只要前只要前1万个数万个数，再，再从这从这100块共块共100万个数万个数中取最大的中取最大的1万个就可以了。万个就可以了。 当当N为为100万时，万时，O(NlogN)是是2000万万，所以求解，所以求解101块百万数据的排序块百万数据的排序问题，时间大约是问题，时间大约是20亿亿次运算次运算。堆选择堆选择方法方法3： 先读出先读出1百万个数，建立百万个数，建立初始堆初始堆（100万运算量），对剩下的万运算量），对剩下的近近1亿亿个个数进行数进行过滤过滤：每次读入剩下的一个数，如果该数小于等于这：每次读入剩下的一个数，如果该数小于等于这1万个数的万个数的最小值最小值，则

3、继续读下一个数；否则，用该数，则继续读下一个数；否则，用该数替代替代1万个数里的最小值万个数里的最小值。 100万（万（1百万建堆）百万建堆）+ 1亿（顺序过滤）亿（顺序过滤）+ 14 * 1千万，共约千万，共约2.4亿。亿。（1万亿）万亿）（20亿）亿）（2.4亿）亿）N=1亿，亿，log10000=14过滤所有数据需要过滤所有数据需要 14亿？亿？No!随机数将使得绝大多数随机数将使得绝大多数很快被排除！比如只有很快被排除！比如只有大约大约1/10需要替换。需要替换。第7章 排序7.2 选择排序简单选择排序简单选择排序 时间复杂性时间复杂性 T(n) = O（n2） 空空 间复杂性间复杂性

4、S(n) = O（1） 稳定性：稳定性：不稳定。不稳定。反例如下：反例如下：2 2 11 2 2不稳定！不稳定！排序前排序前2 领先于领先于 22 落后于落后于 2排序后排序后 堆排序的核心思想是：利用堆排序的核心思想是：利用最大堆最大堆（或者最小堆）（或者最小堆）输出堆顶元输出堆顶元素素，即最大值（或最小值），将剩余元素，即最大值（或最小值），将剩余元素重新生成最大堆重新生成最大堆（或者（或者最小堆），继续输出堆顶元素，最小堆），继续输出堆顶元素，重复此过程重复此过程，直到全部元素都已，直到全部元素都已输出，得到的输出元素序列即为有序序列。输出，得到的输出元素序列即为有序序列。堆排序（属于堆

5、排序（属于选择排序选择排序大类）大类）对初始已经有序的序列对初始已经有序的序列没有实质性的省时间优势没有实质性的省时间优势。996645371033221399136645371033229966374513103322第7章 排序7.2 堆排序例例花了花了logN的时间搞定了最大元的时间搞定了最大元素。以后类似素。以后类似可以搞定第二大、可以搞定第二大、第三大第三大元素。元素。一次性花一次性花O(N)的时的时间建立成间建立成最大堆最大堆。从根往从根往较大孩子方较大孩子方向渗透向渗透到合适位置。到合适位置。void Adjust( ElementType A, int i, int N ) /

6、* 对对A中的前中的前N个元素从第个元素从第i个元素开始向下迁移调整个元素开始向下迁移调整 */int Child;ElementType temp;for( temp = Ai; (2*i + 1) AChild)Child+; /* Child指向左右子结点的较大者指向左右子结点的较大者 */if( temp = 0; i- ) /*从有儿子的最后一个结点开始从有儿子的最后一个结点开始*/ Adjust(A, i, N); /* 建立最大堆建立最大堆*/for( i = N-1; i 0; i- ) /* 将堆顶元素将堆顶元素A0与当前堆的最后一个元素与当前堆的最后一个元素Ai换位换位 *

7、/ temp = A0; A0 = Ai; Ai = temp; /* 将有将有i个元素的新堆从根结点向下过滤调整个元素的新堆从根结点向下过滤调整 */ Adjust(A, 0, i);与与DeleteMax( MaxHeap H )类似类似。第7章 排序7.2 堆排序第7章 排序7.2 选择排序 时间复杂性时间复杂性 T(n) = O（nlogn） 空空 间复杂性间复杂性S(n) = O（1） 稳定性：稳定性：不稳定。不稳定。反例如下：反例如下：不稳定！不稳定！排序前排序前2 领先于领先于 22 落后于落后于 2排序后排序后 堆排序（属于堆排序（属于选择排序选择排序大类）大类） 2 1 2

8、1 2 2 211223211223121223 最坏情形最坏情形:输入的输入的A 是逆序是逆序. T( N ) = O( N2 ) 最好情形最好情形:输入的输入的A 已经有序已经有序. T( N ) = O( N )第7章 排序7.3 插入排序简单插入排序简单插入排序void InsertionSort ( ElementType A , int N ) /* 插入排序插入排序 */ int i, j ; ElementType temp; for ( i = 1; i 0) & (temp Aj1); j- ) A j = A j 1 ; /*依次与已排序序列中元素比较并右移依次与

9、已排序序列中元素比较并右移*/ Aj = temp; /* 放进合适的位置放进合适的位置 */ 空空 间复杂性间复杂性S(n) = O（1） 稳定性：稳定性：稳定。稳定。例例: 81941196123517952858417515962812588135419417751195155-sort964194112858357595128117153-sort1-sort96419411285835759512811715 定义一个递增序列定义一个递增序列： h1 h2 ht ( h1 = 1 ) 分步骤进行分步骤进行 “间隔间隔hk-插入排序插入排序”，k = t, t 1, , 1第7章 排序

10、7.3 插入排序 希尔排序希尔排序by Donald Shell注意注意: “间隔间隔hk-插入排序插入排序” 的结果留给的结果留给“间隔间隔hk-1-插入排序插入排序”第7章 排序7.3 希尔排序void ShellSort( ElementType A , int N, int Incre , int M ) /* 希尔排序希尔排序*/ /* 其中其中Incre为包含为包含M个增量的序列，递减有序，且最后一个元素为个增量的序列，递减有序，且最后一个元素为1 */int i, j, k, Increment;ElementType temp;for ( i = ; iM; i+ ) Incr

11、ement = Incre i ;/* 选择该趟排序需要选择该趟排序需要的增量的增量 */ for ( j = Increment; j = 0; k -= Increment ) if ( temp = A k - Increment ) break; else A k = A k - Increment ; Ak = temp; /* 结束一趟插入排序结束一趟插入排序 */第7章 排序7.3 插入排序希尔排序希尔排序 空空 间复杂性间复杂性S(n) = O（1） 稳定性：稳定性：不稳定。不稳定。对初始基本有序的序列对初始基本有序的序列可以提高时间性能。可以提高时间性能。希尔排序算法的整体时

12、间复杂度希尔排序算法的整体时间复杂度和增量序列的选取有关和增量序列的选取有关，目前并，目前并没有统一的最优增量序列。没有统一的最优增量序列。 当使用增量序列当使用增量序列 N/2 , N/22 , , 1 进行希尔排序时，有例进行希尔排序时，有例子表明，最差情况下的时间复杂度子表明，最差情况下的时间复杂度 Tworst(n) = O(N2)； 而当使用而当使用增量序列增量序列 2k-1, 7, 3,1 时，最差情况下时间复杂度时，最差情况下时间复杂度为为Tworst(n) = O(N3/2)，平均时间复杂度为，平均时间复杂度为Taverage(n) = O(N5/4)。441259366243

13、 j i j j第7章 排序7.4 交换排序冒泡排序冒泡排序012345124436594362 j i j123644435962 j i j123643445962 j i 无交换发生，可以提前结束？无交换发生，可以提前结束？ 时间复杂性时间复杂性 T(n) = O（n2） 空空间复杂性间复杂性S(n) = O（1） 稳定性：稳定性：稳定。稳定。void BubbleSort ( ElementType A , int N ) /*冒泡排序冒泡排序*/ int i, j ; bool flag; ElementType temp; for ( i = N - 1; i = 0; i-) f

14、lag = 0 ; /*标记该次循环中是否发生交换，若无，则说明整个序列有序标记该次循环中是否发生交换，若无，则说明整个序列有序*/for ( j = 0; j A j + 1 ) temp = A j ; A j = A j + 1 ; A j + 1 = temp ;flag = 1 ;/*若发生交换，则标记若发生交换，则标记*/ if ( !flag ) break ; /*若没有发生交换，则跳出循环若没有发生交换，则跳出循环*/ 若不考虑提前结束，若不考虑提前结束，可以忽略可以忽略flag。第7章 排序7.4 交换排序SN个元素S1N1个元素S2N2个元素元素元素 = e元素元素 =

15、e元素元素 = ee元素元素 jiijiiji= High ) return; Swap ( &ALow, &ARight ) ; /*将基准与最后一个元素交换将基准与最后一个元素交换*/ while (1) /*将序列中比基准小的移到基准左边，大的移到右边将序列中比基准小的移到基准左边，大的移到右边*/while ( (Low = ALow) ) Low+ ;while ( (Low Hight) & (Pivot = AHigh) ) High- ; if ( Low High ) Swap ( &ALow, &AHigh ) ;else break; Swap ( &ALow, &ARigh