C#归并排序的实现方法(递归,非递归,自然归并)

下面是关于C#归并排序的实现方法的完整攻略：

什么是归并排序？

归并排序是一种基于分治法的算法，具体实现方法是将原序列分成若干个子序列，分别进行排序，然后将排好序的子序列合并成一个大的有序序列。

递归实现归并排序

递归实现归并排序分为三步：

1. 分解数组：将要排序的数组从中间分成两个部分，即分为左右两个子数组。这里使用数组下标来实现。

2. 递归排序子数组：对分解出来的左右两个子数组分别调用递归函数，重复第1步和第2步。

3. 合并两个有序子数组：将两个排好序的子数组合并成一个有序的数组。

以下是递归实现归并排序的代码片段：

void MergeSort(int[] arr, int left, int right)
{
    if (left >= right)
        return;

    int mid = (left + right) / 2;
    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);
    Merge(arr, left, mid, right);
}

void Merge(int[] arr, int left, int mid, int right)
{
    int[] tmp = new int[right - left + 1];//辅助数组

    int i = left, j = mid + 1, k = 0;//i和j分别表示两个子数组的起始位置，k表示tmp的起始位置

    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }

    while (i <= mid)
        tmp[k++] = arr[i++];

    while (j <= right)
        tmp[k++] = arr[j++];

    for (int p = 0; p < tmp.Length; p++)
        arr[left + p] = tmp[p];//将排好序的辅助数组中的数据复制回原数组
}

非递归实现归并排序

非递归实现归并排序使用迭代的方式，将数组划分成多个小的块，然后将每个小块排序，随后在已排序的各个小块之间进行合并，直到整个数组有序。

以下是非递归实现归并排序的代码片段：

void MergeSort(int[] arr)
{
    int len = arr.Length;
    int blockSize = 1;//块大小

    while (blockSize < len)
    {
        int left = 0;
        while (left + blockSize < len)
        {
            Merge(arr, left, left + blockSize - 1, Math.Min(left + 2 * blockSize - 1, len - 1));
            left += 2 * blockSize;
        }
        blockSize *= 2;
    }
}

void Merge(int[] arr, int left, int mid, int right)
{
    int[] tmp = new int[right - left + 1];

    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }

    while (i <= mid)
        tmp[k++] = arr[i++];

    while (j <= right)
        tmp[k++] = arr[j++];

    for (int p = 0; p < tmp.Length; p++)
        arr[left + p] = tmp[p];
}

自然归并排序

自然归并排序是一种针对初始序列有序程度较高的序列排序算法。例如一段序列有两个、三个或多个有序片段时，只需对这些有序片段进行归并就能得到有序的最终序列。

以下是自然归并排序的代码片段：

void MergeSort(int[] arr)
{
    int len = arr.Length;
    int[] tmp = new int[len];

    while (true)
    {
        int i = 0;
        while (i < len - 1 && arr[i] <= arr[i + 1])
            i++;

        if (i == len - 1)//整个序列已有序，结束排序
            break;

        int left = i++;//left是分段的左端点
        while (i < len - 1 && arr[i] <= arr[i + 1])
            i++;

        int mid = i;//mid是分段的中间点
        i++;

        int right = i;//right是分段的右端点
        Merge(arr, tmp, left, mid, right);
    }
}

void Merge(int[] arr, int[] tmp, int left, int mid, int right)
{
    int i = left, j = mid, k = 0;

    while (i < mid && j < right)
    {
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }

    while (i < mid)
        tmp[k++] = arr[i++];

    while (j < right)
        tmp[k++] = arr[j++];

    for (int p = 0; p < k; p++)
        arr[left + p] = tmp[p];
}

示例说明

假设有一个数组arr，其中元素为{6, 1, 2, 3, 4, 5}，下面分别以递归、非递归和自然归并排序的方式将其排序。

递归实现

int[] arr = { 6, 1, 2, 3, 4, 5 };
MergeSort(arr, 0, arr.Length - 1);
Console.WriteLine(string.Join(" ", arr));

输出结果为：1 2 3 4 5 6

非递归实现

int[] arr = { 6, 1, 2, 3, 4, 5 };
MergeSort(arr);
Console.WriteLine(string.Join(" ", arr));

输出结果为：1 2 3 4 5 6

自然归并排序

int[] arr = { 6, 1, 2, 3, 4, 5 };
MergeSort(arr);
Console.WriteLine(string.Join(" ", arr));

输出结果为：1 2 3 4 5 6

以上就是关于C#归并排序的实现方法的完整攻略，希望对你有所帮助。