归并排序和堆排序_图文

1、归并排序(MergeSort和堆排序(HeapSort1 归并排序（MergeSort）归并排序最差运行时间是O(nlogn，它是利用递归设计程序的典型例子。归并排序的最基础的操作就是合并两个已经排好序的序列。假设我们有一个没有排好序的序列，那么首先我们使用分割的办法将这个序列分割成一个一个已经排好序的子序列。然后再利用归并的方法将一个个的子序列合并成排序好的序列。分割和归并的过程可以看下面的图例。从上图可以看出，我们首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列

2、。如何把两个已经排序好的子序列归并成一个排好序的序列呢？可以参看下面的方法。假设我们有两个已经排序好的子序列。序列A：1 23 34 65序列B：2 13 14 87那么可以按照下面的步骤将它们归并到一个序列中。（1）首先设定一个新的数列C8。（2）A0和B0比较，A0 = 1，B0 = 2，A0 B0，那么C1 = 2（4）A1和B1比较，A1 = 23，B1 = 13，A1 B1，那么C2 = 13（5）A1和B2比较，A1 = 23，B2 = 14，A1 B2，那么C3 = 14（6）A1和B3比较，A1 = 23，B3 = 87，A1 B3，那么C4 = 23（7）A2和B3比较，A2

3、 = 34，B3 = 87，A2 B3，那么C5 = 34（8）A3和B3比较，A3 = 65，B3 = 87，A3 leftmid=(right+left/2;MSort(temp,left,mid;/分割左边的序列MSort(temp,mid+1,right;/分割右边的序列Merge(temp,left,mid+1,right;/归并序列privatestaticvoidMerge(inttemp,intleft,intmid,intrightinti,left_end,num_elements,tmp_pos;left_end=mid-1;tmp_pos=left;num_elemen

4、ts=right-left+1;while(left=left_end&(mid=rightif(myArrayleft=myArraymid/将左端序列归并到temp数组中temptmp_pos=myArrayleft;tmp_pos=tmp_pos+1;left=left+1;else/将右端序列归并到temp数组中temptmp_pos=myArraymid;tmp_pos=tmp_pos+1;mid=mid+1;while(left=left_end/拷贝左边剩余的数据到temp数组中temptmp_pos=myArrayleft;left=left+1;tmp_pos=tmp_pos

5、+1;while(mid=right/拷贝右边剩余的数据到temp数组中temptmp_pos=myArraymid;mid=mid+1;tmp_pos=tmp_pos+1;for(i=0;i1arraySize-;Exchange(0,arraySize;/将最大值放在数组的最后DownHeap(0;/将序列从0到n-1看成一个新的序列，重新建立堆privatestaticvoidBuildHeap(for(intv=arraySize/2-1;v=0;v-DownHeap(v;/利用向下遍历子节点建立堆privatestaticvoidDownHeap(intvintw=2*v+1;/节点

6、w是节点v的第一个子节点while(warraySizeif(w+1myArrayww+;/将子节点w设置成节点v下面值最大的子节点/节点v已经大于子节点w，有了堆的性质，那么返回if(myArrayv=myArraywreturn;Exchange(v,w;/如果不是，就交换节点v和节点w的值v=w;w=2*v+1;/继续向下找子节点/交换数据privatestaticvoidExchange(inti,intjintt=myArrayi;myArrayi=myArrayj;myArrayj=t;堆排序主要用于超大规模的数据的排序。因为它不需要额外的存储空间，也不需要大量的递归。3 几种O(

7、nlogn算法的初步比较我们可以从下表看到几种O(nlogn算法的效率的区别。所有的数据都使用.Net的Random类产生，每种算法运行100次，时间的单位为毫秒。500随机整数5000随机整数20000随机整数合并排序0.31251.56257.03125Shell排序0.31251.256.875堆排序0.468752.18756.71875快速排序0.156250.6252.8125从上表可以明显地看出，快速排序是最快的算法。这也就给了我们一个结论，对于一般的应用来说，我们总是选择快速排序作为我们的排序算法，当数据量非常大（百万数量级）我们可以使用堆排序，如果内存空间非常紧张，我们可以使用Shell排序。但是这意味着我们不得不损失速度。 /*【Author】：flyingbread*【Date】：2007