合并排序:歸并排序 - elvinle－IT工程師數位筆記本

文章出處

一、歸并排序

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合并之后, 他們肯定就是一個有序集合了吧.

這里就是一個集合拆分成原子, 再將原子兩兩合并,再合并,再合并......的過程

過程好像不復雜, 不知道實現起來怎么樣.

///<summary>
/// 數組的劃分
///</summary>
///<param name="array">待排序數組</param>
///<param name="temparray">臨時存放數組</param>
///<param name="left">序列段的開始位置，</param>
///<param name="right">序列段的結束位置</param>
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);
    }
}

///<summary>
/// 數組的兩兩合并操作
///</summary>
///<param name="array">待排序數組</param>
///<param name="temparray">臨時數組</param>
///<param name="left">第一個區間段開始位置</param>
///<param name="middle">第二個區間的開始位置</param>
///<param name="right">第二個區間段結束位置</param>
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<int> list = new List<int>();
        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()));
    }
}