清华大学：《实用数据结构》课程教学资源（PPT课件）第九章 排序技术

清华大学出版社 TSINGHUA UNIVERSITY PRESS 第9章排序技术 9.1互换类排序 9.2插入类排序 9.3选择类排序 9.4拓扑分类 9.5其他排序方法简介

第9章 排序技术 9.1 互换类排序 9.2 插入类排序 9.3 选择类排序 9.4 拓扑分类 9.5 其他排序方法简介

清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 9.1.1冒泡排序 9.1.2快速排序

9.1 互换类排序 9.1.1 冒泡排序 9.1.2 快速排序

清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 9.1.1冒泡排序 首先,从表头开始往后扫描线性表,在扫描过程中逐次比较相邻两 个元素的大小。若相邻两个元素中,前面的元素大于后面的元素 ,则将它们互换,称之为消去了一个逆序。显然,在扫描过程中 ,不断地将两相邻元素中的大者往后移动,最后就将线性表中的 最大者换到了表的最后。 然后从后到前扫描剩下的线性表,同样,在扫描过程中逐次比较相 邻两个元素的大小。若相邻两个元素中,后面的元素小于前面的 元素,则将它们互换,这样就又消去了一个逆序。显然,在扫描 过程中,不断地将两相邻元素中的小者往前移动,最后就将剩下 线性表中的最小者换到了表的最前面。 对剩下的线性表重复上述过程,直到剩下的线性表变空为止,此时 的线性表已经变为有序

9.1 互换类排序 9.1.1 冒泡排序 首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两 个元素的大小。若相邻两个元素中，前面的元素大于后面的元素 ，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中 ，不断地将两相邻元素中的大者往后移动，最后就将线性表中的 最大者换到了表的最后。 然后从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相 邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的 元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描 过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下 线性表中的最小者换到了表的最前面。 对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时 的线性表已经变为有序

清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 冒泡排序 输入:无序序列P(1:n)。 输出:有序序列P(1:n) PROCEDURE BUBSORT(P, n) k=1: m=n WHILE(kp(i+1))THEN[发现逆序进行交换] {d=p(i);p(i)=p(i+1);p(i+1)=d;m=

9.1 互换类排序 冒泡排序 输入：无序序列P(1：n)。 输出：有序序列P(1：n)。 PROCEDURE BUBSORT(P，n) k＝1； m＝n WHILE (k＜m) DO [子表未空] { j＝m－1； m＝0 FOR i＝k TO j DO [从前往后扫描子表] IF (p(i)＞p(i＋1)) THEN [发现逆序进行交换] {d＝p(i)；p(i)＝p(i＋1)；p(i＋1)＝d；m＝i}

清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 j=k+1;k=0 FORi=mT0jBY一1DO[从后往前扫描子表] IF(p(i-1)>p(i)THN[发现逆序进行交换] d=p(i);p(i)=p(i-1);p(i-1)=d;k=i} RETURN

9.1 互换类排序 j＝k＋1； k＝0 FOR i＝m TO j BY －1 DO [从后往前扫描子表] IF (p(i－1) ＞p(i)) THEN[发现逆序进行交换] {d＝p(i)；p(i)＝p(i－1)；p(i－1)＝d；k＝i} } RETURN

清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 原序列 5173169 286 第1遍(从前往后)5←→17←→3←→1←→69←→4→2←→8←→6 结果15316742869 从后往前)15←→3←→16←→7←-←→28+→69 结果11532674689 第2遍(从前往后)115←→3←→267←→4←→689 结果113125646789 〔从后往前)113+→25←→6←→46789 结果11234566789 第3遍(从前往后)11234566789 最后结果11234566789

9.1 互换类排序

清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 bubsort(p, n) int n; et pl; I int m, k, j,i; et d k=0;m=n-1; while(kp[i+1])/*发现逆序进行交换* d=p[i];p[i]=p[i+1];p[i+1]=d;m=i;}

9.1 互换类排序 bubsort(p，n) int n； ET p[]； { int m，k，j，i； ET d； k＝0； m＝n－1； while (k＜m) /*子表未空*/ { j＝m－1； m＝0； for(i＝k；i＜＝j；i＋＋) /*从前往后扫描*/ if (p[i]＞p[i＋1]) /*发现逆序进行交换*/ {d＝p[i]；p[i]＝p[i+1]；p[i+1]＝d；m＝i；}

清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 j=k+1;k=0; for(i=m;i>=j;i--)/*从后往前扫描* if(p[i-1]>p[i])/*发现逆序进行交换*/ d=p[i];p[i]=p[i-1];p[i-1]=d;k=i; return:

9.1 互换类排序 j＝k＋1； k＝0； for (i＝m；i＞＝j；i－－) /*从后往前扫描*/ if (p[i－1] ＞p[i]) /*发现逆序进行交换*/ {d＝p[i]；p[i]＝p[i-1]；p[i-1]＝d；k＝i；} } return； }

清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 9.1.2快速排序 分割 无 序 分制 线 分制

9.1 互换类排序 9.1.2 快速排序

清华大学出版社 TSINGHUA UNIVERSITY PRESS 9.1互换类排序 首先,在表的第一个、中间一个与最后一个元素中选取 中项,设为P(k),并将P(k)赋给T,再将表中的第一个 元素移到P(k)的位置上。 然后设置两个指针i和j分别指向表的起始与最后的 位置。反复作以下两步: (1)将j逐渐减小,并逐次比较P(j)与T,直到发现 个P(j)T为止,将P(i)移到P(j)的位置上。 上述两个操作交替进行,直到指针i与j指向同一个 位置(即i=j)为止,此时将T移到P(i)的位置上

9.1 互换类排序 首先，在表的第一个、中间一个与最后一个元素中选取 中项，设为P(k)，并将P(k)赋给T，再将表中的第一个 元素移到P(k)的位置上。 然后设置两个指针i和j分别指向表的起始与最后的 位置。反复作以下两步： (1)将j逐渐减小，并逐次比较P(j)与T，直到发现一 个P(j)＜T为止，将P(j)移到P(i)的位置上。 (2)将i逐渐增大，并逐次比较P(i)与T，直到发现一 个P(i)＞T为止，将P(i)移到P(j)的位置上。 上述两个操作交替进行，直到指针i与j指向同一个 位置（即i＝j）为止，此时将T移到P(i)的位置上