软件技术基础第三章2基本排序.ppt

冒泡排序与快速排序(交换排序法) 简单插入排序与希尔排序(插入排序法) 简单选择排序与堆排序(选择排序法) 其他排序方法简介,排序是数据处理的重要内容,是指将一个无序序列整理成按值非递减顺序排列的有序序列(本章仅介绍内部排序:即能够在内存中完成的排序),基本排序,交换排序,交换排序的思想是通过交换元素以达到消除逆序的目的 冒泡排序 (1)从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后。 (2)除去最后已经冒出的元素,对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时冒出的元素构成的线性表已经变为有序。,逆序：在数组An中,存在iAj则称Ai和Aj构成一个逆序,5 1 7 3 1 6 9 4 2 8 6,冒泡排序需要经过(n-1)+(n-2)+(n-3)+1=n(n-1)/2次比较 算法复杂度量级为O(n2),双向冒泡排序 (1)从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后。 (2)从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下线性表中的最小者换到了表的最前面 (3)对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。,bubsort(p，n) int n； ET p； int m，k，j，i； ET d； k0； mn1； while (km) /*子表未空*/ jm1； m0； for(ik；ij；i) /*从前往后扫描*/ if (pipi1) /*发现逆序进行交换*/ dpi；pipi+1；pi+1d；mi； jk1； k0； for (im；ij；i) /*从后往前扫描*/ if (pi1 pi) /*发现逆序进行交换*/ dpi；pipi-1；pi-1d；ki； return； ,输入：无序序列P(1：n)。 输出：有序序列P(1：n)。,虽然从算法上优化了冒泡法排序,但是其最坏算法复杂度量级依然是O(n2),快速排序: 解决冒泡排序中一次仅通过交换两个相邻元素完成一个逆序的消除的效率不高的问题 快速排序的思想为:从线性表中取一个元素,设为T,小于T的元素移到T前,大于T的元素移到T后从而将线性表以T为分界分成两个子表. 关键是对线性表的分割.,首先，在表的第一个、中间一个与最后一个元素中选取其中一项作为枢纽， 设为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指向同一个位置 （即ij）为止，此时将T移到P(i)的位置上。,算法描述,9,例: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,10,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,11,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,12,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,13,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,14,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,15,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,16,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,17,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,18,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,19,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,20,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,21,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,22,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,界点,23,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,界点,24,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,界点,25,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,界点,26,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,界点,27,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,界点,28,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,界点,29,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,界点,30,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,界点,31,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,界点,32,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,界点,33,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,界点,34,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,界点,35,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,13,38,27,38,65,97,49,49,76,13,65,76,27,49,97,49,界点,36,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,13,38,27,38,65,97,49,49,76,13,65,76,27,49,97,49,界点,37,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,13,38,27,38,65,97,49,49,76,13,65,76,27,49,97,49,界点,快速排序结束, 最坏情况: Tp = O( ? ),n2,出现在原序列已经有序., 幸运情况: . . . . ,平均情况: T ( n ) = O( n ) + 2 T ( n / 2 ) = O( n ) + 2 O( n / 2 ) + 2 T ( n / 22 ) = 2 O( n ) + 22 T ( n / 22 ) = . . = k O( n ) + 2k T ( n / 2k ),n / 2k = 1 k = log2 n,= O( n log2 n ) + n T ( 1 ) = O( n log2 n ),快速排序的非递归算法 输入：待排序的子表P(m：n)。 输出：有序子表P(m：n)。 PROCEDURE QKSORT2(P，m，n) 建立一个栈，并初始化栈中每一个元素有两个数据项：子表第一个元素下 标与最后一个元素下标 将下标m与n进栈 子表进栈 WHILE 栈非空 DO 还有子表需要分割 从栈中退出两个下标m与n 从栈中退出一个子表进行分割 WHILE (nm) DO 子表不空 SPLIT(P，m，n，i) 进行分割 将下标i1与n进栈 将分割出的后一个子表进栈 ni1 对分割出前一个子表继续进行分割 RETURN,前面是通过交换来消除逆序,下面采用插入 简单插入排序(插入类排序) 将无序序列中的各元素依次插入已有序的线性表中 输入：待排序序列P(1：n)。 输出：有序序列P(1：n)。 PROCEDURE INSORT(P，n) FOR j2 TO n DO TP(j)；kj1 WHILE (k0)and(P(k)T) DO P(k1)P(k)；kk1 P(k1)T RETURN,5 1 7 3 1 6 9 4 2 8 6 j2 1 5 7 3 1 6 9 4 2 8 6 j3 1 5 7 3 1 6 9 4 2 8 6 j4 1 3 5 7 1 6 9 4 2 8 6 j5 1 1 3 5 7 6 9 4 2 8 6 j6,1 1 3 5 6 7 9 4 2 8 6 j7 1 1 3 5 6 7 9 4 2 8 6 j8 1 1 3 4 5 6 7 9 2 8 6 j9 1 1 2 3 4 5 6 7 9 8 6 j10 1 1 2 3 4 5 6 7 8 9 6 j11 1 1 2 3 4 5 6 6 7 8 9 简单插入排序在最坏情况下需要比较n(n-1)/2次,insort(p，n) int n； ET p； int j，k； ET t； for (j1； jn； j) tpj； kj1； while (k0)&(pkt) pk1pk； kk1； pk1t； return； ,基本思想:将整个无序序列分割成若干小子序列分别进行插入排序 子序列的分割方法如下： 将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。 增量序列一般取 htn/2k(k1，2，log2n)， 其中n为待排序序列的长度。,希尔排序(插入类排序),shlsort(p，n) int n； ET p； int h，j，i； ET t； hn/2； while (h0) for (jh； jn1； j) tpj； ijh； while (i0)&(pit) pihpi； iih； piht； hh/2； return； ,输入：待排序序列P(1：n)。 输出：有序序列P(1：n)。,代码比较,insort(p，n) int n； ET p int j，k； ET t； for (j1； jn； j) tpj； kj1； while (k0)&(pkt) pk1pk； kk1； pk1t； return ,shlsort(p，n) int n； ET p； int h，j，i； ET t； hn/2； while (h0) for (jh； jn1； j) tpj； ijh； while (i0)&(pit) pihpi； iih； piht； hh/2； return； ,选择排序,简单选择排序 基本思想:扫描线性表,选出最小的元素,交换到最前,然后对剩余的元素采用相同的方法,直到表空.对长度为n的序列,选择排序需要扫描n-1次,注意,这里的方法和冒泡法排序有区别 选择vs冒泡 冒泡:目的在于减少逆序,通过遇到相邻构成逆序就交换的的方式,逐步将最小(大)元素冒到最前 选择:目的在于选取最小(大)元素,通过扫描寻找方式,直接和最前(后)元素进行一次交换.,简单选择排序在最坏情况下需要比较n(n-1)/2次,selesort(p，n) int n； ET p； int i，j，k； ET d； for (i0； in2； ii1) ki； for (ji1； jn1； jj1) if (pjpk) kj； if (k!i) dpi；pipk；kd； return； ,输入：无序序列P(1：n)。 输出：有序序列P(1：n)。,堆排序(选择排序的一种),复习: 堆的定义： 具有n个元素的序列(h1，h2，hn)， 当且仅当满足 或 (i1，2，n/2)时称之为堆。,序列(91，85，53，36，47，30，24，12)是一个堆,如何调整建堆 在一棵具有n个结点的完全二叉树（用一维数组H(1：n) 表示）中，假设结点H(m)的左右子树均为堆，现要将以 H(m)为根结点的子树也调整为堆。 具体的步骤: 将根结点值与左右子树的根结点值进行比较,若不满足堆的条件,则将左右子树的根结点值中的大者与根结点值进行交换.此调整过程一直做到所有子树均为堆为止,调整建堆 已知H.rsm中记录的关键字除H.rs.key之外均满足堆的定义，本汉书调整H.rs的关键字，使H.rsm成为一个大顶堆（对其中记录的关键字而言） Void HeapAdjust(HeapType ,由堆的定义,可得堆排序的方法为: (1)首先将一个无序序列建成堆。 (2)然后将堆顶元素（序列中的最大项）与堆中最后一个 元素交换（最大项应该在序列的最后）。 不考虑已经换到最后的那个元素，只考虑前n1个元 素构成的子序列，显然，该子序列已不是堆，但左、 右子树仍为堆，可以将该子序列调整为堆。 反复做第(2)步，直到剩下的子序列为空为止。,堆排序 输入：无序序列H(1：n)。 输出：无序序列H(1：n)。,heapsort(HeapType ,平均时间复杂度是O(nlogn) 最坏情况下的时间复杂度是O(nlogn) Good!,堆排序方法对于记录数较少的文件并不值得提倡,但对n较大的文件还是很有效的.因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复”筛选”上.对深度为k的堆,筛选算法中进行的关键字比较次数至多为2(k-1)次,则建含n个元素,深度为h的堆时,总共进行的关键字比较次数不超过4n.又,n个结点的完全二叉树的深度为logn+1,则调整建立新堆时调用HeapAdjust过程n-1次,总共进行的比较次数不超过下式的值: 2(log(n-1)+log(n-2)+log2)2nlogn,所谓归并是将两个或两个以上的有序表合并成一个新的有序表 设线性表L(1：n)中的某段L(low：high)已经部分有序，即它的两个子表L(low：mid)与L(mid1：high)（其中lowmidhigh）已经有序，现要将这两个有序子表归并成一个有序子表L(low：high)。,归并排序,请翻到p106见2.7,2.11 我们已经学会将两个有序序列合并成一个有序序列的方法,实现上述两个子表归并的基本做法如下： (1)开辟一个与线性表L同样大小的表空间A。 (2)设置三个指针i，j，k，其初始状态分别指向两个有序子 表的首部及表空间A中与L中需要进行排序段相对应空间 的首部。即ilow，jmid1，klow。 (3)沿两个有序子表扫描： 若L(i)L(j)，则A(k)L(i)，且i与k指针均加1； 否则A(k)L(j)，且j与k指针均加1。 如此反复，直到有一个子表的指针已经指到末端（即子 表内的元素已经取空）为止。 (4)将未取空的子表中的剩余元素依次放入表空间A中。 (5)将A中的对应段复制到L中。,复习,两个相邻有序子表的合并 输入：两个相邻有序子表L(low：mid)与L(mid1：high) （其中lowmidhigh）；工作数组A(low：high)。 输出：有序子表L(low：high)。 static merge(p，low，mid，high，a) int low，mid，high;ET p，a； int I，j，k； ilow； jmid1； klow； while (imid)&(jhigh) if (pi1pj1) ak1pi1； ii1； else ak1pj1； jj1； kk1； if (imid) for(ji； jmid； j) ak1pj1； kk1； else if (jhigh) for(ij； ihigh； i) ak1pi1； kk1； for(ilow；ihigh；i) pi1ai1； return； ,归并排序是指把一个长度为N的线性表看成是由N个长度为1的有序表组成的,然后进行两两归并,最后得到长度为N的有序线性表,由于归并是两两进行的,因此也称为2路归并排序,一趟归并之后,两趟归并之后,归并排序的非递归算法 输入：无序序列P(1：n)。 输出：有序序列P(1：n)。 #include “stdlib.h“ mergsort(p，n) int n； ET p； int m，k，j，low，high，mid； ET *a； amalloc(n*sizeof(ET)； m1； while (mn) k2*m； for(j1； jn； jjk) lowj； highjk1； midjm1； if (highn) highn； if (highmid) merge(p,low,mid,high,a)； mk； fr