Feeling

    三人行,必有我师焉

   ::  :: 新随笔 :: 联系 ::  :: 管理 ::
  185 随笔 :: 0 文章 :: 392 评论 :: 0 Trackbacks

1 归并排序(MergeSort)

归并排序最差运行时间是O(nlogn),它是利用递归设计程序的典型例子。

归并排序的最基础的操作就是合并两个已经排好序的序列。

假设我们有一个没有排好序的序列,那么首先我们使用分割的办法将这个序列分割成一个一个已经排好序的子序列。然后再利用归并的方法将一个个的子序列合并成排序好的序列。分割和归并的过程可以看下面的图例。



从上图可以看出,我们首先把一个未排序的序列从中间分割成2部分,再把2部分分成4部分,依次分割下去,直到分割成一个一个的数据,再把这些数据两两归并到一起,使之有序,不停的归并,最后成为一个排好序的序列。

如何把两个已经排序好的子序列归并成一个排好序的序列呢?可以参看下面的方法。

假设我们有两个已经排序好的子序列。
序列A:1 23 34 65
序列B:2 13 14 87
那么可以按照下面的步骤将它们归并到一个序列中。

(1)首先设定一个新的数列C[8]。
(2)A[0]和B[0]比较,A[0] = 1,B[0] = 2,A[0] < B[0],那么C[0] = 1
(3)A[1]和B[0]比较,A[1] = 23,B[0] = 2,A[1] > B[0],那么C[1] = 2
(4)A[1]和B[1]比较,A[1] = 23,B[1] = 13,A[1] > B[1],那么C[2] = 13
(5)A[1]和B[2]比较,A[1] = 23,B[2] = 14,A[1] > B[2],那么C[3] = 14
(6)A[1]和B[3]比较,A[1] = 23,B[3] = 87,A[1] < B[3],那么C[4] = 23
(7)A[2]和B[3]比较,A[2] = 34,B[3] = 87,A[2] < B[3],那么C[5] = 34
(8)A[3]和B[3]比较,A[3] = 65,B[3] = 87,A[3] < B[3],那么C[6] = 65
(9)最后将B[3]复制到C中,那么C[7] = 87。归并完成。

如果我们清楚了上面的分割和归并过程,那么我们就可以用递归的方法得到归并算法的实现。

    public class MergeSorter
    {
        
private static int[] myArray;
        
private static int arraySize;

        
public static void Sort( int[] a )
        {
            myArray 
= a;
            arraySize 
= myArray.Length;
            MergeSort();
        }

        
/// <summary>
        
/// 利用归并的方法排序数组,首先将序列分割
        
/// 然后将数列归并,这个算法需要双倍的存储空间
        
/// 时间是O(nlgn)
        
/// </summary>
        private static void MergeSort()
        {
            
int[] temp = new int[arraySize];
            MSort( temp, 
0, arraySize - 1);
        }

        
private static void MSort(int[] temp, int left, int right)
        {
            
int mid;

            
if (right > left)
            {
                mid 
= (right + left) / 2;
                MSort( temp, left, mid); 
//分割左边的序列
                MSort(temp, mid+1, right);//分割右边的序列
                Merge(temp, left, mid+1, right);//归并序列
            }
        }

        
private static void Merge( int[] temp, int left, int mid, int right)
        {
            
int i, left_end, num_elements, tmp_pos;

            left_end 
= mid - 1;
            tmp_pos 
= left;
            num_elements 
= right - left + 1;

            
while ((left <= left_end) && (mid <= right)) 
            {
                
if (myArray[left] <= myArray[mid]) //将左端序列归并到temp数组中
                {
                    temp[tmp_pos] 
= myArray[left];
                    tmp_pos 
= tmp_pos + 1;
                    left 
= left +1;
                }
                
else//将右端序列归并到temp数组中
                {
                    temp[tmp_pos] 
= myArray[mid];
                    tmp_pos 
= tmp_pos + 1;
                    mid 
= mid + 1;
                }
            }

            
while (left <= left_end) //拷贝左边剩余的数据到temp数组中
            {
                temp[tmp_pos] 
= myArray[left];
                left 
= left + 1;
                tmp_pos 
= tmp_pos + 1;
            }
            
while (mid <= right) //拷贝右边剩余的数据到temp数组中
            {
                temp[tmp_pos] 
= myArray[mid];
                mid 
= mid + 1;
                tmp_pos 
= tmp_pos + 1;
            }

            
for (i=0; i < num_elements; i++//将所有元素拷贝到原始数组中
            {
                myArray[right] 
= temp[right];
                right 
= right - 1;
            }
        }
    }


归并排序算法是一种O(nlogn)的算法。它的最差,平均,最好时间都是O(nlogn)。但是它需要额外的存储空间,这在某些内存紧张的机器上会受到限制。

归并算法是又分割和归并两部分组成的。对于分割部分,如果我们使用二分查找的话,时间是O(logn),在最后归并的时候,时间是O(n),所以总的时间是O(nlogn)。

2 堆排序(HeapSort)

堆排序属于百万俱乐部的成员。它特别适合超大数据量(百万条记录以上)的排序。因为它并不使用递归(因为超大数据量的递归可能会导致堆栈溢出),而且它的时间也是O(nlogn)。还有它并不需要大量的额外存储空间。

堆排序的思路是:

(1)将原始未排序的数据建成一个堆。
(2)建成堆以后,最大值在堆顶,也就是第0个元素,这时候将第零个元素和最后一个元素交换。
(3)这时候将从0到倒数第二个元素的所有数据当成一个新的序列,建一个新的堆,再次交换第一个和最后一个元素,依次类推,就可以将所有元素排序完毕。

建立堆的过程如下面的图所示:


堆排序的具体算法如下:

public class HeapSorter 
    {
        
private static int[] myArray;
        
private static int arraySize;

        
public static void Sort( int[] a )
        {
            myArray 
= a;
            arraySize 
= myArray.Length;
            HeapSort();
        }

        
private static void HeapSort()
        {
            BuildHeap();            
//将原始序列建成一个堆

            
while ( arraySize > 1 )
            {
                arraySize
--;
                Exchange ( 
0, arraySize );//将最大值放在数组的最后
                DownHeap ( 0 );  //将序列从0到n-1看成一个新的序列,重新建立堆
            } 
        }

        
private static void BuildHeap()
        {
            
for (int v=arraySize/2-1; v>=0; v--)
                DownHeap ( v );
        }

        
//利用向下遍历子节点建立堆
        private static void DownHeap( int v )
        {
            
int w = 2 * v + 1;                     // 节点w是节点v的第一个子节点

            
while (w < arraySize)
            {
                
if ( w+1 < arraySize )        // 如果节点v下面有第二个字节点
                    if ( myArray[w+1> myArray[w] ) 
                        w
++;                        // 将子节点w设置成节点v下面值最大的子节点

                 
// 节点v已经大于子节点w,有了堆的性质,那么返回
                if ( myArray[v] >= myArray[w] ) 
                    
return;   
                
                Exchange( v, w );     
// 如果不是,就交换节点v和节点w的值
                v = w;        
                w 
= 2 * v + 1;            // 继续向下找子节点
            }
        }

        
//交换数据
        private static void Exchange( int i, int j )
        {
            
int t = myArray[i];
            myArray[i] 
= myArray[j];
            myArray[j] 
= t;
        }
    }    


 

堆排序主要用于超大规模的数据的排序。因为它不需要额外的存储空间,也不需要大量的递归。

3 几种O(nlogn)算法的初步比较

我们可以从下表看到几种O(nlogn)算法的效率的区别。所有的数据都使用.Net的Random类产生,每种算法运行100次,时间的单位为毫秒。


500随机整数5000随机整数20000随机整数
合并排序0.31251.56257.03125
 Shell排序0.31251.256.875
堆排序0.468752.18756.71875
快速排序0.156250.6252.8125

从上表可以明显地看出,快速排序是最快的算法。这也就给了我们一个结论,对于一般的应用来说,我们总是选择快速排序作为我们的排序算法,当数据量非常大(百万数量级)我们可以使用堆排序,如果内存空间非常紧张,我们可以使用Shell排序。但是这意味着我们不得不损失速度。 

/******************************************************************************************
 *【Author】:flyingbread
 *【Date】:2007年2月2日
 *【Notice】:
 *1、本文为原创技术文章,首发博客园个人站点(http://flyingbread.cnblogs.com/),转载和引用请注明作者及出处。
 *2、本文必须全文转载和引用,任何组织和个人未授权不能修改任何内容,并且未授权不可用于商业。
 *3、本声明为文章一部分,转载和引用必须包括在原文中。
 ******************************************************************************************/
posted on 2012-11-10 23:18 三人行,必有我师焉 阅读(536) 评论(2)  编辑  收藏

评论

# re: 排序1+4:归并排序(MergeSort)和堆排序(HeapSort)(转) 2012-11-11 01:52 三人行,必有我师焉
堆排序,首先建立一个大顶堆,从最底层的叶子节点开始建(数组尾端),首先最底层的叶子右节点和左节点比较,取出较大的那个叶子节点,让这个节点和父亲比较,如果大于父亲,则和父亲交换。底层叶子遍历比较完之后,父节点遍历比较,直到根节点(数组头)。

建立完大顶堆之后,开始遍历,因为最大的节点就是根节点,直接把根节点和最底层叶子交换,然后重新构建大顶堆,这个大顶堆已经是有序的了(不包括已交换的部分),除了根节点外,其他部分都是大顶堆构造,此时先让根节点的左孩子和右孩子比较,大的那个孩子和父节点交换,交换后继续递归比较,看看被交换的根节点交换后还是小于子节点,如果还是小,则继续交换,直到大于子节点为止。那么剩下的堆就又是个大顶堆了,然后循环构建n-1次即可。  回复  更多评论
  

# re: 排序1+4:归并排序(MergeSort)和堆排序(HeapSort)(转) 2012-11-12 01:16 三人行,必有我师焉
原地快速排序,把数组需要需要排序的部分分成左边和右边两部分,但是如何让数组分成左边和右边两块呢?
1.以数组最右端的元素作为分割点
2.做一个标记符,标记已经放了几个元素到左边了
3.开始遍历数组每个元素,碰到小于分割点的元素,就和第(标记符+1)个元素交换,然后标记符增加1。
4.将分割点和第(标记符+1)个元素交换,这是第(标记符+1)个元素左边的元素都小于分割点,右边的元素都大于或等于分割点元素。
5.递归排序分割点左边的部分和右边的部分,直到子数组的左边部分索引和右边部分索引相等,也就是长度为1为止。  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航:
 
GitHub |  开源中国社区 |  maven仓库 |  文件格式转换