基本的排序技术.pptVIP

第3章 查找与排序技术 3.2 基本的排序技术 3.2.1 冒泡排序与快速排序 3.2.2 简单插入排序与希尔排序 3.2.3 简单选择排序与堆排序 3.2.4 其他排序方法简介 3.3.1 冒泡排序与快速排序 1. 冒泡排序首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后。然后从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下线性表中的最小者换到了表的最懊妗对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。 输入：无序序列P(1：n)。 输出：有序序列P(1：n)。PROCEDURE BUBSORT(P，n)k＝1； m＝nWHILE (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} 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 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；} 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；} 2. 快速排序 首先，在表的第一个、中间一个与最后一个元素中选取中项， 设为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)的位置上。 线性表的分割 输入：待分割的子表P(m：n)。 输出：分割后的分界线位置i。 PROCEDURE SPLIT(P，m，n，i) 选取P(k) 其中m≤k≤n T＝P(k)；P(k)＝P(m) i＝m；j＝n  WHILE (i≠j) DO { WHILE (P(j)≥T)and(i＜j) DO j＝j－1 IF (i＜j) THEN { P(i)＝P(j)；i＝i＋1 WHILE (P(i)≤ T)and(i＜j) DO i＝i＋1 IF (i＜j) THEN { P(j)＝P(i)；j＝j－1 } } } P(i)＝T RETURN 快速排序的递归算法输入：待排序的子表P(m：n)。输出：有序子表P(m：n)。PROCEDURE QKSORT1(P，m，n)IF (n＞m) THEN [子表不空] { SPLIT(P，m，n，i)； [分割] QKSORT1(P，m，i－1)；[对前面子表进行快速排序] QKSORT1