数据结构与算法-算法篇：排序—归并排序（五）

数据结构与算法系列文章：数据结构与算法目录

归并字面上的意思是合并，归并算法的核心思想是分治法，就是将一个数组一刀切两半，递归切，直到切成单个元素，然后重新组装合并，单个元素合并成小数组，两个小数组合并成大数组，直到最终合并完成，排序完毕。

归并排序的核心思想是分治，分而治之，将一个大问题分解成无数的小问题进行处理，处理之后再合并，采用递归来实现：

实现：

/// <summary>
/// 归并排序
/// </summary>
/// <param name="arr"></param>
public void MergeSort(int[] arr)
{
    if (arr == null || arr.Length < 2)
    {
        return;
    }

    int[] tempArr = new int[arr.Length];
    Sort(arr, tempArr, 0, arr.Length - 1);
}

/// <summary>
/// 递归排序
/// </summary>
/// <param name="arr">排序数组</param>
/// <param name="tempArr">临时存储数组</param>
/// <param name="startIndex">排序起始位置</param>
/// <param name="endIndex">排序终止位置</param>
private void Sort(int[] arr, int[] tempArr, int startIndex, int endIndex)
{
    if (endIndex <= startIndex)
    {
        // 排序完毕
        return;
    }

    // 中部下标
    int middleIndex = startIndex + (endIndex - startIndex) / 2;

    // 分解左半边
    Sort(arr, tempArr, startIndex, middleIndex);
    // 分解右半边
    Sort(arr, tempArr, middleIndex + 1, endIndex);

    Merage(arr, tempArr, startIndex, middleIndex, endIndex);
}

/// <summary>
/// 归并
/// </summary>
/// <param name="arr">排序数组</param>
/// <param name="tempArr">临时存储数组</param>
/// <param name="startIndex">归并起始位置</param>
/// <param name="middleIndex">归并中间位置</param>
/// <param name="endIndex">归并停止位置</param>
private void Merage(int[] arr, int[] tempArr, int startIndex, int middleIndex, int endIndex)
{
    for (int i = startIndex; i <= endIndex; i++)
    {
        tempArr[i] = arr[i];
    }

    // 左边首位下标
    int left = startIndex;
    // 右边首位下标
    int right = middleIndex + 1;

    // 合并 (startIndex, middleIndex - 1) 和 (middleIndex, endIndex)两个数组
    for (int i = startIndex; i <= endIndex; i++)
    {
        if (left > middleIndex)
        {
            // 如果左边首位下标大于中部下标，证明左边的数据已经排完了
            arr[i] = tempArr[right];
            right++;
        }
        else if (right > endIndex)
        {
            // 如果右边的首位下标大于数组长度，证明右边的数据已经排完了
            arr[i] = tempArr[left];
            left++;
        }
        else if (tempArr[right] < tempArr[left])
        {
            // 将右边的首位排入，然后右边的下标+1
            arr[i] = tempArr[right];
            right++;
        }
        else
        {
            // 将左边的首位排入，然后左边的下标+1
            arr[i] = tempArr[left];
            left++;
        }
    }
}