归并排序 和 堆排序(C++实现)【转】

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();
        }

        /// 

        /// 利用归并的方法排序数组，首先将序列分割
        /// 然后将数列归并，这个算法需要双倍的存储空间
        /// 时间是O(nlgn)
        /// 

        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 <=

阅读(1038) | 评论(1) | 转发(0) |

0

上一篇：排序算法 小结【转】

下一篇：常见查找排序算法实现（C语言）