《数据结构》课件第10章 内部排序

1、第10章 内部排序学习要点: 深刻理解排序的定义和各种排序方法的特点了解各种方法的排序过程及其依据的原则掌握各种排序方法的时间复杂度的分析方法理解排序方法“稳定”或“不稳定”的含义重点掌握希尔排序、快速排序、堆排序和归并排序等高效方法10.1 概述什么是排序？将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列。52, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为：14, 23, 36, 49, 52, 58, 61 ,75, 80, 97一般情况下，假设含n个记录的序列为 R1, R2, ，Rn 其相应的关键字序列为 K1, K2, ，Kn

2、。这些关键字之间存在着关系：Kp1Kp2Kpn，按此固定关系将上面记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。其中，关键字Ki是主关键字时，排序结果唯一；否则，不唯一。假设Ki=Kj(1in, 1jn, ij)，且在排序前的序列中Ri领先于Rj(即ij)。若排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中Rj领先于Ri，则称所用的排序方法是不稳定的。内部排序和外部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无 序 序 列 区有序序

3、列区无 序 序 列 区基于不同的“扩大” 有序序列长度的方法，内部排序方法大致可分下列几种类型：插入交换选择归并其它方法排序中的基本操作：比较关键字大小移动记录若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。(第11章)必须的！可通过改变记录的存储方式来避免！存放在地址连续的一组存储单元上；存放在静态链表中，记录之间的次序关系由指针指示；记录本身存储在一组地址连续的存储单元内，同时另设一个指示各个记录存储位置的地址向量。待排序的记录若以顺序存储，其结构如下：#define MAXNUM100 /顺序表的最大长度typedef int KeyType;

4、 /关键字类型为整型typedef structKeyTypekey; /关键字项DataTypeInfo; /其他数据项RedType; /记录类型typedef struct RedType r MAXNUM+1; /r0做其他用 intlength; / 记录个数, 即顺序表长度SqList; /顺序表类型一趟直接插入排序的基本思想：10.2 插入排序有序序列R1.i-1Ri无序序列 Ri.n有序序列R1.i无序序列 Ri+1.n实现“一趟插入排序”可分三步进行：在有序序列R1.i-1中查找Ri的插入位置， R1.j.key Ri.key Rj+1.i-1.key；将Rj+1.i-1中的

5、所有记录均后移一个位置；将Ri 插入(复制)到Rj+1的位置上。不同的“查找”方法导致不同的算法描述：直接插入排序(基于顺序查找)折半插入排序(基于折半查找)表插入排序(基于链表存储)希尔排序(基于逐趟缩小增量)10.2.1 直接插入排序利用“顺序查找”实现“在R1.i-1中查找Ri的插入位置”。算法的实现要点：从Ri-1起向前进行顺序查找，监视哨设置在R0R0 = Ri; / 设置“哨兵”循环结束表明Ri的插入位置为 j +1R0jRifor (j=i-1; R0.keyRj.key; -j); / 从后往前找j=i-1插入位置对于在查找过程中找到的那些关键字Ri.key的记录, 在查找的同

6、时实现记录向后移动；上述循环结束后可以直接进行“插入”。令 i = 2，3，, n, 实现整个序列的排序。for ( i=2; i=n; +i ) if (Ri.keyRi-1.key) 在 R1.i-1中查找Ri的插入位置; 插入Ri ; for (j=i-1; R0.keyRj.key; -j); Rj+1 = Rj;R0jRij= i-1插入位置算法实现：void InsertionSort ( SqList &L ) / 对顺序表 L 作直接插入排序。 for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) L.r0 = L.ri; /

7、 待排序记录复制为监视哨 for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 记录后移 L.rj+1 = L.r0; / 插入到正确位置 / InsertSort例如：n个元素需进行n-1趟排序。49 38 65 97 76 13 27 49i=2 38 (38 49) 65 97 76 13 27 49i=3 65 (38 49 65) 97 76 13 27 49i=4 38 (38 49 65 97) 76 13 27 49i=5 76 (38 49 65 76 97) 13 27 49i=6 13 (13 38 49 65 76

8、 97) 27 49i=1 ( )i=7 (13 38 49 65 76 97) 27 4927jjjjjj97)7665493827 (13 27 38 49 49 65 76 97)排序结果：0 1 2 3 4 5 6 7 8i=8 (13 27 38 49 65 76 97) 494938算法时间性能分析： 直接插入排序算法由两重循环组成，对于有n个记录的排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。最好情况: 关键字在排序前已递增有序。“比较”的次数：“移动”的次数：最坏情况: 关键字在排序前为递减有序。“比较”的次数：“移动”的次数：直接插入排序是一种稳定的排

9、序方法。010.2.2 折半插入排序因为 R1.i-1 是一个按关键字有序的有序序列，则可以利用折半查找实现“在R1.i-1中查找Ri的插入位置”，如此实现的插入排序为折半插入排序。算法描述：void BiInsertionSort ( SqList &L ) for ( i=2; i=high+1; -j ) /一趟排序 L.rj+1 = L.rj; / 记录后移 L.rhigh+1 = L.r0; / 插入 / for / BInsertSort/折半查找low = 1; high = i-1;while (low=high) m = (low+high)/2; / 折半 if (L.r0

10、.key L.rm.key) high = m-1; / 插入点在低半区 else low = m+1; / 插入点在高半区性能分析：空间效率：同上O(1)时间效率：仅减少了比较次数，移动记录次数不变。例如：再如：14 36 49 52 8058 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow插入位置插入位置L.rL.r1 2 3 4 5 6 7 8 9 1010.2.3 表插入排序利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整

11、到它们所应该在的位置上。算法描述：void LInsertionSort (Elem SL ， int n) / 对记录序列SL1.n作表插入排序 SL0.key = MAXINT ; SL0.next = 1; SL1.next = 0; /构造循环链表 for ( i=2; i=n; +i ) for ( j=0, k = SL0.next;SLk.key=SLi.key ; j=k, k=SLk.next ) SLj.next = i; SLi.next = k; / 结点i插在结点j和结点k之间/ LinsertionSort修改指针项的值按照非递减顺序重排记录如何在排序之后调整记录序

12、列？重排算法中使用三个指针：p：指示第i个记录的当前位置i：指示第i个记录应在的位置q：指示第i+1个记录的当前位置算法描述：void Arrange ( Elem SL , int n ) p = SL0.next; / p指示第一个记录的当前位置 for ( i=1; in; +i ) while (pi) p = SLp.next; q = SLp.next; / q指示尚未调整的表尾 if ( p!= i ) SLpSLi; / 交换记录，使第i个记录到位 SLi.next = p; / 指向被移走的记录 p = q; / p指示尚未调整的表尾，为找第i+1个记录作准备 / Arran

13、ge10.2.4 希尔排序1959年由D.L. Shell提出，又称缩小增量排序(Diminishing-increment sort) 。基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是“跳跃式”的插入排序。具体做法：将记录序列分成若干子序列，分别对每个子序列进行插入排序。例如：将 n 个记录分成 d 个子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 其中，d 称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。例如：16 25 12 30 47 1

14、1 23 36 9 18 31 第一趟希尔排序，设增量 d =511 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 1 2 3 4 5 6 7 8 9 10 11算法描述：void ShellInsert ( SqList &L, int dk ) /对增量为dk的子序列进行 /直接插入排序 for ( i=dk+1; i=n; +i ) if ( L.ri.key0&(L.r0.key

15、L.rj.key); j-=dk) L.rj+dk = L.rj; / 记录后移，查找插入位置 L.rj+dk = L.r0; / 插入 / if / ShellInsertvoid ShellSort (SqList &L, int dlta, int t) / 增量为dlta的希尔排序 for (k=0; k1) / while / BubbleSorti = n; / i 指示无序序列中最后一个记录的位置i = lastExchangeIndex; / 本趟进行过交换的最后一个记录的位置 if (Rj+1.key Rj.key) Swap(Rj, Rj+1); lastExchangeI

16、ndex = j; /记下进行交换的记录位置 /iffor (j = 1; j i; j+)lastExchangeIndex = 1;注意：起泡排序的结束条件为，最后一趟没有进行记录“交换”；一般情况下，每经过一趟“起泡”，“i 减1”，但并不是每趟都如此。例如：2553157989i=7i=6for (j = 1; j i; j+) if (Rj+1.key Rj.key) 13i=2即i=lastExchangeIndex=1时间性能分析：最好的情况(关键字在记录序列中顺序有序)：只需进行一趟起泡。“比较”的次数：“移动”的次数：最坏的情况(关键字在记录序列中逆序有序)：需进行n-1趟起

17、泡。“比较”的次数：“移动”的次数： (每次移动记录3次)起泡排序方法是稳定的。n-10时间复杂度：O(n2)10.3.2 快速排序一趟快速排序(一次划分)：目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后致使一趟排序之后，记录的无序序列Rs.t将分割成两部分：Rs.i-1和Ri+1.t， 且 Rj.key Ri.key Rj.key (sji-1) 枢轴 (i+1jt)。例如：设 Rs=52 为枢轴将 Rhigh.key和枢轴的关键字进行比较，要求Rhigh.key 枢轴的关键字；将 Rlow.key和枢轴

18、的关键字进行比较，要求Rlow.key 枢轴的关键字。stlowhighhigh23low80high14low52R052lowhighhighhighlow可见，经过“一次划分” ，将关键字序列 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，并保证 Rhigh.key52 和 Rlow.key52否则进行记录的“交换”。一趟快速排序算法描述：int Par

19、tition ( SqList &L，int low, int high ) L.r0 = L.rlow; pivotkey = L.rlow.key; / 枢轴 while ( low high ) while ( low = pivotkey ) -high; / 从右向左搜索 L.rlow = L.rhigh; while ( low high & L.rhigh.key = pivotkey ) +low; / 从左向右搜索 L.rhigh = L.rlow; L.rlow = L.r0; return low; / 返回枢轴所在位置 / Partition快速排序： 首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无 序 的 记 录 序 列无序子序列(1)无序子序列(2)枢轴一次划分分别进行快速排序算法描述：void QSort (RedType & R, int s, int t) / 对记录序列Rs.t进行快速排序 if (s t-1) / 长度大于1 pivotloc = Pa