算法导论part_II---排序和顺序统计

1、1报告人：熊正强报告人：熊正强Introduction To Algorithms算法导论算法导论Part IIPart II：排序和顺序统计：排序和顺序统计6.堆排序堆排序7.快速排序快速排序8.线性时间排序线性时间排序9.中位数和顺序统计中位数和顺序统计主要内容主要内容3Chapter 6. 堆排序堆排序如：序列 12,36,24,85,47,30,53,91是一个小顶堆； 序列 91,47,85,24,36,53,30,16是一个大顶堆。 堆排序堆排序(Heap Sort)(Heap Sort)1.1.堆堆的定义的定义设有设有n n个元素的序列个元素的序列 R R1 1，R R2 2，R

2、 Rn n，当且仅当满足下述关，当且仅当满足下述关系之一时，称之为堆。系之一时，称之为堆。前者称为小顶堆，后者称为大顶堆。前者称为小顶堆，后者称为大顶堆。k ki ik2ik2i+1k ki ik2ik2i+1或或其中其中i=1,2,i=1,2,n/2,n/2 堆排序堆排序(Heap Sort)(Heap Sort) 在完全二叉树上，父结点和左右子节点之间的编号就是i和2i、2i+1的关系。因此一个序列可以和一棵完全二叉树对应起来，用父结点和左右子节点之间的关系可以直观的分析是否符合堆的特性。 如果该序列是一个堆，则对应的这棵完全二叉树的特点是：如果该序列是一个堆，则对应的这棵完全二叉树的特点

3、是：所有分支结点的值均不小于所有分支结点的值均不小于 ( (或不大于或不大于) )其子节点的值，即每其子节点的值，即每棵子树根结点的值是最大棵子树根结点的值是最大( (或最小或最小) )的。的。堆特点：堆顶元素是整个序列中最大堆特点：堆顶元素是整个序列中最大( (或最小或最小) )的元素。的元素。8516364730532491小顶堆 ：16，36，24，85，47，30，53，914791243653308516大顶堆：大顶堆：91，47，85，24，36，53，30，162 2堆排序堆排序 堆特点：堆顶元素是整个序列中最大堆特点：堆顶元素是整个序列中最大( (或最小或最小) )的元素。的元

4、素。 因此，实现堆排序需解决两个问题：因此，实现堆排序需解决两个问题： 1. 1. 如何将如何将n n个元素的排序序列按关键码建成堆（初始个元素的排序序列按关键码建成堆（初始堆）；堆）； 2. 2. 怎样将剩余的怎样将剩余的n-1n-1个元素按其关键码调整为一个新堆。个元素按其关键码调整为一个新堆。 堆排序：堆排序： 对对n n个元素的序列进行堆排序，先将其建成堆，以根结点个元素的序列进行堆排序，先将其建成堆，以根结点与第与第n n个结点交换；调整前个结点交换；调整前n-1n-1个结点成为堆，再以根结点与个结点成为堆，再以根结点与第第n-1n-1个结点交换；个结点交换；重复上述操作，直到整个序

5、列有序；重复上述操作，直到整个序列有序。堆排序算法堆排序算法void HeapSort(datetype R , int n) /*将序列将序列R1.Rn按堆排序方法进行排序按堆排序方法进行排序*/for(i=n/2; i0; i- ) HeapAdjust(R, i, n); /*将序列将序列R1.Rn建成初始堆建成初始堆 */for(i=n; i1; i-) R0=R1; /* 堆顶堆顶R1与堆底元素与堆底元素Ri交换交换 */ R1=Ri; Ri=R0; HeapAdjust(R,1, i-1); /*将将R1.Ri-1重新调整为堆重新调整为堆*/ 3.3.堆调整算法堆调整算法void

6、HeapAdjust(datetype R , int s, int t) /*以以Rs为根的子树只有为根的子树只有Rs与其左右孩子之间可能不满足与其左右孩子之间可能不满足堆特性堆特性*/ /*进行调整使以进行调整使以Rs为根的子树成为大顶堆为根的子树成为大顶堆*/datetype rc; /*缓冲变量缓冲变量*/rc=Rs；i=s; for(j=2*i; j=t; j=2*j) /*沿关键码较大的子结点向下筛选沿关键码较大的子结点向下筛选*/ if(jt & Rj.key Rj.key) break; /*不用调到叶子就到位了不用调到叶子就到位了*/ Ri=Rj; i=j; /*准备

7、继续向下调整准备继续向下调整 */ Ri=rc； /*插入插入*/4.性能分析： 设树高为k，由二叉树的性质知：k=log2n +1。从根到叶的筛选，关键码比较次数至多为2(k-1)次，移动记录至多k次。共n-1次。因此堆排序最坏情况下，时间复杂度为O(nlog2n)。11Chapter 7. 快速排序法快速排序法快速排序算法快速排序算法n快速排序算法是快速排序算法是 1962年年C.R.A.Hoare提出的划分提出的划分交换排序算法，交换排序算法，是应用非常广泛的一种排序算法是应用非常广泛的一种排序算法，被评为，被评为20世纪十大算法之一。世纪十大算法之一。n快速排序算法是一种基于分治策略的

8、快速排序算法是一种基于分治策略的算法算法 n分治策略的基本思想分治策略的基本思想 Step1-分解：将原问题分解为若干个规模更小分解：将原问题分解为若干个规模更小但结构与原问题相似的子问题但结构与原问题相似的子问题 Step2-求解：递归求解子问题求解：递归求解子问题 Step3-组合：将子问题的解组合为原问题的解组合：将子问题的解组合为原问题的解 代排序无序区间为Klow.high，分解的思路如下: 1. 选择基准：Klow.high中任选一个记录作为基准中任选一个记录作为基准(Pivot). 2. 划分子区间: 根据基准，根据基准， 将当前无序区间划分为左、右两个较小的子区间将当前无序区间

9、划分为左、右两个较小的子区间Klow.pivotpos-1)和和Kpivotpos+1.high. 3. 左边子区间: 所有记录的键值均小于等于基准记录所有记录的键值均小于等于基准记录(不妨记为不妨记为pivot)的键值的键值pivot.key 4. 右边子区间: 中所有记录的键值均大于中所有记录的键值均大于pivot.key 5. 基准到位：基准基准pivot则在正确的位置则在正确的位置(pivotpos)上，它无须参加后续的排序上，它无须参加后续的排序 例如： 4，8，7，9，3，5，6，2 调整： 2，3， (4) ，9，7，5，6，8Step1: 分解分解xxxStep1:分解分解算法

10、描述算法描述Int Partition(Elem K , int low, int high)pivot = Klow; /选取序列第一个记录做为基准选取序列第一个记录做为基准while(low high)/从序列的前后两端交替向中间扫描从序列的前后两端交替向中间扫描while(low = pivot) /向低端向低端-high;Klow = Khigh;/比基准小的移到低端比基准小的移到低端while(low high& Klow pivot) /向高端向高端+low;Khigh = Klow;/比基准大的移到高端比基准大的移到高端/endwhileKlow = pivot ; /

11、基准到位基准到位Retrun low /partitionpivotXLowhighK1.lowx还未处理元素还未处理元素Step2: 求解求解QuickSort(Elem K , int low, int high)if (low high) /长度大于长度大于1pivot = Partition(k, low, high); /将区间一分为二将区间一分为二QuickSort(K, low, pivot-1); / 左子区间快排左子区间快排QuickSort(K, pivot+1, high); / 右子区间快排右子区间快排/endif/endQuickSort递归调用快速排序递归调用快速排

12、序, 对左、右子区间Klow.pivotpos-1和Kpivotpos+1.high快速排序.Step3: 组合组合因为当“求解”步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，“组合”步骤无须进行其他操作，可看作是空操作。时间复杂度分析时间复杂度分析 假设第一次划分所得基准位置假设第一次划分所得基准位置i=k，则对，则对n个序列值进行快个序列值进行快排所需时间：排所需时间：T(n) = Tpass(n)+T(k-1)+T(n-k) Tpass(n)是对序列进行一次划分所需时间，它是和是对序列进行一次划分所需时间，它是和n成正比成正比的，我们记为的，我们记为Cn基准位置基

13、准位置k取从取从1到到n任意值，取任意一个值的概率相同。任意值，取任意一个值的概率相同。则快排所需平均时间值为：则快排所需平均时间值为：设 Tavg(1) = b 则 快速排序的时间复杂度为O(nlgn)18Chapter 8. 线性时间排序线性时间排序至今为止，我们见过的排序都是比较排序: 仅仅使用比较来比较各项的相对顺序。 比如：插入排序,合并排序,快速排序, 堆排序。比较排序中最快的最坏运行时间是O(nlgn). O(nlgn)O(nlgn)是不是我们能做到的极限是不是我们能做到的极限? ? 决策树决策树可以帮助我们回答这个问题 ： 1.1.排序算法的下界19排序a1, a2, , an

14、每个内部节点标识为 i:j i, j 1, 2, n.左子树表示当ai aj时的比较序列 .右子树表示当ai aj时的比较序列 .20决策树举例决策树举例排序 a1, a2, a3= 9 , 4 , 6 :每个内部节点标识为i:j,i,j1, 2, n.左子树表示当aiaj时的比较序列 .右子树表示当aiaj时的比较序列 .21决策树举例决策树举例每个内部节点标识为i:j,i,j1, 2, n.左子树表示当aiaj时的比较序列 .右子树表示当aiaj时的比较序列 .排序 a1, a2, a3= 9 , 4 , 6 :22决策树举例决策树举例每个内部节点标识为i:j,i,j1, 2, n.左子树

15、表示当aiaj时的比较序列 .右子树表示当aiaj时的比较序列 .排序 a1, a2, a3= 9 , 4 , 6 :23决策树举例决策树举例每个内部节点标识为i:j,i,j1, 2, n.左子树表示当aiaj时的比较序列.右子树表示当aiaj时的比较序列.排序 a1, a2, a3= 9 , 4 , 6 :24决策树举例决策树举例 决策树可以模拟任何的比较排序的执行过程过程:每个输入大小为n的序列都可以用这棵树表示. 将算法视为每次两个项相比后就分叉.树包含了所有可能比较的指令路径.算法的运行时间 = 路径的长度.最坏运行时间 = 树的高度.25决策树模型决策树模型2.计数排序计数排序假设n

16、个输入元素中的每一个都是介于0到k之间的整数，此处k为某个整数，当k=O(n)时，计数排序的运行时间是O(n)。计数排序的基本思想就是对每一个输入元素x，确定出小于x的元素个数。有了这一信息，就可以 把x直接放到它在最终输出数组中的位置上。在计数排序算法中，我们假设输入时隔数组A1.n，length(A)=n。另外还需要两个数组：存放排序结果的B1.n，以及提供临时存数区的C1.k计数排序伪代码COUNT-SORT(A,B,k)1 for i0 to k2 do Ci03 for j1 to lengthA4 do CAj CAj + 15 Ci 现在包含等于i的元素个数6for i 1 to

17、 k7 do Ci Ci + Ci - 18 Ci现在包含小于或等于i的元素个数7 for j lengthA downto 18 do BCAj Aj9 CAj CAj - 128计数排序举例计数排序举例for i1 to k do Ci 029循环循环1 1for j1 to n do CAj CAj + 1 Ci = |key = i|30循环循环2 2for j1 to n do CAj CAj + 1 Ci = |key = i|31循环循环2 2for j1 to n do CAj CAj + 1 Ci = |key = i|32循环循环2 2for j1 to n do CAj

18、CAj + 1 Ci = |key = i|33循环循环2 2for j1 to n do CAj CAj + 1 Ci = |key = i|34循环循环2 2for i2 to k do Ci Ci + Ci1 Ci = |key i|35循环循环3 3for i2 to k do Ci Ci + Ci1 Ci = |key i|36循环循环3 3for i2 to k do Ci Ci + Ci1 Ci = |key i|37循环循环3 3for jn downto 1 do BCAj Aj CAj CAj 138循环循环4 4for jn downto 1 do BCAj Aj CAj

19、 CAj 139循环循环4 4for jn downto 1 do BCAj Aj CAj CAj 140循环循环4 4for jn downto 1 do BCAj Aj CAj CAj 141循环循环4 4for jn downto 1 do BCAj Aj CAj CAj 142循环循环4 4如果 k n, 那么计数排序用的时间复杂度为O (n).和上一章的最小时间复杂度 O(nlgn)矛盾问题出在：比较排序比较排序 的时间复杂度是 O(nlgn) .计数排序不是 比较排序比较排序.实际上, 各项之间根本没有比较!43运行时间运行时间153 基数排序基数排序(radix sort)是一种

20、用在老式穿卡机上的算法。一张卡片有80列，每列可在12个位置中的任一处穿孔。排序器可被机械地“程序化”以检查每一迭卡片中的某一列，再根据穿孔的位置将它们分放12个盒子里。这样，操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面，第二个位置穿孔的其次，等等。 对十进制数字来说，每列中只用到10个位置(另两个位置用于编码非数值字符)。一个d位数占用d个列。因为卡片排序器一次只能查看一个列，要对n张片上的d位数进行排序就要有个排序算法。16基数排序例子优点：优点：实际上, 在大量输入的情况下，基排序速度很快，算法也很容易编码和维护。 缺点缺点: 与快速排序不同, 基排序基本上没有引用局部性, 这样在现代的处理器上一个调优的快速排序，利用内存的分层体系，可以在性能