排序算法.htm

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

            循环j不必到达7，只要到达4-1=3就可以了。按照这种思路，可以来回地进行扫描，即先从头扫到尾，再从尾扫到头。这样就得到双向冒泡排序算法： 
            <BR><BR>procedure Bi-Directional_Bubble_Sort(var L:List); <BR>var 
            <BR>low,up,t,i:position; <BR>begin <BR>1 low:=First(L);up:=Last(L); 
            <BR>2 while up&gt;low do <BR>begin <BR>3 t:=low; <BR>4 for i:=low to 
            up-1 do <BR>5 if L[i]&gt;L[i+1] then <BR>begin <BR>6 
            swap(L[i],L[i+1]); <BR>7 t:=i; <BR>end; <BR>8 up:=t; <BR>9 for i:=up 
            downto low+1 do <BR>10 if L[i]&lt; L[i-1] then <BR>begin <BR>11 
            swap(L[i],L[i-1]); <BR>12 t:=i; <BR>end; <BR>13 low:=t; <BR>end; 
            <BR>end; <BR>算法利用两个变量low和up记录排序的区域L[low..up]，用变量t 
            记录最近一次交换纪录的位置，4-7行从前向后扫描，9-12行从后向前扫描，每次扫描以后利用t所记录的最后一次交换记录的位置，并不断地缩小需要排序的区间，直到该区间只剩下一个元素。 
            <BR><BR>直观上来看，双向冒泡法先让重的气泡沉到底下，然后让轻的气泡浮上来，然后再让较大气泡沉下去，让较轻气泡浮上来，依次反复，直到排序结束。 
            <BR><BR>双向冒泡排序法的性能分析比较复杂，目前暂缺，那位朋友知道请告诉我。 
            <BR><BR>冒泡排序法和双向冒泡排序法是原地置换排序法，也是稳定排序法，如果算法Bubble_Sort中第3行的比较条件L[j]&gt;L[j+1]改为L[j]&gt;= 
            L[j+1]，则不再是稳定排序法。 <BR><BR>选择排序 Selection Sort 
            <BR>选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。 
            <BR><BR>选择排序算法可实现如下。 <BR><BR>procedure Selection_Sort(var L:List); 
            <BR>var <BR>i,j,s:position; <BR>begin <BR>1 for i:=First(L) to 
            Last(L)-1 do <BR>begin <BR>2 s:=i; <BR>3 for j:=i+1 to Last(L) do 
            <BR>4 if L[j]&lt; L[s] then <BR>5 s:=j; //记录L[i..n]中最小元素的位置 <BR>6 
            swap(L[i],L[s]); //交换L[i],L[s] <BR>end; <BR>end; 
            <BR>算法Selection_Sort中里面的一个for循环需要进行n-i次比较，所以整个算法需要 <BR><BR><BR>次比较。 
            <BR><BR>显而易见，算法Selection_Sort中共调用了n-1次swap过程。选择排序法是一个原地置换排序法，也是稳定排序法。 
            <BR><BR><BR>插入排序 Insertion Sort 
            <BR>插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ 
            L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] 
            ≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。 <BR><BR><BR>图1 
            对4个元素进行插入排序 
            <BR><BR>在下面的插入排序算法中，为了写程序方便我们可以引入一个哨兵元素L[0]，它小于L[1..n]中任一记录。所以，我们设元素的类型ElementType中有一个常量-∞，它比可能出现的任何记录都小。如果常量-∞不好事先确定，就必须在决定L[i]是否向前移动之前检查当前位置是否为1，若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时，就将L[i]放入L[0]中，这样也可以保证在适当的时候结束第i遍处理。下面的算法中将对当前位置进行判断。 
            <BR><BR>插入排序算法如下： <BR><BR>procedure Selection_Sort(var L:List); 
            <BR>var <BR>i,j:position; <BR>v:ElementType; <BR>begin <BR>1 for 
            i:=First(L)+1 to Last(L) do <BR>begin <BR>2 v:=L[i]; <BR>3 j:=i; 
            <BR>4 while (j&lt;&gt;First(L))and(L[j-1]&lt; v) do //循环找到插入点 
            <BR>begin <BR>5 L[j]:=L[j-1]; //移动元素 <BR>6 j:=j-1; <BR>end; <BR>7 
            L[j]:=v; //插入元素 <BR>end; <BR>end; 
            <BR>下面考虑算法Insertion_Sort的复杂性。对于确定的i，内while循环的次数为O(i)，所以整个循环体内执行了∑O(i)=O(∑i)，其中i从2到n。即比较次数为O(n2)。如果输入序列是从大到小排列的，那么内while循环次数为i-1次，所以整个循环体执行了∑(i-1)=n(n-1)/2次。由此可知，最坏情况下，Insertion_Sort要比较Ω(n2)次。 
            <BR><BR>如果元素类型是一个很大的纪录，则算法第5行要消耗大量的时间，因此有必要分析移动元素的次数。经过分析可知，平均情况下第5行要执行n(n-1)/4次，分析方法与冒泡排序的分析相同。 
            <BR><BR>如果移动元素要消耗大量的时间，则可以用链表来实现线性表，这样Insertion_Sort可以改写如下(当然前一个算法同样也适用于链表，只不过没下面这个好，但是下面算法这个比较复杂)： 
            <BR><BR>注意：在下面的算法中链表L增加了一个哨兵单元，其中的元素为-∞，即线性表L的第一个元素是L^.next^ 
            <BR><BR>procedure Selection_Sort_II(var L:PList); <BR>var 
            <BR>i,j,tmp:Position; <BR>begin <BR>1 if L^.next=nil then exit; 
            //如果链表L为空则直接退出 <BR>2 i:=L^.next; 
            //i指向L的第一个元素，注意，L有一个哨兵元素，因此L^.next^才是L的第一个元素 <BR>3 while 
            i^.next&lt;&gt;nil do <BR>begin <BR>4 tmp:=i^.next; 
            //tmp指向L[i]的下一个位置 <BR>5 j:=L; <BR>6 while 
            (j&lt;&gt;i)and(tmp^.data&gt;=j^.next^.data) do 
            //从前向后找到tmp的位置，tmp应该插在j后面 <BR>7 j:=j^.next; <BR>8 if j&lt;&gt;i then 
            //j=i说明不需要改变tmp的位置 <BR>begin <BR>9 i^.next:=tmp^.next; //将tmp从i后面摘除 
            <BR>10 tmp^.next:=j^.next; //在j后面插入tmp <BR>11 j^.next:=tmp; <BR>end 
            <BR>12 else i:=i^.next; //否则i指向下一个元素 <BR>end; <BR>end; 
            <BR>上述改进算法主要是利用链表删除和插入元素方便的特性，对于数组则不适用。 
            <BR><BR>插入排序法是一个原地置换排序法，也是一个稳定排序法。插入法虽然在最坏情况下复杂性为θ(n2)，但是对于小规模输入来说，插入排序法是一个快速的原地置换排序法。许多复杂的排序法，在规模较小的情况下，都使用插入排序法来进行排序，比如快速排序和桶排序。 
            <BR><BR>下面是一个Java Applet制作的插入排序演示程序。 <BR><BR><BR><BR>快速排序 Quick Sort 
            <BR><BR>我们已经知道，在决策树计算模型下，任何一个基于比较来确定两个元素相对位置的排序算法需要Ω(nlogn)计算时间。如果我们能设计一个需要O(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。 
            <BR><BR>下面介绍快速排序算法，它在平均情况下需要O(nlogn)时间。这个算法是由C.A.R.Hoare发明的。 
            <BR><BR>算法的基本思想 
            <BR><BR>快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理： 
            <BR><BR>分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。 
            <BR>递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。 
            <BR>合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。 
            <BR>这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。 <BR><BR>算法的实现 
            <BR><BR>算法Quick_Sort的实现： 
            <BR><BR>注意：下面的记号L[p..r]代表线性表L从位置p到位置r的元素的集合，但是L并不一定要用数组来实现，可以是用任何一种实现方法（比如说链表），这里L[p..r]只是一种记号。 
            <BR><BR>procedure Quick_Sort(p,r:position;var L:List); <BR><BR>const 
            <BR><BR>e=12; <BR><BR>var <BR><BR>q:position; <BR><BR>begin 
            <BR><BR>1 if r-p&lt;=e then 
            Insertion_Sort(L,p,r)//若L[p..r]足够小则直接对L[p..r]进行插入排序 <BR><BR>else 
            begin <BR><BR>2 
            q:=partition(p,r,L);//将L[p..r]分解为L[p..q]和L[q+1..r]两部分 <BR><BR>3 
            Quick_Sort(p,q,L); //递归排序L[p..q] <BR><BR>4 
            Quick_Sort(q+1,r,L);//递归排序L[q+1..r] <BR><BR>end; <BR><BR>end; 
            <BR><BR>对线性表L[1..n]进行排序，只要调用Quick_Sort(1,n,L)就可以了。算法首先判断L[p..r]是否足够小，若足够小则直接对L[p..r]进行排序，Sort可以是任何一种简单的排序法，一般用插入排序。这是因为，对于较小的表，快速排序中划分和递归的开销使得该算法的效率还不如其它的直接排序法好。至于规模多小才算足够小，并没有一定的标准，因为这跟生成的代码和执行代码的计算机有关，可以采取试验的方法确定这个规模阈值。经验表明，在大多数计算机上，取这个阈值为12较好，也就是说，当r-p&lt;=e=12即L[p..r]的规模不大于12时，直接采用插入排序法对L[p..r]进行排序(参见 
            Sorting and Searching Algorithms: A 
            Cookbook)。当然，比较方便的方法是取该阈值为1，当待排序的表只有一个元素时，根本不用排序(其实还剩两个元素时就已经在Partition函数中排好序了)，只要把第1行的if语句该为if 
            p=r then exit else ...。这就是通常教科书上看到的快速排序的形式。 
            <BR><BR>注意：算法Quick_Sort中变量q的值一定不能等于r，否则该过程会无限递归下去，永远不能结束。因此下文中在partition函数里加了限制条件，避免q=r情况的出现。 
            <BR><BR>算法Quick_Sort中调用了一个函数partition，该函数主要实现以下两个功能： <BR><BR>1. 
            在L[p..r]中选择一个支点元素pivot; <BR><BR>2. 
            对L[p..r]中的元素进行整理，使得L[p..q]分为两部分L[p..q]和L[q+1..r]，并且L[p..q]中的每一个元素的值不大于pivot，L[q+1..r]中的每一个元素的值不小于pivot，但是L[p..q]和L[q+1..r]中的元素并不要求排好序。 
            <BR><BR>快速排序法改进性能的关键就在于上述的第二个功能，因为该功能并不要求L[p..q]和L[q+1..r]中的元素排好序。 
            <BR><BR>函数partition可以实现如下。以下的实现方法是原地置换的，当然也有不是原地置换的方法，实现起来较为简单，这里就不介绍了。 
            <BR><BR>function partition(p,r:position;var L:List):position; 
            <BR><BR>var <BR><BR>pivot:ElementType; <BR><BR>i,j:position; 
            <BR><BR>begin <BR><BR>1 pivot:=Select_Pivot(p,r,L); 
            //在L[p..r]中选择一个支点元素pivot <BR><BR>2 i:=p-1; <BR><BR>3 j:=r+1; 
            <BR><BR>4 while true do <BR><BR>begin <BR><BR>5 repeat j:=j-1 until 
            L[j]&lt;=pivot; //移动左指针，注意这里不能用while循环 <BR><BR>6 repeat i:=i+1 until 
            L[i]&gt;=pivot; //移动右指针，注意这里不能用while循环 <BR><BR>7 if i&lt; j then 
            swap(L[i],L[j]) //交换L[i]和L[j] <BR><BR>8 else if j&lt;&gt;r then 
            return j //返回j的值作为分割点 <BR><BR>9 else return j-1; //返回j前一个位置作为分割点 
            <BR><BR>end; <BR><BR>end; 
            <BR><BR>该算法的实现很精巧。其中，有一些细节需要注意。例如，算法中的位置i和j不会超出A[p..r]的位置界，并且该算法的循环不会出现死循环，如果将两个repeat语句换为while则要注意当L[i]=L[j]=pivot且i&lt;j时i和j的值都不再变化，会出现死循环。 
            <BR><BR>另外，最后一个if..then..语句很重要，因为如果pivot取的不好，使得Partition结束时j正好等于r，则如前所述，算法Quick_Sort会无限递归下去；因此必须判断j是否等于r，若j=r则返回j的前驱。 
            <BR><BR>以上算法的一个执行实例如图1所示，其中pivot=L[p]=5： <BR><BR><BR>图1 
            Partition过程的一个执行实例