算法设计与分析第2章排序算法.ppt

第2章 排序算法,主学习要点 一、偏序集 二、排序的一般方法 三、堆排序 四、快速排序 五、线性时间排序 六、中数排序,主要内容 2.1 排序 2.2 堆排序 2.3 快速排序 2.4 线性时间排序 2.5 中数排序,2.1 排序,2.1.1排序问题 排序(Sorting)是最常见的一种典型非数值计算。排序问题的输入一个线性表，要求对该线性表的元素重排，是得表中的元素递增（或递减）排列,1.偏序集 设R是非空集合A上的二元关系，x,y,zR,如果R满足： 1 自反性（x A,(x,x) R) 2 反对称性(x,y) R (y,x) Rx=y) 3 传递性 (x,y) R (y,z) R(x,z) R) 则称R为A上的偏序关系，记作,2. 原地置换排序算法 排序算法利用输入的线性表在原地重排其中的元素，且没有额外的内存开销,3.稳定排序算法 排序后表中相同原始的相对位置没有发生改变,4. 内外排序 根据排序是是否访问外存,2.1.2冒泡排序,第一轮,10,9,8,7,10,9,7,8,10,7,9,8,7,10,9,8,7,10,9,8,7,10,8,9,7,8,10,9,7,8,10,9,7,8,9,10,交换3次，循环3次,第二轮,第三轮,交换2次，循环2次,交换1次，循环1次,Bubble_Sort(A) 1 for i1 to lengthA-1 2 for jn to I 3 if (AjAj-1) 4 swap(Aj,Aj-1); 5 jj-1 6 ii+1,循环次数是 1/2(n-1)n 算法的复杂度 O(n2),2.1.3 交换排序 交换排序的思路是每次用当前的元素同其后元素一一比较交换,2.1.3 交换排序,第一轮,10,9,8,7,9,10,8,7,8,10,9,7,7,10,9,8,7,10,9,8,7,9,10,8,7,8,10,9,7,8,10,9,7,8,9,10,交换3次，循环3次,第二轮,第三轮,交换2次，循环2次,交换1次，循环1次,Exchange_Sort(A) 1 for i0 to lengthA-1 2 for jj=i+1 to lengthA 3 if (AjAi) 4 swap(Aj,Ai) 5 jj+1 6 ij+1,循环次数是 1/2(n-1)n 算法的复杂度 O(n2),2.1.4 选择排序 选择排序是指先从数据中选择最小的同第一个值交换，再从剩下的部分中选择最小的与第二个值交换，如此反复直至所有的数据均有序。,2.1.4选择排序,第一轮,10,9,8,7,10,9,8,7,10,9,8,7,7,9,8,10,7,9,8,10,7,9,8,10,7,8,9,10,7,8,10,9,7,8,9,10,交换1次，循环3次,第二轮,第三轮,交换1次，循环2次,交换0次，循环1次,Select_Sort(A) 1 int iTemp 2 int iPos; 3 for i0 to lengthA-1 4 iTempAi 5 iPosI; 6 for ji+1 to lengthA 7 if AjiTemp 8 iTempAj 9 iPosj; 10 AiPos Ai 11 AiiTemp 12 ii+1,2.1.5 插入排序 插入排序是从无序部分不经选择，随机抽取一个元素，然后插入到有序的部分的正确位置上。,2.1.5插入排序,第一轮,10,9,8,7,9,10,8,7,8,9,10,7,交换1次，循环1次,第二轮,第三轮,交换2次，循环2次,交换3次，循环3次,9,10,8,7,9,8,10,7,8,9,10,7,8,9,7,10,8,7,9,7,7,8,10,7,Insertion_Sort(A) 1 for j2 to lengthA-1 2 do keyAj 3 ij-1 4 while i0 and Ajkey 5 do Ai+1Ai 6 ii-1; 7 Ai+1key;,2.2 堆排序,堆排序在最坏和平均情况下的时间复杂度都为O(nlogn)，而且它是一种原地置换的算法，即在任何时候，数组中仅有固定数目的元素存在数组外。,2.2.1 堆 堆是一种数组对象，其定义如下： n个元素的序列k1,k2, ,kn当前仅当满足以下关系时，则称之为堆。 (a) ki k2i (b) kik2i ki k2i+1 ki k2i+1 (a)是大顶堆 (b)是小定堆,2.2.2 建堆 HEAPIFY是对堆进行操作的重要过程，其输入为一个数组A和小标i.当HEAPIFY被调用时，假定以LEFT(i)和RIGHT(i)为根的两棵子树都已是堆，Ai可能小于其子女，这与堆得定义不符。只需要自上而下进行调整，将Ai放到合适的位置，得到一个新的堆，称这种自堆顶至叶子的调整过程为“筛选”,HEAPIFY(A,i,length) 1 lLEFT(i) 2 rRIGHT(i) 3 if lAi 4 then largestl; 5 else largesi; 6 if lAlargest then largestr; 8 if largesti then swap(Ai, Alargest; HEAPIFY(A, largest, length);,20,5,10,14,9,7,3,1,8,2,1,2,3,4,5,6,7,8,9,10,Build_Heap(A) 1 for ilengthA/2 to 1 2 do HEAPIFY(A, i ,lengthA) 3 ii-1;,2.2.3 堆排序算法 堆排序算法先调用Build_Heap将输入数组A1, ,n构造成一个堆。则堆顶元素A1为最大值，将A1与An互换，破坏了原先的堆，从堆中“去掉”节点An，根节点的子女都是堆，调用HEAPIFY，将A1, ,n-1重建成一个新堆。堆排序算法继续这个过程，直至堆的大小有n-1到2为止，最终得到的数组为一个有序数组。,Heap_Sort(A) 1 Build_Heap(A, lengthA) 2 for ilengthA to 2 3 do swap(A1, Ai) 4 HEAPIFY(A, 1, i-1);,2.2.4 堆排序的应用,2.3 快速排序,2.3.1 快速排序的描述 快速排序的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，可分别对这两个部分继续进行排序，已达到整个记录有序。,设待排序序列为数组Ap, ,r，选取其中任意一个元素作为枢轴，然后按下述方法重排其余元素： (1) 将小于枢轴元素的其他元素放在其位置前面，大于它的元素放在其位置后面 (2) 已枢轴记录的最后的位置i作为分界线，将数组Ap, ,r分为两部分Ap, ,i-1和Ai+1, ,r,5,3,2,6,4,1,3,7,一趟快速排序 Partition(A, p, r) 1 pivotkeyAp; 2 while p=pivotkey 4 do rr-1; 5 ApAr; 6 Arpivotkey 7 while pr and Appivotkey 8 do pp+1; 9 ArAp 10 Appirotkey 11 return p,递归形式的快速排序算法,Quick_Sort(A,p,r) 1 if pr 2 then locPartition(A,p,r) 3 Quick_Sort(A,p,loc-1); 4 Quick_Sort(A, loc+1,p);,快速排序的最坏情况下的算法的复杂度为O(n2).平均情况下其算法的复杂度为O(nlgn), 在所有同数量级的排序算法中，快速排序的常数因子是最小的，所以就平均情况而言，快速排序被认为是排序算法中最佳的,2.3.2 快速排序的性能 (1) 在平均代价上好于其他算法，但在最坏情况下其性能不足 (2) 当输入序列为有序或基本有序时，算法的性能较差。 (3) 分割算法的好坏影响数据移动的次数 (4) 运行时间使用系统的堆栈,2.3.3 随机化的快速排序算法 Ran_Partition(A,p,r) 1 iRandom(p,r); 2 pivotkeyAi; 3 Aipivotkey; 4 Appivotkey; 5 return Partition(A,p,r);,随机快速排序算法,Ran_Quick_Sort(A,p,r) 1 if pr 2 then locRan_Partition(A,p,r) 3 Ran_Quick_Sort(A,p,loc-1) 4 Ran_Quick_Sort(A, loc+1,p),快速排序分析 快速排序的运行时间与分割是否对称有关。,2.4 线性时间排序,2.4.1排序算法的下界 1. 判断树模型,a1:a2,a2:a3,a1:a3,1,2,3,a1:a3,2,1,3,a2:a3,1,3,2,3,1,2,2,3,1,3,2,1,2 最坏情况下界 引理2-1 判定树的叶节点l与树深度h有如下关系：l=log l 引理2-3 任意一颗n元判定树至少有n!个叶节点,定理2-1 任一输入规模为n的比较排序算法在最坏情况下的比较次数为 w(n)=log n!=nlog n-1.443n 定理2-2 任意一颗对n个元素排序的判定树的高度为 (nlogn),A,C,3,6,4,1,3,4,1,4,2,0,2,3,0,1,B,1,1,3,3,4,4,4,6,1,2,3,4,5,6,2.4.2 计数排序 计数排序的基本思想就是对每一个输入元素x，确定出小于x的元素的个数。从而把x直接放到相应位置上。,Counting_Sort(A, B, k) 1 for i1 to k 2 do Ci0 3 for i1 to lengthA 4 do CAiCAi+1 5 for i2 to k 6 do CiCi+Ci-1 7 for ilengthA to 1 8 do BCAiAi 9 CAiCAi-1,2.4.3 基数排序 Radix_Sort(A,d) for i1 to d do 数组A使用一种稳定的排序算法进行排序,2.4.4 桶排序 桶排序假设输入有一个随机过程产生。该过程将元素一致地分布在区间0,1)上，其基本思想就是把区间0,1)划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。因为输入数随机分布在0,1)上，所以一般不会有很多数落在一个通中的情况。,Bucket_Sort(A) 1 nlength(A) 2 for i1 to n 3 do 将Ai插入到表BnAi中 4 for i0 to n-1 5 do 用插入排序对Bi进行排序 6 将B0,B1, ,Bn-1按顺序合并；,2.5 中数排序,n个元素组成的集合的第i个顺序统计就是该集合中第i小的元素。中位数既是该集合的中间点上的元素。 当n为奇数是，中位数唯一，既i=(n+1)/2 处。 当n为偶数时，存在两个中位数，在i=n/2和i=n/2+1处,2.5.1 最大和最小元素 Minmum(A) 1 minA0 2 for i to lengthA-1 3 do if mi