二路归并排序

作者：追风剑情发布于：2014-10-31 22:11 分类：Algorithms

时间复杂度为, 且是稳定的。

开发工具 Visual Studio

开发语言 C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MergeSortTest
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] R = new int[] { 75, 87, 68, 92, 88, 61, 77, 96, 80, 72 };
            Console.Write("排序前:");
            Printf(R);

            MergeSort(R);

            Console.WriteLine();
            Console.Write("排序后:");
            Printf(R);

            Console.Read();
        }

        static void Printf(int[] R)
        {
            for (int i = 0; i < R.Length; i++)
                Console.Write(R[i]+" ");
        }

        //一次归并，将两个有序表归并为一个有序表
        static void Merge(int[] R, int low, int mid, int high)
        {
            int[] R1 = new int[R.Length];
            int i = low, j = mid + 1, k = 0;
            while(i<=mid && j<=high){
                if(R[i] <= R[j]){
                    R1[k] = R[i];
                    i++; k++;
                }else{
                    R1[k] = R[j];
                    j++; k++;
                }
            }

            while(i<=mid){
                R1[k] = R[i];
                i++; k++;
            }

            while (j <= high)
            {
                R1[k] = R[j];
                j++; k++;
            }

            for (k = 0, i = low; i <= high; k++, i++)
                R[i] = R1[k];
        }

        //一趟归并
        static void MergePass(int[] R, int length)
        {
            int n = R.Length;
            int i;
            //归并length长的两个相邻子表
            for (i = 0; i + 2 * length - 1 < n; i = i + 2 * length)
                Merge(R, i, i+length-1, n-1);

            //余下两个子表，后者长度小于length
            if (i + length - 1 < n)
                Merge(R, i, i+length-1, n-1);//归并这两个子表
        }

        //二路归并排序
        static void MergeSort(int[] R)
        {
            int n = R.Length;
            int length;
            for (length = 1; length < n; length = 2 * length)
                MergePass(R, length);
        }
    }
}

运行结果