C#实现归并排序

下面是“C#实现归并排序”的完整攻略。

什么是归并排序

归并排序是一种基于“分治”思想的排序算法。该算法将待排数组递归地分成两部分，分别进行排序，最后合并成有序序列。

归并排序的步骤

1. 拆分：将待排数组递归地拆分成左右两个子数组，直到每个子数组只有一个元素。
2. 排序：将左右子数组分别进行排序，排序完成后合并。
3. 合并：合并左右两个有序子数组为一个有序数组。

C#实现归并排序代码

下面是C#实现归并排序的代码：

public static void MergeSort(int[] input)
{
    if (input == null || input.Length <= 1)
    {
        return;
    }

    MergeSort(input, 0, input.Length - 1);
}

private static void MergeSort(int[] input, int start, int end)
{
    if (start >= end)
    {
        return;
    }

    int mid = start + (end - start) / 2;

    MergeSort(input, start, mid);
    MergeSort(input, mid + 1, end);

    Merge(input, start, mid, end);
}

private static void Merge(int[] input, int start, int mid, int end)
{
    int[] temp = new int[end - start + 1];
    int i = start, j = mid + 1, k = 0;

    while (i <= mid && j <= end)
    {
        if (input[i] <= input[j])
        {
            temp[k++] = input[i++];
        }
        else
        {
            temp[k++] = input[j++];
        }
    }

    while (i <= mid)
    {
        temp[k++] = input[i++];
    }

    while (j <= end)
    {
        temp[k++] = input[j++];
    }

    for (int m = 0; m < temp.Length; m++)
    {
        input[start + m] = temp[m];
    }
}

示例演示

下面给出两个示例，分别对待排数组{5, 4, 3, 2, 1}和{1, 4, 5, 3, 2}进行归并排序。

示例一：{5, 4, 3, 2, 1}

1. 第一次拆分：{5, 4, 3, 2, 1} -> {5, 4, 3}、{2, 1}
   {5, 4, 3} -> {5}、{4, 3}
   {4, 3} -> {4}、{3}
   {2, 1} -> {2}、{1}
2. 第一次排序：{5}、{4, 3}、{2}、{1} -> {4, 5, 3}、{1, 2}
3. 第一次合并：{4, 5, 3}、{1, 2} -> {1, 2, 4, 5, 3}
4. 第二次拆分：{1, 2, 4, 5, 3} -> {1, 2}、{4, 5, 3}
   {4, 5, 3} -> {4}、{5, 3}
   {5, 3} -> {5}、{3}
5. 第二次排序：{1, 2}、{4}、{5}、{3} -> {1, 2, 4}、{3, 5}
6. 第二次合并：{1, 2, 4}、{3, 5} -> {1, 2, 3, 4, 5}

示例二：{1, 4, 5, 3, 2}

1. 第一次拆分：{1, 4, 5, 3, 2} -> {1, 4, 5}、{3, 2}
   {1, 4, 5} -> {1}、{4, 5}
   {4, 5} -> {4}、{5}
   {3, 2} -> {3}、{2}
2. 第一次排序：{1}、{4}、{5}、{3}、{2} -> {1, 4}、{3, 5}、{2}
3. 第一次合并：{1, 4}、{3, 5}、{2} -> {1, 3, 4, 5}、{2}
4. 第二次拆分：{1, 3, 4, 5}、{2} -> {1, 3}、{4, 5}、{2}
   {4, 5} -> {4}、{5}
5. 第二次排序：{1, 3}、{4}、{5}、{2} -> {1, 2, 3}、{4, 5}
6. 第二次合并：{1, 2, 3}、{4, 5} -> {1, 2, 3, 4, 5}

以上就是“C#实现归并排序”的完整攻略。