分治策略3快速排序.ppt

Software College, Northeast University neuzl@163.com 2.5 快速排序问题 由著名计算机科学家霍尔(C.A.R.Hoare)给出。 把原序列分成两个子问题，在被分成的两个子问题以后不再需要归并。 被分成的两个子问题必须满足一子问题中的所有元素都小于或等于另一子问题的任何一个元素。 2.5 快速排序问题 基本策略是： 选取A的某个元素t=A(s)，然后将其他元素重新排列，使A(1:n)中所有在t以前出现的元素都小于或等于t，而在t之后出现的元素都大于或等于t。 算法步骤 分解(Divide):以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q]和a[q+1:r],使得a[p:q-1]中任何一个小于等于a[q],下标q在划分过程中确定。 递归求解(conquer):通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序。 合并(Merge):由于对a[p:q-1]和a[q+1:r]的排序是就地进行的，所以在a[p:q-1]和a[q+1:r]都已排好的序后步需执行任何计算a[p:r]就已排好序。 快速排序 Templateclass Type void QuickSort(Type a[ ], int p,int r) { if(pr){ int q=Partition(a,p,r); QuickSort(a,p,q-1);//对左半段排序 QuickSort(a,q+1,r);//对右半段排序 } } 划分过程 Partition的过程中，首先要选择一个元素，根据其值划分数组。称该元素为中轴。 选择中轴有许多不同的策略，我们使用最简单的策略，选择第一个元素：s = a[p]。 划分举例 划分的过程 使用一种两次扫描子数组的方法:一次是从左到右,另一次是从右到左,每次都把子数组的元素和中轴进行比较 从左到右的扫描从第二个元素开始,希望小于中轴的元素位于子数组的第一部分，扫描会忽略小于中轴的元素，直到遇到第一个大于等于中轴的元素才会停止， 从右到左的扫描从最后一个元素开始，因为我们希望大于中轴的元素位于子数组的第二部分，扫描会忽略大于中轴的元素，直到遇到第一个小于等于中轴的元素才会停止。 划分程序 templateclass Type int Partition(Type a[ ],int p,int r) { int i = , j = ; Type x = ; while( true ) { while( a[ ++i ]x ); while( a[ - - j ]x ); if( ) break; Swap( a[ i ], a[ j ] ); } a[ p ] = ; a[ j ] = ; return j; } 问题： 扫描停止的时候i和j有几种关系，每种代表哪种情况？ 下标i和j会不会超出a的下标界？ 该排序算法是否稳定？ 算法分析 最坏情况：划分的两个区域分别包含n－1个元素和1个元素，也就是已经排好序的数组。如果用A[0]作为中轴，从左到右的扫描会停在A[1]上，而从右到左的扫描会一直处理到A[0]，导致分裂点出现在0这个位置，所以，在进行了n＋1次比较之后建立了分区，并且将A[0] 和它本身进行了交换以后，快速排序算法还会对严格递增的数组A[1···n-1]进行排序，对规模减小了的严格递增数组的排序会一直继续到最后一个子数组A[n-2···n-1]，这种情况下，键值比较的总次数应该等于： (n+1)+n+…+3=O(n2) 算法分析 最坏情况：划分的两个区域分别包含n－1个元素和1个元素，如果每一步都出现这种情况，其复杂性T(n) O(1) n≤1 T(n)= T(n-1)+O(n) n1 解得：T(n)=O(n2) 最好情况 每次划分所取的基准都恰好为中值，即每次划分都产生两个大小为n/2的区域， O(1) n≤1 T(n)= 2T(n/2)+O(n) n1 T(n)=O(nlogn) 计数排序、冒泡排序、插入排序、选择排序、归并排序和快速排序的时间复杂性如下： 算法 最坏复杂性