6.归并排序

算法 > 排序算法 算法 排序算法
发布时间 :
字数:5.7k 阅读 : 评论:
  1. 6.归并排序
    1. 6.1 基础知识
      1. 核心思想
      2. 算法步骤
      3. 时间复杂度
      4. 空间复杂度
      5. 稳定性
      6. 适用场景
      7. 代码步骤
      8. 总结说明
    2. 6.2 思路框架
    3. 6.3 纯净代码
    4. 6.4 带注释代码
    5. 6.5 运行结果

6.归并排序

6.1 基础知识

核心思想

归并排序采用分治法的思想，将一个大问题分解为小问题，先解决小问题，然后合并它们的解以得到原始问题的解。具体而言，归并排序将待排序数组分为两个子数组，分别排序后再合并成一个有序数组。可以通俗的理解为天下第一武道大会的形式。分淘汰赛，比完排序战斗力后就合成一个队了。一个个队再继续比，再合并队，直到比完。

算法步骤

  • 初始状态：将整个数组递归地分为两半，直到每个子数组只包含一个元素。
  • 递归排序：对每个子数组进行递归排序，直至每个子数组都有序。
  • 合并操作：合并两个有序子数组，创建一个新的有序数组。这个过程不断重复，直到整个数组有序。

时间复杂度

归并排序的时间复杂度始终为 O(n log n)，无论是最好、最坏还是平均情况。这是因为每次合并操作都需要线性时间，而递归树的深度是 log n。

空间复杂度

归并排序需要额外的空间来存储临时数组，其空间复杂度为 O(n)。这使得归并排序不是一个原地排序算法。

稳定性

归并排序是稳定的排序算法。相同元素的相对顺序在排序前后不会改变。

适用场景

由于其稳定性和一贯的 O(n log n) 时间复杂度，归并排序适用于各种规模的数据集。特别是在链表结构中，它比其他排序算法更易于实现。

代码步骤

  1. MergeSort 函数：接收一个数组进行归并排序。调用 MergeSortRecursive 函数传入数组和数组的起始终止索引，作为归并排序开始的递归入口。
  2. MergeSortRecursive 函数：接收数组和数组的起始终止索引。如果起始索引小于终止索引，说明有元素需要排序，把数组分成左右两半分别递归调用 MergeSortRecursive 函数得到排序后的左右数组，调用 Merge 函数对左右数组进行合并排序。如果起始索引不小于于终止索引，说明没有元素需要排序，只有一个元素了，直接返回只有该元素的数组。
  3. Merge 函数：合并左右数组并排序。定义长度是左右数组长度相加的结果数组。定义左右数组和结果数组指针索引。使用 while 循环，比较左右数组的元素，并将较小的元素放入合并数组，直到其中一个数组被完全处理，然后将另一个数组的剩余元素添加到合并数组中。

总结说明

归并排序在各个方面都表现出色，但其对额外空间的需求可能在某些情况下成为限制因素。在需要稳定性和较为均衡的性能时，归并排序是一个可靠的选择。然而，在对空间有严格限制的情况下，可能需要考虑其他排序算法。

6.2 思路框架

static void MergeSort(ref int[] array)
{
    调用归并排序递归部分函数MergeSortRecursive，传入数组和起始终止索引，得到排序后的数组
}

static int[] MergeSortRecursive(int[] array, int left, int right)
{
    如果左索引小于右索引
    {
        计算中间索引
        对左半部分调用归并排序递归部分函数，传入数组、左索引和中间索引，得到左半部分排序后的数组
        对右半部分调用归并排序递归部分函数，传入数组、中间索引+1和右索引，得到右半部分排序后的数组
        调用合并函数Merge，合并排序后的左右数组
    }

    左右索引相等，返回当前元素
    
}

Merge(int[] leftArray, int[] rightArray)
{
    初始化左、右、合并数组的索引
    获取左、右数组的长度
    初始化合并后的数组 mergedArray，长度为左右数组长度之和

    循环直到左或右数组其中一个索引值大于该数组长度后结束
    {
        若左数组当前元素小于等于右数组当前元素
        {
            将左数组当前元素放入合并数组中
            左数组索引向后移动一位
        }
        否则
        {
            将右数组当前元素放入合并数组中
            右数组索引向后移动一位
        }
        合并数组索引向后移动一位
    }

    若左数组还有剩余元素，则将剩余元素复制到合并数组末尾
    若右数组还有剩余元素，则将剩余元素复制到合并数组末尾

    返回合并后的数组 mergedArray
}

6.3 纯净代码

static void MergeSort(ref int[] array)
{
    array = MergeSortRecursive(array, 0, array.Length - 1);
}

static int[] MergeSortRecursive(int[] array, int left, int right)
{
    if (left < right)
    {
        int middle = (left + right) / 2;
        int[] leftSorted = MergeSortRecursive(array, left, middle);
        int[] rightSorted = MergeSortRecursive(array, middle + 1, right);
        return Merge(leftSorted, rightSorted);
    }

    return new int[] { array[left] };
}

static int[] Merge(int[] leftArray, int[] rightArray)
{
    int leftIndex = 0;
    int rightIndex = 0;
    int leftLength = leftArray.Length;
    int rightLength = rightArray.Length;
    int mergedIndex = 0;
    int[] mergedArray = new int[leftLength + rightLength];

    while (leftIndex < leftLength && rightIndex < rightLength)
    {
        if (leftArray[leftIndex] <= rightArray[rightIndex])
        {
            mergedArray[mergedIndex] = leftArray[leftIndex];
            leftIndex++;
        }
        else
        {
            mergedArray[mergedIndex] = rightArray[rightIndex];
            rightIndex++;
        }

        mergedIndex++;
    }

    while (leftIndex < leftLength)
    {
        mergedArray[mergedIndex] = leftArray[leftIndex];
        leftIndex++;
        mergedIndex++;
    }

    while (rightIndex < rightLength)
    {
        mergedArray[mergedIndex] = rightArray[rightIndex];
        rightIndex++;
        mergedIndex++;
    }

    return mergedArray;
}

require("Lesson01_SortHelpTool")

-- 归并排序函数
function QuickSort(array)
    array = QuickSortRecursive(array, 1, #array)
    return array
end

function QuickSortRecursive(array, left, right)
    if left < right then
        local middle = left + math.floor((right - left) / 2)

        local leftSorted = QuickSortRecursive(array, left, middle)
        local rightSorted = QuickSortRecursive(array, middle + 1, right)
        return Merge(leftSorted, rightSorted)
    end

    return {array[left]}
end

function Merge(leftArray, rightArray)
    local leftIndex = 1;
    local rightIndex = 1;
    local leftLength = #leftArray;
    local rightLength = #rightArray;
    local mergedIndex = 1;
    local mergedArray = {};

    while leftIndex <= leftLength and rightIndex <= rightLength do
        if(leftArray[leftIndex] < rightArray[rightIndex] ) then
            mergedArray[mergedIndex] = leftArray[leftIndex]
            leftIndex = leftIndex +1
        else
            mergedArray[mergedIndex] = rightArray[rightIndex]
            rightIndex = rightIndex +1
        end
        mergedIndex = mergedIndex+1
    end

    while leftIndex <= leftLength do
        mergedArray[mergedIndex] = leftArray[leftIndex]
        leftIndex = leftIndex +1
    end

    while rightIndex <= rightLength do
        mergedArray[mergedIndex] = rightArray[rightIndex]
        rightIndex = rightIndex +1
    end

    return mergedArray

end

SortHelpTool.PrintArray(SortHelpTool.arrayToSort, "排序前")

SortHelpTool.arrayToSort = QuickSort(SortHelpTool.arrayToSort)

SortHelpTool.PrintArray(SortHelpTool.arrayToSort, "排序后")

6.4 带注释代码

using System;
using Lesson01_概述;

class Program
{
    static void Main()
    {
        // 输出排序前的数组
        Console.WriteLine("排序前的数组:");
        SortHelpTool.PrintArray(SortHelpTool.arrayToSort);

        // 调用归并排序函数
        MergeSort(ref SortHelpTool.arrayToSort);

        // 输出排序后的数组
        Console.WriteLine("排序后的数组:");
        SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
    }

    // 归并排序函数
    static void MergeSort(ref int[] array)
    {
        // 调用归并排序辅助函数
        array = MergeSortRecursive(array, 0, array.Length - 1, 0);
    }

    // 归并排序的递归函数，返回吧左右数组合并排序后的数组
    static int[] MergeSortRecursive(int[] array, int left, int right, int depth)
    {
        Console.WriteLine(new String('-', 2 * depth) + $"开始归并排序的递归部分函数，深度是{depth}");
        // 如果左边索引小于右边索引，说明还有至少两个元素需要排序
        if (left < right)
        {
            Console.WriteLine(
                new String('-', 2 * depth) + $"左边索引小于右边索引，至少有两个元素需要排序，左边索引是{left}，右边索引是{right}，深度是{depth}");

            // 计算中间位置，这将帮助将数组一分为二
            int middle = (left + right) / 2;

            // 递归对左半部分进行排序
            Console.WriteLine(new String('-', 2 * depth) + $"开始递归对左半部分进行排序，左半部分开始索引是{left}，终止索引是{middle}，深度是{depth}");
            int[] leftSorted = MergeSortRecursive(array, left, middle, depth + 1);
            Console.WriteLine(new String('-', 2 * depth) + $"结束递归对左半部分进行排序，左半部分开始索引是{left}，终止索引是{middle}，深度是{depth}");


            // 递归对右半部分进行排序
            Console.WriteLine(new String('-', 2 * depth) +
                              $"开始递归对右半部分进行排序，右半部分开始索引是{middle + 1}，终止索引是{right}，深度是{depth}");
            int[] rightSorted = MergeSortRecursive(array, middle + 1, right, depth + 1);
            Console.WriteLine(new String('-', 2 * depth) +
                              $"结束递归对右半部分进行排序，右半部分开始索引是{middle + 1}，终止索引是{right}，深度是{depth}");

            // 合并两个已排序的部分的数组并重新排序
            return Merge(leftSorted, rightSorted, depth);
        }

        // 当左右索引相等时，返回只包含一个元素的数组，表示已排序
        Console.WriteLine(
            new String('-', 2 * depth) + $"左右索引相等，返回只包含一个元素的数组，表示已排序，索引是{left}，值是{array[left]}，深度是{depth}");
        Console.WriteLine(new String('-', 2 * depth) + $"结束归并排序的递归部分函数，深度是{depth}");
        return new int[] { array[left] };
    }

    // 合并两个已排序的部分的数组并重新排序函数
    static int[] Merge(int[] leftArray, int[] rightArray, int depth)
    {
        Console.WriteLine(new String('-', 2 * depth) + $"开始合并两个已排序的部分的数组并重新排序函数，深度是{depth}");
        Console.Write(new String('-', 2 * depth) + $"左数组是：");
        SortHelpTool.PrintArray(leftArray);
        Console.Write(new String('-', 2 * depth) + $"右数组是：");
        SortHelpTool.PrintArray(rightArray);

        // 初始化左子数组的索引
        int leftIndex = 0;

        // 初始化右子数组的索引
        int rightIndex = 0;

        // 获取左子数组的长度
        int leftLength = leftArray.Length;

        // 获取右子数组的长度
        int rightLength = rightArray.Length;

        // 初始化合并后数组的索引
        int mergedIndex = 0;

        // 创建一个新的数组，用于存储合并后的结果
        int[] mergedArray = new int[leftLength + rightLength];

        // 归并 leftArray 和 rightArray 到 mergedArray
        while (leftIndex < leftLength && rightIndex < rightLength)
        {
            // 比较左右两个子数组的元素，将较小的元素放入合并后的数组
            if (leftArray[leftIndex] <= rightArray[rightIndex])
            {
                mergedArray[mergedIndex] = leftArray[leftIndex];
                leftIndex++;
            }
            else
            {
                mergedArray[mergedIndex] = rightArray[rightIndex];
                rightIndex++;
            }

            // 移动合并后数组的索引
            mergedIndex++;
        }

        // 将 leftArray 的剩余部分复制到 mergedArray
        while (leftIndex < leftLength)
        {
            mergedArray[mergedIndex] = leftArray[leftIndex];

            // 移动 leftArray 和 mergedArray 的索引
            leftIndex++;
            mergedIndex++;
        }

        // 将 rightArray 的剩余部分复制到 mergedArray
        while (rightIndex < rightLength)
        {
            mergedArray[mergedIndex] = rightArray[rightIndex];

            // 移动 rightArray 和 mergedArray 的索引
            rightIndex++;
            mergedIndex++;
        }

        Console.Write(new String('-', 2 * depth) + $"合并结束，深度是{depth}，合并后的数组是：");
        SortHelpTool.PrintArray(mergedArray);

        Console.WriteLine(new String('-', 2 * depth) + $"结束归并排序的递归部分函数，深度是{depth}");
        // 返回合并后的结果数组
        return mergedArray;
    }

}

6.5 运行结果

排序前的数组:
5 2 8 1 7 3 10 4 6 9

开始归并排序的递归部分函数，深度是0
左边索引小于右边索引，至少有两个元素需要排序，左边索引是0，右边索引是9，深度是0
开始递归对左半部分进行排序，左半部分开始索引是0，终止索引是4，深度是0
–开始归并排序的递归部分函数，深度是1
–左边索引小于右边索引，至少有两个元素需要排序，左边索引是0，右边索引是4，深度是1
–开始递归对左半部分进行排序，左半部分开始索引是0，终止索引是2，深度是1
—-开始归并排序的递归部分函数，深度是2
—-左边索引小于右边索引，至少有两个元素需要排序，左边索引是0，右边索引是2，深度是2
—-开始递归对左半部分进行排序，左半部分开始索引是0，终止索引是1，深度是2
——开始归并排序的递归部分函数，深度是3
——左边索引小于右边索引，至少有两个元素需要排序，左边索引是0，右边索引是1，深度是3
——开始递归对左半部分进行排序，左半部分开始索引是0，终止索引是0，深度是3
——–开始归并排序的递归部分函数，深度是4
——–左右索引相等，返回只包含一个元素的数组，表示已排序，索引是0，值是5，深度是4
——–结束归并排序的递归部分函数，深度是4
——结束递归对左半部分进行排序，左半部分开始索引是0，终止索引是0，深度是3
——开始递归对右半部分进行排序，右半部分开始索引是1，终止索引是1，深度是3
——–开始归并排序的递归部分函数，深度是4
——–左右索引相等，返回只包含一个元素的数组，表示已排序，索引是1，值是2，深度是4
——–结束归并排序的递归部分函数，深度是4
——结束递归对右半部分进行排序，右半部分开始索引是1，终止索引是1，深度是3
——开始合并两个已排序的部分的数组并重新排序函数，深度是3
——左数组是：5
——右数组是：2
——合并结束，深度是3，合并后的数组是：2 5
——结束归并排序的递归部分函数，深度是3
—-结束递归对左半部分进行排序，左半部分开始索引是0，终止索引是1，深度是2
—-开始递归对右半部分进行排序，右半部分开始索引是2，终止索引是2，深度是2
——开始归并排序的递归部分函数，深度是3
——左右索引相等，返回只包含一个元素的数组，表示已排序，索引是2，值是8，深度是3
——结束归并排序的递归部分函数，深度是3
—-结束递归对右半部分进行排序，右半部分开始索引是2，终止索引是2，深度是2
—-开始合并两个已排序的部分的数组并重新排序函数，深度是2
—-左数组是：2 5
—-右数组是：8
—-合并结束，深度是2，合并后的数组是：2 5 8
—-结束归并排序的递归部分函数，深度是2
–结束递归对左半部分进行排序，左半部分开始索引是0，终止索引是2，深度是1
–开始递归对右半部分进行排序，右半部分开始索引是3，终止索引是4，深度是1
—-开始归并排序的递归部分函数，深度是2
—-左边索引小于右边索引，至少有两个元素需要排序，左边索引是3，右边索引是4，深度是2
—-开始递归对左半部分进行排序，左半部分开始索引是3，终止索引是3，深度是2
——开始归并排序的递归部分函数，深度是3
——左右索引相等，返回只包含一个元素的数组，表示已排序，索引是3，值是1，深度是3
——结束归并排序的递归部分函数，深度是3
—-结束递归对左半部分进行排序，左半部分开始索引是3，终止索引是3，深度是2
—-开始递归对右半部分进行排序，右半部分开始索引是4，终止索引是4，深度是2
——开始归并排序的递归部分函数，深度是3
——左右索引相等，返回只包含一个元素的数组，表示已排序，索引是4，值是7，深度是3
——结束归并排序的递归部分函数，深度是3
—-结束递归对右半部分进行排序，右半部分开始索引是4，终止索引是4，深度是2
—-开始合并两个已排序的部分的数组并重新排序函数，深度是2
—-左数组是：1
—-右数组是：7
—-合并结束，深度是2，合并后的数组是：1 7
—-结束归并排序的递归部分函数，深度是2
–结束递归对右半部分进行排序，右半部分开始索引是3，终止索引是4，深度是1
–开始合并两个已排序的部分的数组并重新排序函数，深度是1
–左数组是：2 5 8
–右数组是：1 7
–合并结束，深度是1，合并后的数组是：1 2 5 7 8
–结束归并排序的递归部分函数，深度是1
结束递归对左半部分进行排序，左半部分开始索引是0，终止索引是4，深度是0
开始递归对右半部分进行排序，右半部分开始索引是5，终止索引是9，深度是0
–开始归并排序的递归部分函数，深度是1
–左边索引小于右边索引，至少有两个元素需要排序，左边索引是5，右边索引是9，深度是1
–开始递归对左半部分进行排序，左半部分开始索引是5，终止索引是7，深度是1
—-开始归并排序的递归部分函数，深度是2
—-左边索引小于右边索引，至少有两个元素需要排序，左边索引是5，右边索引是7，深度是2
—-开始递归对左半部分进行排序，左半部分开始索引是5，终止索引是6，深度是2
——开始归并排序的递归部分函数，深度是3
——左边索引小于右边索引，至少有两个元素需要排序，左边索引是5，右边索引是6，深度是3
——开始递归对左半部分进行排序，左半部分开始索引是5，终止索引是5，深度是3
——–开始归并排序的递归部分函数，深度是4
——–左右索引相等，返回只包含一个元素的数组，表示已排序，索引是5，值是3，深度是4
——–结束归并排序的递归部分函数，深度是4
——结束递归对左半部分进行排序，左半部分开始索引是5，终止索引是5，深度是3
——开始递归对右半部分进行排序，右半部分开始索引是6，终止索引是6，深度是3
——–开始归并排序的递归部分函数，深度是4
——–左右索引相等，返回只包含一个元素的数组，表示已排序，索引是6，值是10，深度是4
——–结束归并排序的递归部分函数，深度是4
——结束递归对右半部分进行排序，右半部分开始索引是6，终止索引是6，深度是3
——开始合并两个已排序的部分的数组并重新排序函数，深度是3
——左数组是：3
——右数组是：10
——合并结束，深度是3，合并后的数组是：3 10
——结束归并排序的递归部分函数，深度是3
—-结束递归对左半部分进行排序，左半部分开始索引是5，终止索引是6，深度是2
—-开始递归对右半部分进行排序，右半部分开始索引是7，终止索引是7，深度是2
——开始归并排序的递归部分函数，深度是3
——左右索引相等，返回只包含一个元素的数组，表示已排序，索引是7，值是4，深度是3
——结束归并排序的递归部分函数，深度是3
—-结束递归对右半部分进行排序，右半部分开始索引是7，终止索引是7，深度是2
—-开始合并两个已排序的部分的数组并重新排序函数，深度是2
—-左数组是：3 10
—-右数组是：4
—-合并结束，深度是2，合并后的数组是：3 4 10
—-结束归并排序的递归部分函数，深度是2
–结束递归对左半部分进行排序，左半部分开始索引是5，终止索引是7，深度是1
–开始递归对右半部分进行排序，右半部分开始索引是8，终止索引是9，深度是1
—-开始归并排序的递归部分函数，深度是2
—-左边索引小于右边索引，至少有两个元素需要排序，左边索引是8，右边索引是9，深度是2
—-开始递归对左半部分进行排序，左半部分开始索引是8，终止索引是8，深度是2
——开始归并排序的递归部分函数，深度是3
——左右索引相等，返回只包含一个元素的数组，表示已排序，索引是8，值是6，深度是3
——结束归并排序的递归部分函数，深度是3
—-结束递归对左半部分进行排序，左半部分开始索引是8，终止索引是8，深度是2
—-开始递归对右半部分进行排序，右半部分开始索引是9，终止索引是9，深度是2
——开始归并排序的递归部分函数，深度是3
——左右索引相等，返回只包含一个元素的数组，表示已排序，索引是9，值是9，深度是3
——结束归并排序的递归部分函数，深度是3
—-结束递归对右半部分进行排序，右半部分开始索引是9，终止索引是9，深度是2
—-开始合并两个已排序的部分的数组并重新排序函数，深度是2
—-左数组是：6
—-右数组是：9
—-合并结束，深度是2，合并后的数组是：6 9
—-结束归并排序的递归部分函数，深度是2
–结束递归对右半部分进行排序，右半部分开始索引是8，终止索引是9，深度是1
–开始合并两个已排序的部分的数组并重新排序函数，深度是1
–左数组是：3 4 10
–右数组是：6 9
–合并结束，深度是1，合并后的数组是：3 4 6 9 10
–结束归并排序的递归部分函数，深度是1
结束递归对右半部分进行排序，右半部分开始索引是5，终止索引是9，深度是0
开始合并两个已排序的部分的数组并重新排序函数，深度是0
左数组是：1 2 5 7 8
右数组是：3 4 6 9 10
合并结束，深度是0，合并后的数组是：1 2 3 4 5 6 7 8 9 10
结束归并排序的递归部分函数，深度是0

排序后的数组:
1 2 3 4 5 6 7 8 9 10

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏