数据结构-清华大学-殷人昆.docx

《数据结构-清华大学-殷人昆.docx》由会员分享，可在线阅读，更多相关《数据结构-清华大学-殷人昆.docx（184页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章排序从来处来往去处去次序之美美在规矩利在行方概述插入排序 交换排序 选择排序 归并排序 表排序 基数排序各种内排序方法的比较 外排序概述 排序：将一组杂乱无章的数据按一定的规律顺次 排列起来。 数据表(datalist):它是待排序数据记录的有限集 合。 排序码(key):通常数据记录有多个属性域，即多 个数据成员组成，其中有一个属性域可用来区分 记录，作为排序依据。该域即为排序码。口每个数据表用哪个属性域作为排序码，要视具 体的应用需要而定。本章所涉及排序码的值允许重复。排序算法的稳定性：如果在记录序列中有两个记 录ri和5,它们的排序码值kij = kj,且在排序 之前，记录门“排在

2、rj前面。如果在排序之后，记 录邙仍在记录的前面，则称这个排序方法是 稳定的,否则称这个排序方法是不稳定的。内排序与外排序内排序是指在排序期间数据记录全部存放在内 存的排序；外排序是指在排序期间全部记录个数太多，不 能同时存放在内存，必须根据排序过程的要求, 不断在内、外存之间移动的排序。排序的时间开销：排序的时间开销是衡量算法好 坏的最重要的标志。内排序的时间开销可用算法 执行中的排序码比较次数与数据移动次数来衡量; 外排序的时间开销要看读写外存的次数。-算法运行时间代价的大略估算一般都按平均情况 进行估算。对于那些受记录排序码序列初始排列 及记录个数影响较大的，需要按最好情况和最坏 情况分

3、别进行估算。-算法执行时所需的附加存储：评价算法好坏的另 一标准。从排序过程中数据的总体变化趋势来看，排序方 法的处理可以分为两大类。(1)有序区增长：将数据表分成有序区和无序区，在 排序过程中逐步扩大有序区，缩短无序区，直到 有序区扩大到整个数据表为止。如插入排序、选 择排序、起泡排序、堆排序、归并排序等。(2)有序程度增长：数据表不能明确区分有序区和无 序区，随着排序过程的执行，逐步调整表中元素 的排列，使得表中的有序程度不断提高，直到完 全有序。如快速排序、希尔排序、基数排序等。待排序数据表的结构定义const int DefaultSize = 100; typedef int Dat

4、aType;typedef struct Element DataType key; otherdata;表元素定义排序码其他数据成员）；typedef struct dataList 数据表定义Element elemDefaultSize; 存宿羲组int n;前元素个数插入排序(Insert Sorting)基本方法是：每步将一个待排序的记录，按其排序码值的大小，插入到前面已经排好序的一组记录的适当位置上,直到记录全部插入为止。直接插入排序(Insert Sort)直接插入排序的基本思想是：当插入第个记录时,前面的elem0h,elemi-l已经排好序。这时，用的排序码与的排序码顺序比较

5、，找到插入位置即将插入,原来位置上的记录向后顺移。”101234567t 25 21 ,无需移动t4925,无需移动t 37 5252, 49后移直接插入排序的算法void InsertSort ( dataList& L ) Element w； inti;for (i = 1; i L.n; i+ )插入n-1 趟if ( L.elemi.key O;j)从后向前比较if ( w.key L.elemj-l.key ) 比j-l元素小L.elemj = L.elemj-1; 让j-1 元素后移 else break;L.elemj = w;法分析 设待排序记录个数为，则该算法的主程序执行

6、趟。排序码比较次数和记录移动次数与记录 排序码的初始排列有关。 最好情况下，排序前记录已按排序码的值从小到 大有序，每趟只需与前面有序记录序列的最后一 个记录比较1次，移动0次记录，总的排序码比 较次数为-1,记录移动次数为Oo 最坏情况下，第i趟时第，个记录必须与前面i 个记录都做排序码比较，并且每做1次比较就要 做1次数据移动。 因此，在最坏情况下，总排序码比较次数KCN和 记录移动次数RMN分别为n-lKCN = i =双11 - D。- n2/29i=lRMN = (i + 2) = (n + 4)(n -1)/2。n2/2 在平均情况的排序码比较次数和记录移动次数 约为4/4。因此，

7、直接插入排序的时间复杂度为 O(n2)o 直接插入排序是一种稳定的排序方法。 直接插入排序需要一个附加记录暂存待插记录。折半插入排序(Binary Insertsort)-折半插入排序的基本思想是：设在顺序表中有一 个记录序列 elem09 eleml,elemw-lo 其中, elem05 eleml,elemi-l是已经排序的数据 记录。在插入时，不是利用顺序查找从后 向前寻找插入位置，而是利用折半查找法寻找elemf的插入位置。折半插入排序的算法void BinaryInsSort ( dataList& L ) Element w; int i, k, left, right, mid

8、; for (i = 1; i L.n; i+ ) 159-15left = 0; right = i-1; w = L.elemi;while (left = right) 在内寻找elemi插入位置mid = (left+right )/2;中间位置if ( w.key = left; k-)L.elemk+1 = L.elemk;空出 left 位置L.elemleft = w; / for算法分析- 折半搜索比顺序搜索查找快，所以折半插入排序 就平均性能来说比直接插入排序要快。- 它所需的排序码比较次数与待排序记录序列的初 始排列无关,仅依赖于记录个数。- 在插入第，个记录时，需要经过

9、|_1吗，+1次排序码比较，才能确定它应插入的位置。- 因此，将个记录元素（为推导方便，设为 =2匕 k = log2n ）,折半插入排序所进行的排序码比较 次数为：n-1*1峭+1)=!+2+土+3 h卜k+k 1 1 K i=l221222k-1= 1*2。+2+3*22+ + k*2i= (k-l)* 2k +1 = n(log2n-l) + l = nlog2n-n + l 这是折半查找算法分析得到的结果。折半查找的 时间复杂度为O(nk)g2n)，这是指排序码比较次数 的时间开销，但记录移动次数就不同了。 折半插入排序的记录移动次数比直接插入排序多 一点，依赖于记录元素的初始排列。

10、折半插入排序是一个稳定的排序方法。 折半插入排序需要一个附加记录暂存待插记录。希尔排序(Shell Sort).希尔排序方法又称为缩小增量排序。.该方法的基本思想是：设待排序记录序列有n个记 录，首先取一个整数gap vn作为间隔，将全部记录 分为gap个子序列，所有距离为gap的记录放在同 一个子序列中，在每一个子序列中分别施行直接插 入排序。然后缩小间隔gap,例如取gap = gap/2，重复上 述的子序列划分和排序工作。直到最后取gap = 1, 将所有记录放在同一个序列中排序为止。16V21.21 后移08 49.无需移动37 25.无需移动01234567i = 2 gap=249

11、 1621 49无需移动 49后移无需移动25* 0825 = 2537 25无需移动无需移动无需移动结果i = 3 gap=l国同闻同012316 0816后移国园国国国国阂国456725 4937 5249后移 52, 49后移国同同阂开始时gap的值较大，子序列中的记录较少，排 序速度较快；随着排序进展，gap值逐渐变小， 子序列中记录个数逐渐变多，由于前面工作的基 础，大多数记录已基本有序，所以排序速度仍然 很快。希尔排序的算法void ShellSort ( dataList& L ) Elementw； gap = L.n / 2;while ( gap != 0 ) 宿环，直到g

12、ap为零for (i = gap; i = gap; j = j-gap )if ( w.key elemj,则 交换elemj-l和elemj。01234567同国国国国同阈同Exchang=lExchang=lExchang=lExchang=lExchange起泡排序的算法void BubbleS ort ( dataList& L ) int i = 1, j; int exchange = 1;while (i = i; j )if (L.elemj-l.key L.elemj.key ) 逆序Swap (L.elemj-1, L.elemj);/交装exchange = 1; 标志

13、置为1,有交换)i+；算法分析 第i趟对待排序记录序列进行排序，结果将该序列中排序码最小 的记录交换到序列的第一个位置其他记录 也都向排序的最终位置移动。在个别情形，记录可 能在排序中途向相反的方向移动。 最多做趟起泡就能把所有记录排好序。 起泡排序的时间代价受记录的初始排列影响。在 记录的初始排列已经按排序码的值从小到大排好 序时，此算法只执行一趟起泡，做次排序码 比较，不移动记录。这是最好的情形。 最坏情形是算法执行趟起泡，第，趟(iwiv) 做次排序码比较，执行次记录交换。像所 有记录在一开始就已经按其排序码值逆序即为这 种情况。因此，在最坏情形下总的排序码比较次 数KCN和记录移动次数

14、RMN为：KCN = 2(n-i) = -n(n-l)i=l2RMN = 32L(n-i) = -n(n-l) 起泡排序是一本居定的排序方法。 起泡排序需要一个附加记录作为交换记录使用。快速排序（Quick Sort）.快速排序又称分区排序，其基本思路是：任取待 排序记录序列中的某个记录（例如取第一个记录） 作为基准，按照该记录的排序码值的大小，将整 个记录序列划分为左右两个子序列：左侧子序列中所有记录的排序码值都小于或等 于基准记录的排序码值；右侧子序列中所有记录的排序码值都大于基准 记录的排序码值。 基准记录则排在这两个子序列中间（这也是该记录 最终应安放的位置）。然后分别对这两个子序列重

15、复施行上述方法, 到所有的记录都排在相应位置上为止。下图是对一组排序码的一趟划分的例子。逆向正向012345it-16 21 J j快速排序一趟划分的算法int Partiton 1 ( dataList& L, int i, int j) Element w = L.elemi;while (i j ) while (i = w.key ) j一一;if (i j) L.elemi = L.elemfj; i+;逆向，小于基准者左移while (i j & L.elemi.key = w.key ) i+;) L.elemj = L.elemi; j ;正向，大于基准者右移)L.elemi

16、= w;/基准记录就位return i;返回基准位置,即排序区间划分点快速排序的递归算法void Quicksort ( dataList& L, int left, int right) if (left =w,让j-，重复这一步，直到遇到 Lj vw的记录容止；(2)若Liv=w,让i+,重复这一步，直到遇到 Li w的记录停止；(3)若 ivj,则交换 Li与 Lj,且令 i+, j, 然后继续重复以上(1), (2), (3)步，向中间靠拢，直到i = j为止。交换Lj与Lleft后，基准排在 位置j,此即划分点，它左边子区间记录的排序 码都比它的排序码小，右边子区间记录的排序码 都比

17、它的排序码大。 此算法比前一个划分算法整齐，算法时间复杂度 都是O(n),但由于它每一次交换需要3次数据传 递，比前一个算法需要数据传送的次数多。而前 一个划分算法的数据传送次数已经达到了最少。 下面是一个使用此算法进行划分的示例。同同国同同国同囱01234567- ii j 425 2108 2125, 08交换01234567i ii j 21162149,16交换iiij 一i=j与基准对换01234567int Partition2 ( DataList& L, int left, int right) if (left right) int i = left+1, j = right

18、;do while (i = j &反向检测L.elemlow.key = L.elemj.key ) j-;while (i j &正向检测L.elemi.key = L.elemlow.key ) i+; if(ij) Swap (L, i,j); i+; j-; while (i j);交换if (j != low ) Swap ( L, low, j); 交换 /* end of if (left f2125 2116,16继续继续继续与25交换4 1，3 F2108, 08与49交换2K52 2K37继续 继续34567012ik基准21与最后交换到前面 的比21小的元素08交换国园

19、固国国国同时01234567k-一趟划分的算法如下所示。这三种划分算法的时 间复杂度都是O(n),随序列不同，差别不大。int Partitions ( dataList& L, int low, int high ) int i, k = low;for (i =low+1; i = high; i+ )if ( L.elemi.key L.elemlow.key ) k+;if(k!=i)Swap(L, i,k);)交换小于基准的元素到左边去if ( k != low ) Swap ( L, low, k);基准就位return k;)；返回基准元素位置4, 7, 5, 6,3,1,2Pa

20、rtitionlPartitionlPartitions比较次数101111移动次数142124递归深度2334, 7, 5, 6, 2, 3,1PartitionlPartitionlPartitions比较次数111012移动次数161818递归深度3234, 6, 5, 7, 3,1,2PartitionlPartitionlPartitions比较次数11910移动次数172118递归深度322算法分析 算法quicksort是一个递归的算法，其递归树如图所 不。 这是快速排序算法一次次调用partition算法得到 的结果。 快速排序执行排序的趟数取决于递归树的高度。 如果每次划分能

21、将序列划分为长度接近相等的子 序列，则下一步将是对两个长度减半的子序列进 行排序，这是最理想的情况。 在n个元素的序列中，对基准元素定位所需时间 为O(n)。若设T(n)是对n个元素的序列进行排序 所需的时间，而且每次对一个记录正确定位后， 正好把序列划分为长度相等的两个子序列，则T(n)cn + 2T(n/2)/ c 是一个常数cn + 2(cn/2 + 2T(n/4) = 2cn + 4T(n/4) k 最小者21 159-55 交换 “RI不交换同同同同同同阈同1 = 4ik 最小者25本交换1 = 5最小者37 iWk k交换49,37国同同同国同同国1 = 6最小者49 用左一山交换

22、49,52国同国固国同国阈i = l时选择最小记录的过程画园同国固团012345ik最初假定Lk (k = i)最小5女指示当 0 前序列中1234ik j 49 25, j+团连国国同国国国除 J I25* 25, j+词国同国国国16 16简单选择排序的算法void SelectSort ( dataList& L) int i,j,k;for (i = 0; i L.n-1; i+ ) k二i;选择具有最小排序码值的记录for (j = i+l; j L,n; j+)if (L.elemj.key L.elemk.key) k = j;当前具最小排序码值的记录if(k!=i) 对换到第i

23、个位置Swap ( L.elemi, L.elemk);算法分析 简单选择排序的排序码比较次数KCN与记录的 初始排列无关。设整个待排序记录序列有个记 录，则第，趟选择具有最小排序码记录所需的比 较次数总是次。总排序码比较次数为KCN = (n i l) = i-o2 记录的移动次数与序列的初始排列有关。当这组 记录初始时已经按其排序码值从小到大有序时， 记录的移动次数RMN = O,最坏情况是每趟都要 进行交换，总记录移动次数为RMN = 3(n-1)。 简单选择排序是一种不稳定的排序方法。 简单选择排序算法只用到一个附加存储用于数据 交换。堆排序(Heap Sort) 利用堆及其运算，可以

24、实现选择排序的思路。 堆排序分为两个步骤根据初始输入数据，利用堆的筛选算法 siftDown()形成初始堆；通过一系列的记录交换和重新调整堆进行排序。如果堆排序采用小根堆，所有记录在排序后将按 其排序码从大到小排列。所以改使用大根堆。21254925*1608初始排序码集合214908i = 2时的局部调整214908i = 1时的局部调整214908i = 0时的局部调整 形成大根堆大根堆的向下筛选算法void siftDown (dataList& H, int start, int m) int i = start; int j = 2*i+l;HElemType w = H.heapi

25、;while (j = m ) 藁后位置if (j m & H.heapj.key = H.heapj.key ) break;else H.heapi = H.heapj; i = j; j = 2*j+l; 大子女上移，向下继续调整)H.heapi = w;回放到合适位置将表转换成堆的算法for (int i = (H.n-2) / 2 ; i = 0; i-) siftDown( H, i, H.n-1 );基于初始堆进行堆排序 大根堆的存储结构采用完全二叉树的顺序存储， 实际上它的所有结点是保存在一维数组H.heap0 中的。对大根堆进行各种操作，实际上是对一维 数组的操作，因此，堆排

26、序的结果将存放在一维 数组中。 大根堆排序的过程可描述如下： 大根堆堆顶H.heapO保存具有最大排序码的记 录，将H.heapO与H.heapn-1对调，把具有 最大排序码的记录交换到最后；.对前面的11-1个记录，使用堆的向下筛选算法 siftDown(H, 0, n-2),重新建立大根堆，具有次大 排序码的记录又上浮到H.heap0H立置。其中n 是堆的当前大小。 对调 H.heap0和 H.heapn-2记录，调用 siftDown(H, 0, n-3),对前n-2个记录重新筛选形 成大根堆，如此反复执行，最后得到全部排 序好的记录序列。此算法即堆排序。49252125*1608初始大

27、根堆08 25 21 25女 16 4908252125*1649交换0号与5号记录, 5号记录就位2525*21081649从0号到4号重新 调整为大根堆16 25* 21 08 25 491625*21082549交换0号与4号记录, 4号记录就位25*1621082549从0号到3号重新 调整为大根堆08162125*254908 16 21 25* 25 49交换0号与3号记录, 3号记录就位21160825*2549从0号到2号重新 调整为大根堆08162125*254908 16 21 25* 25 49交换0号与2号记录, 2号记录就位16082125*254916 08 21

28、25* 25 49从0号到1号重新 调整为大根堆08162125*254908 16 21 25* 25 49交换0号与1号记录, 1号记录就位堆排序的算法void HeapSort ( maxHeap& H ) 对小根堆 H.heap0到 H.heapH.CurrentSize-l进行排序，使得表中各个记录按其排序码非递减有序。int i;for (i = (H.CurrentSize/2 -1; i = 0; i- )siftDown ( H, i, H.CurrentSize -1); 初始堆for (i = H.CurrentSize-1; i = 1; i- ) Swap ( H.h

29、eap0, H.heapi);/交换siftDown ( H, 0, i-1 );重建大根堆算法分析若设堆中有n个结点，且2h/WnV2h,则对应的 完全二叉树有h层。在第i层上的结点数(i = 1,2,h)。在第一个形成初始堆的for循环中 对每一个非叶结点调用了 一次堆的向下筛选算法 siftDown(),因此该循环所用的计算时间为：h-l2Z2”(h-i) i=l其中，i是层号，非叶结点最多有h-l层，第i层 最多有27个结点，第i层每个结点最多下移h-i 层。每个结点每次执行横/纵向2次比较。h-12 p i (h-i) = 2* i=lh1)*2 +(h2)*2+1*2卜2 =2*

30、(2R2+2r3+2。)+ (2h-3+2h-4+*+2) + + 2 h-l个=2* Qh“1) + (2h-2-l) + + (21-1)=2* (2h-x+2h-2+-+21+2)-2-(1+1+1) = 2*(2h-l)-l-(h-l)=2* 2h-l-h = 2*(n+l)-1-log2(n+l)l=2* n- Flog2(n+l)l当n = 255时，h =log2(n+l)1 = 8,形成初始堆得 到排序码最小记录需比较2*(255-8) = 494次。排序过程中，第i次重构堆时堆内有n-i个结点, 自顶向下筛选时,排序码比较2*Llog2(n-i)J次,n-1次重构堆的排序码比

31、较次数为nl2*ZUg2(ni)(2*log2(n1)+105(吁2)+ +10当1 i=l=2*log2(n-l)! -2*(n-l)log2(n-l)-1.5(n-l)=2*(l)*log2(nT)3*(n-1) 因此，堆排序的时间复杂性为O(nlog2ii)。 该算法的附加存储主要是在第二个for循环中用来 执行记录交换时所用的一个临时记录。因此该算法 的空间复杂性为0(1)。 堆排序是一个不稳定的排序方法。归并排序(Merge Sort)-归并排序采用典型的分而治之算法，描述如下：MergeSort (List) if (List的长度大于1)将序列List划分为等长的两个子序列Lef

32、tList 和Right List;MergeSort (LeftList); 对子序列递归排序MergeSort (RightList); 对子序列递归排序 将两个子序列LeftList和RightList归并为一个 序列List;两路归并(2-way merging) 归并，是将两个或两个以上的有序表合并成一个 新的有序表。 例如，原始序列L中有两个有序表L4Lm 和Lm+1L川。把它们归并成一个有序表，存 于另一序列L1的L1用L1川中。这种归并方法 称为两路归并(2-way merging)o 为了实现两路归并，需要设置3个指针：变量， 和j是表L用L.和LM+1L川的当前检测 指针。

33、女是表L1的存放指针。leftmid mid+1 rightL | 08 21 25 25*49 62 72 93 ”16 37 54leftrightLI | 08 16 21 25 25*37 49 54 62 72 93I k 当i和j都在两个表的表长内变化时，根据对应项 的排序码的大小，依次把排序码小的记录排放到 新表女所指位置中； 当，与j中有一个已经超出表长时，将另一个表中 的剩余部分照抄到新表中。两路归并算法void merge( dataList& L, dataList& L1, int left, int mid, int right) int i = left, j = mid+1, k = left;while (i = mid & j = right)两两比较if ( L.elemi.key = L.elemj.key ) Ll.elemk = L.elemi; i+; k+; else Ll.elemk = L.elemj; j+; k+;wh