一、归并排序

1. 思想

如果有两个集合, listA={2,4,6,8}, listB={1,3,5,7}.

现在要将这两个数组合并成listC, 且必须保证listC中的数是有序的, 该咋弄呢?

第一步. 使listA, listB都变成有序的集合. 然后再合并的时候, 才会变得更好处理.

第二步. 合并. 只用比较listA, listB最左侧的数, 谁小就先放谁进listC, 放完之后, 还得把listA,listB中的对应的数删除掉.

循环执行第二步, 知道listA,listB中都不再有数据位置, listC就合并成功了.

这种方式, 是不是也挺好理解的? 而且, 速度应该不会慢哦.

但是, 这里还牵涉到一个问题, 就是对listA,listB集合的排序问题, 该怎么搞? 先对两个集合排序, 有没有搞错, 这不是搞了三个排序了?

listA,listB集合的排序, 我是用什么方式好? 快速排序? 真是麻烦事啊.

我不想对listA, listB再进行排序了, 太麻烦了, 我是来追求排序速度的, 不是来自找麻烦的. 

那如果listA, listB中, 都只有一个数, 他们是不是就不需要排序了呢? 当listA, listB合并之后, 他们肯定就是一个有序集合了吧. 

这里就是一个集合拆分成原子, 再将原子两两合并,再合并,再合并......的过程

     

 过程好像不复杂, 不知道实现起来怎么样.

///
/// 数组的划分///
///待排序数组///临时存放数组///序列段的开始位置，///序列段的结束位置static void MergeSort(int[] array, int[] temparray, int left, int right){    if (left < right)    {        //取分割位置        int middle = (left + right) / 2;        //递归划分数组左序列        MergeSort(array, temparray, left, middle);        //递归划分数组右序列        MergeSort(array, temparray, middle + 1, right);        //数组合并操作        Merge(array, temparray, left, middle + 1, right);    }}///
/// 数组的两两合并操作///
///待排序数组///临时数组///第一个区间段开始位置///第二个区间的开始位置///第二个区间段结束位置static void Merge(int[] array, int[] temparray, int left, int middle, int right){    //左指针尾    int leftEnd = middle - 1;    //右指针头    int rightStart = middle;    //临时数组的下标    int tempIndex = left;    //数组合并后的length长度    int tempLength = right - left + 1;    //先循环两个区间段都没有结束的情况    while ((left <= leftEnd) && (rightStart <= right))    {        //将两个区间数组中比较小的值存入临时数组, 一直到有一方数组结束        if (array[left] < array[rightStart])            temparray[tempIndex++] = array[left++];        else            temparray[tempIndex++] = array[rightStart++];    }    //判断左序列是否结束, 将没有结束的数据全部放入临时数组中    while (left <= leftEnd)        temparray[tempIndex++] = array[left++];    //判断右序列是否结束, 将没有结束的数据全部放入临时数组中    while (rightStart <= right)        temparray[tempIndex++] = array[rightStart++];    //将临时数组中的数据覆盖回去    for (int i = 0; i < tempLength; i++)    {        array[right] = temparray[right];        right--;    }}

 

二、快速排序 vs 归并排序 

static void Test(){    //五次比较    for (int i = 1; i <= 5; i++)    {        List
     
       list = new List
      
       ();        int[] listA = new int[10000];        //插入2k个随机数到数组中        for (int j = 0; j < 10000; j++)        {            Thread.Sleep(1);            list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 100000));        }        listA = list.ToArray();        Console.WriteLine("\n第" + i + "次比较：{0}...", string.Join(",", list.Take(10)));        Stopwatch watch = new Stopwatch();        watch.Start();        var res = list.OrderBy(n => n).ToList();        watch.Stop();        Console.WriteLine("\n快速排序耗费时间：" + watch.ElapsedMilliseconds);        Console.WriteLine("输出前是十个数:" + string.Join(",", res.Take(10).ToList()));        watch.Restart();        MergeSort(listA, new int[10000], 0, listA.Length - 1);        watch.Stop();        Console.WriteLine("\n归并排序耗费时间：" + watch.ElapsedMilliseconds);        Console.WriteLine("输出前是十个数:" + string.Join(",", listA.Take(10).ToList()));    }}
      
     

 

从这里看归并排序还是很快的.

归并排序的时间复杂度都是O(nlog₂n), 很稳定

 

 参考: