排序算法.htm

算法与数据结构——快速排序 01背包问题,是一个简单的程序,高手就不用研究了

            <BR><BR>Partition对L[p..r]进行划分时，以pivot作为划分的基准，然后分别从左、右两端开始，扩展两个区域L[p..i]和L[j..r]，使得L[p..i]中元素的值小于或等于pivot，而L[j..r]中元素的值大于或等于pivot。初始时i=p-1，且j=i+1，从而这两个区域是空的。在while循环体中，位置j逐渐减小，i逐渐增大，直到L[i]≥pivot≥L[j]。如果这两个不等式是严格的，则L[i]不会是左边区域的元素，而L[j]不会是右边区域的元素。此时若i在j之前，就应该交换L[i]与L[j]的位置，扩展左右两个区域。 
            while循环重复至i不再j之前时结束。这时L[p..r]己被划分成L[p..q]和L[q+1..r]，且满足L[p..q]中元素的值不大于L[q+1..r]中元素的值。在过程Partition结束时返回划分点q。 
            <BR><BR>寻找支点元素select_pivot有多种实现方法，不同的实现方法会导致快速排序的不同性能。根据分治法平衡子问题的思想，我们希望支点元素可以使L[p..r]尽量平均地分为两部分，但实际上这是很难做到的。下面我们给出几种寻找pivot的方法。 
            <BR><BR>1. 选择L[p..r]的第一个元素L[p]的值作为pivot； <BR><BR>2. 
            选择L[p..r]的最后一个元素L[r]的值作为pivot； <BR><BR>3. 
            选择L[p..r]中间位置的元素L[m]的值作为pivot； <BR><BR>4. 
            选择L[p..r]的某一个随机位置上的值L[random(r-p)+p]的值作为pivot； 
            <BR><BR>按照第4种方法随机选择pivot的快速排序法又称为随机化版本的快速排序法，在下面的复杂性分析中我们将看到该方法具有平均情况下最好的性能，在实际应用中该方法的性能也是最好的。 
            <BR><BR>下面是一个快速排序的Java 
            Applet演示程序，该程序使用第一种pivot选择法，即选L[p]为pivot，因此Partition过程作了一些简化，与我们这里的Partition过程实现方法不同，但功能相同。该程序是针对用数组实现的线性表，用C语言实现的。 
            <BR><BR>　 
            <BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR>线性时间排序算法 
            <BR><BR>我们已经知道，通过比较确定两个元素之间相对位置的比较排序算法计算时间复杂性下界为O(nlogn)，要想改进这个下界，就必须对输入的数据作某些限制。下面介绍的几种排序算法都可以在O(n)时间内对一个线性表进行排序，但是他们要求输入数据满足某种条件。 
            <BR><BR>计数排序 <BR>基数排序 <BR>桶排序 <BR>计数排序 Counting Sort 
            <BR><BR>计数排序是一个非基于比较的线性时间排序算法。它对输入的数据有附加的限制条件： <BR><BR>1. 
            输入的线性表的元素属于有限偏序集S； <BR><BR>2. 
            设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。 
            <BR><BR>在这两个条件下，计数排序的复杂性为O(n)。 
            <BR><BR>计数排序算法的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。 
            <BR><BR>假设输入的线性表L的长度为n，L=L1,L2,..,Ln；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；则计数排序算法可以描述如下： 
            <BR><BR>1. 扫描整个集合S，对每一个Si∈S，找到在线性表L中小于等于Si的元素的个数T(Si)； <BR><BR>2. 
            扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1。 
            <BR><BR>具体的实现如下。 
            <BR><BR>注意：在以下的讨论中，为了方便，我们假设线性表是用数组来实现的，并且假设线性表的元素类型TElement为整型，其值在1..k之间，线性表的长度为n，且k=O(n)。这些假设对计数排序算法没有实质的影响，但是可以使以下介绍的算法看起来容易理解。 
            <BR><BR>在下面的计数排序算法中，我们假设L为输入的长度为n的线性表，输出的排序结果存放在线性表R中。算法中还用到一个辅助表tmp用于对输入元素进行计数。 
            <BR><BR>Type <BR><BR>TElement=1..k; <BR><BR>TList=array 
            [1..maxlength] of TElement; <BR><BR>TPosition=integer; 
            <BR><BR><BR><BR>procedure Counting_Sort(var L,R:TList); <BR><BR>var 
            <BR><BR>i,j:integer; <BR><BR>tmp:TList; <BR><BR>begin <BR><BR>1 for 
            i:=1 to k do tmp[i]:=0; <BR><BR>2 for j:=1 to n do inc(tmp[L[j]]); 
            <BR><BR>//执行完上面的循环后，tmp[i]的值是L中等于i的元素的个数 <BR><BR>3 for i:=2 to k do 
            tmp[i]:=tmp[i]+tmp[i-1]; <BR><BR>//执行完上面的循环后，tmp[i]的值是L中小于等于i的元素的个数 
            <BR><BR>4 for j:=n downto 1 do //注意这里的downto保证了排序的稳定性 <BR><BR>begin 
            <BR><BR>5 R[tmp[L[j]]]:=L[j];//L[j]存放在输出数组R的第tmp[L[j]]个位置上 <BR><BR>6 
            dec(tmp[L[j]]); //tmp[L[j]]表示L中剩余的元素中小于等于L[j]的元素的个数 <BR><BR>end; 
            <BR><BR>end; 
            <BR><BR>图1所示的是Counting_Sort作用于一个输入数组L[1..8]上的过程，其中L的每一个元素都是不大于k=6的正整数。 
            <BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR><BR>图1 计数排序算法演示 
            <BR><BR>容易理解，算法的第(l)行是对数组tmp初始化。第(2)行检查每个输入元素。如果输入元素的键值为i，则tmp[i]增1。因此，在第(2)行执行结束后，tmp[i]中存放着值等于i的输入元素个数，i=1,2,..,k。算法的第(3)行，对每个i=1,2,..,i，统计值小于或等于i的输入元素个数。最后在(4)-(8)行中，将每个元素L[j]存放到输出数组R中相应的最终位置上。如果所有n个元素的值都不相同，则共有tmp[L[j]]个元素的键值小于或等于L[j]，而小于L[j]的元素有tmp[L[j]]-1个，因此tmp[L[j]]就是L[j]在输出数组R中的正确位置。当输入元素有相同的值时，每将一个L[j]存放到数组R时，tmp[L[j]]就减1，使下 
            <BR>个值等于L[j]的元素存放在输出数组R中存放元素L[j]的前一个位置上。 
            <BR><BR>计数排序算法的计算时间复杂性很容易分析。其中，第(1)行需要O(k)时间；第(2)行需要O(n)时间，第(3)行需要O(k)时间；第(4)-(8)行的for循环需要O(n)时间。这样，整个算法所需的计算间为O(n+k)。当k=O(n)时，算法的计算时间复杂性为O(n)。 
            <BR><BR>我们看到，计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置。因此，计数排序算法不是一个基于比较的排序算法，从而它的计算时间下界不再是Ω(nlogn)。另一方面，计数排序算法之所以能取得线性计算时间的上界是因为对元素的取值范围作了一定限制，即k=O(n)。如果k=n2,n3,..，就得不到线性时间的上界。此外，我们还看到，由于算法第4行使用了downto语句，经计数排序，输出序列中值相同的元素之间的相对次序与他们在输入序列中的相对次序相同，换句话说，计数排序算法是一个稳定的排序算法，但显然不是原地置换排序算法。 
            <BR><BR>基数排序 Radix Sort 
            <BR><BR>基数排序是一种用在老式穿卡机上的算法。一张卡片有80列，每列可在12个位置中的任一处穿孔。排序器可被机械地"程序化"以检查每一迭卡片中的某一列，再根据穿孔的位置将它们分放12个盒子里。这样，操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面，第二个位置穿孔的其次，等等。 
            <BR><BR>对十进制数字来说，每列中只用到10个位置(另两个位置用于编码非数值字符)。一个d位数占用d个列。因为卡片排序器一次只能查看一个列，要对n张片上的d位数进行排序就要有个排序算法。 
            <BR><BR>直感上，大家可能觉得应该按最重要的一位排序，然后对每个盒子中的数递归地排序，最后把结果合并起来。不幸的是，为排序每一个盒子中的数，10个盒子中的9个必须先放在一边，这个过程产生了许多要加以记录的中间卡片堆。 
            <BR><BR>与人们的直感相反，基数排序是首先按最不重要的一位数字排序来解决卡片排序问题的。同样，把各堆卡片收集成一迭，其中0号盒子中的在1号盒子中的前面，后者又在2号盒子中的前面，等等。然后对整个一迭卡片按次重要位排序，并把结果同样地合并起来。重复这个过程，直到对所有的d位数字都进行了排序。所以，仅需要n遍就可将一迭卡片排好序。图1说明了基数排序作“一迭”7个三位数的过程。第一列为输入，其余各列示出了对各个数位进行逐次排序后表的情形。垂直向上的箭头指示了当前要被加以排序的数位。 
            <BR><BR>　 <BR>图1 基数排序作用于一个由7个3位数组成的表上的过程 
            <BR><BR>关于这个算法很重要的一点就是按位排序要稳定。由卡片排序器所故的排序是稳定的，但操作员在把卡片从盒子里拿出来时不能改变他们的次序，即使某一盒子中所有卡片在给定列上的穿孔位置都相同。 
            <BR><BR>在一台典型的顺序随机存取计算机上，有时采用基数排序来对有多重域关键字的记录进行排序。例如，假设我们想根据三个关键字处、月和日来对日期排序。对这个问题，可以用带有比较函数的排序算法来做。给定两个日期，先比较年份，如果相同，再比较月份，如果再相同，再比较日。这儿我们可以采用另一个方法，即用一种稳定的排序方法对所给信息进行三次排序：先对日，其次对月，再对年。 
            <BR><BR>基数排序的代码是很简单的、下面的过程假设长度为n的数组A中的每个元素都有d位数字，其中第1位是最低的，第d位是最高位。 
            <BR><BR>procedure Radix_Sort(var L:List;d:integer); <BR><BR>var 
            <BR><BR>i:integer; <BR><BR>begin <BR><BR>1 for i:=1 to d do 
            <BR><BR>2 使用一种稳定的排序方法来对数组L按数字i进行排序; <BR><BR>end; 
            <BR><BR>基数排序的正确性可以通过对正在被排序的列进行归纳而加以证明。对本算法时间代价的分析要取决于选择哪种稳定的中间排序算法。当每位数字都界于l到k之间，且k不太大时，可以选择计数排序。对n个d位数的每一遍处理的时间为O(n+k)，共有d遍，故基数排序的总时间为θ(dn+kd)。当d为常数，k=O(n)时，基数排序有线性运行时间。 
            <BR><BR>某些计算机科学家倾向于把一个计算机字中所含位数看成是θ(lgn)。具体一点说，假设共有dlgn位数字，d为正常数。这样，如果待排序的每个数恰能容于一个计算机字内，我们就可以把它视为一个以n为基数的d位数。看一个例子：对一百万个64位数排序。通过把这些数当作是以216为基数的四位数，用基数排序四遍就可完成排序。这与一个典型的O(nlgn)比较排序相比要好得多，后者对每一个参加排序的数约要lgn=20次操作。但有一点不理想，即采用计数排序作为中间稳定排序算法的基数排序版本不能够进行原地置换排序，而很多O(nlgn)比较排序算法却是可以的。因此，当内存比较紧张时，一般来说选择快速排序更合适些。 
            <BR><BR><BR><BR>桶排序 Bin Sort 
            <BR><BR>平均情况下桶排序以线性时间运行。像计数排序一样，桶排序也对输入作了某种假设， 
            因而运行得很快。具体来说，计数排序假设输入是由一个小范围内的整数构成，而桶排序则 
            假设输入由一个随机过程产生，该过程将元素一致地分布在区间[0，1)上。 
            <BR><BR>桶排序的思想就是把区间[0，1)划分成n个相同大小的子区间，或称桶，然后将n个输入数分布到各个桶中去。因为输入数均匀分布在[0，1)上，所以一般不会有很多数落在 
            一个桶中的情况。为得到结果，先对各个桶中的数进行排序，然后按次序把各桶中的元素列 出来即可。 
            <BR><BR>在桶排序算法的代码中，假设输入是个含n个元素的数组A，且每个元素满足0≤ 
            A[i]&lt;1。另外还需要一个辅助数组B[O..n-1]来存放链表实现的桶，并假设可以用某种机制来维护这些表。 
            <BR><BR>桶排序的算法如下，其中floor(x)是地板函数，表示不超过x的最大整数。 <BR><BR>procedure 
            Bin_Sort(var A:List); <BR><BR>begin <BR><BR>1 n:=length(A); 
            <BR><BR>2 for i:=1 to n do <BR><BR>3 将A[i]插到表B[floor(n*A[i])]中; 
            <BR><BR>4 for i:=0 to n-1 do <BR><BR>5 用插入排序对表B[i]进行排序; <BR><BR>6 
            将表B[0],B[1],...,B[n-1]按顺序合并; <BR><BR>end; <BR><BR><BR><BR>图1 
            Bin_Sort的操作 
            <BR><BR>图1演示了桶排序作用于有10个数的输入数组上的操作过程。(a)输入数组A[1..10]。(b)在该算法的第5行后的有序表(桶)数组B[0..9]。桶i中存放了区间[i/10，(i+1)/10]上的值。排序输出由表B[O]、B[1]、...、B[9]的按序并置构成。 
            <BR><BR>要说明这个算法能证确地工作，看两个元素A[i]和A[j]。如果它们落在同一个桶中，则它们在输出序列中有着正确的相对次序，因为它们所在的桶是采用插入排序的。现假设它们落到不同的桶中，设分别为B[i'']和B[j'']。不失一般性，假设i''&lt;j''。在算法的代码中，当第6行中将B中的表并置起来时，桶B[i'']中的元素先于桶B[j'']中的元素，因而在输出序列中A[i]先于A[j]。现在要证鰽[i]≤A[j]。假设情况正好相反，我们有： 
            <BR><BR>i''=floor(n*A[i])≥floor(n*A[j])=j'' <BR><BR>得矛盾 
            (因为i''&lt;j'')，从而证明桶排序能正确地工作。 
            <BR><BR>现在来分析算法的运行时间。除第5行外，所有各行在最坏情况的时间都是O(n)。第5行中检查所有桶的时间是O(n)。分析中唯一有趣的部分就在于第5行中插人排序所花的时间。 
            <BR><BR>为分析插人排序的时间代价，设ni为表示桶B[i]中元素个数的随机变量。因为插入排序以二次时间运行，故为排序桶B[i]中元素的期望时间为E[O(ni2)]=O(E[ni2])，对各个桶中的所有元素排序的总期望时间为： 
            <BR><BR>(1) 
            <BR><BR>为了求这个和式，要确定每个随机变量ni的分布。我们共有n个元素，n个桶。某个元素落到桶B[i]的概率为l/n，因为每个桶对应于区间[0，1)的l/n。这种情况与投球的例子很类似：有n个球 
            (元素)和n个盒子 
            (桶)，每次投球都是独立的，且以概率p=1/n落到任一桶中。这样，ni=k的概率就服从二项分布B(k;n,p)，其期望值为E[ni]=np=1，方差V[ni]=np(1-p)=1-1/n。对任意随机变量X，有: 
            <BR><BR>　 (2) 
            <BR><BR>将这个界用到(1)式上，得出桶排序中的插人排序的期望运行时间为O(n)。因而，整个桶排序的期望运行时间就是线性的。 
            <BR><BR>下面的Java Applet程序演示了桶排序的基本思想。 
            <BR><BR><BR><BR>在该演示程序中，线性表的元素类型为整型，桶的标号为整数，算法将值为i的元素放入标号为i的桶中，再按照桶的标号的顺序将元素依次取出，就得到了最终的排序结果。 
            <BR><BR></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><!-- 页面内容结束 -->
<DIV align=center>
<SCRIPT language=JavaScript src="排序算法.files/in_footer.js"></SCRIPT>

<SCRIPT language=JavaScript id=scriptcount name="scriptcount"></SCRIPT>
</DIV><!--搜索：排序算法--></BODY></HTML>