算法设计与分析*河南工程学院第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冒泡排序第一轮109871097810798710987109871089781097810978910交换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 交换排序第一轮109879108781097710987109879108781097810978910交换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选择排序第一轮109871098710987798107981079810789107810978910交换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 Aj0 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)是小定堆 NoImage算法设计与分析*河南工程学院 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);算法设计与分析*河南工程学院205101497318212345678910算法设计与分析*河南工程学院 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 pr 3 do 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:a2a2:a3a1:a31,2,3a1:a32,1,3a2:a31,3,23,1,22,3,13,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)算法设计与分析*河南工程学院AC36413414202301B11334446123456算法设计与分析*河南工程学院 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 minAi 4 then minAi 5 return min算法设计与分析*河南工程学院 2.5.2 普通选择问题 普通选择的根本思想是对输入数组进展分割，判别需求找的元素位于哪个部分而对相应的部分进展处置算法设计与分析*河南工程学院Ran_Select(A,p,r,i)If p=r then return ApqRan_Partition(A,p,r);kq-p+1;if i=k then return Ran_Select(A,p,q,i);else return Ran_Select(A,q+1,r,i-k);。