一天一个小算法的学习之归并排序

 

　　回归正题~在经过许多大神的指导下,与自己的笔记小本本的乱涂乱改下,算是弄懂了归并排序其中的原理..网上有很多大神的教学,要比我写的详细很多

http://blog.163.com/pinbo_jiankun/blog/static/133546488201391831822169/  这个链接,是我学习这位大神的一些思路和写法..供自己与大家共同参考..

　　首先:

　　归并排序,是将两个,或者两个以上的列表(数组)合并成一个新的有序的列表(注意是有序的)..并把等待排序的序列分成多个子序列,并且,每个子序列都是

有序的,然后,再把他们合并成一个整体的有序序列..

　　话不多说上代码:

主函数调用:

using System;
using System.Collections.Generic;

namespace SortPra
{
    class MainClass
    {

        public static void Main (string[] args)
        {
            int[] arrInt = new int[]{ 5, 7, 6, 9, 7, 8, 9, 19, 11 };

            MergeSorter.MergeWithSort (arrInt);
            for (int i = 0; i < arrInt.Length; i++) {
                Console.WriteLine ("归并排序:" + arrInt [i]);
            }
        }
    }
}

 

归并类代码:

using System;
using System.Text;

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

namespace SortPra
{
    public class MergeSorter
    {
        public MergeSorter ()
        {
        }

        public static int[] MergeWithSort (int[] arr)
        {
            if (null == arr || arr.Length <= 1) {
                return arr;
            }
            //取数组下标  科普: >> 右位移运算 相当于除以2, << 左移位运算符号, 相当于乘以2...
            int mid = arr.Length >> 1;
            //初始化两个临时数组,并定义一个最终结果,如果数组为奇数个,把多余的元素空间预留在right的临时数组中
            int[] left = new int[mid];
            int[] right = new int[arr.Length - mid];
            int[] result = new int[arr.Length];
            //假设数组长度为8,那么mid为4,当i<4时,将代入数组的第一个元素赋值给Left..实行分割,一直到分成两个元素为止
            for (int i = 0; i < arr.Length; i++) {
                if (i < mid) {
                    left [i] = arr [i];
                } else {
                    right [i - mid] = arr [i];
                }
            }
            //将左侧的数组再次带入到该方法,直到分成数组长度为2为止
            left = MergeWithSort (left);
            //同理:将右侧的数组再次带入到该方法,直到分成数组长度为2为止
            right = MergeWithSort (right);
            //将结果进行归并
            result = Merge (left, right);

            return result;
        }

        public static int[] Merge (int[]left, int[]right)
        {
            int[] result = new int[left.Length + right.Length];
            int j = 0, i = 0, k = 0;
            while (i < left.Length && j < right.Length) {
                //当左侧的第一个元素小于右侧的第一个元素,也就是进行比对,小于了,左侧的元素就放在前面,大于了右侧的就放前面
                if (left [i] < right [j]) {
                    //a[i++]相当于a[i];i=i+1;
                    result [k++] = left [i++];
                } else {
                    result [k++] = right [i++];
                }
            }
            //一旦 i,j 大于本数组长度,就不执行
            while (i < left.Length) {
                result [k++] = left [i++];
            }
            while (j < right.Length) {
                result [k++] = right [j++];
            }
            return result;
        }
    }
}