合并排序算法

合并排序利用分治法来完成排序。它的大致过程还可以用扑克牌来作比喻。

假设有两堆扑克牌，各自是从小到大排好序的，如果我想对这两堆扑克牌排序，只需要每次取两堆牌上面较小的那张，一直取到其中一堆为0，然后再依次把剩下的那堆牌取完，我们就把这两堆牌排好序了。

但是，两堆排好序的扑克牌是怎么来的呢？我们可以使用分治的思想。
假设有八张牌需要排序，我们可以将它分为两堆，每堆四张，然后再两分，直到每堆只有一张。我们拿到一组的两张牌，就是分好组的了，我们对这两张牌按到上面的过程排序，之后得到四堆排好序的，每堆两张。再对相邻的两堆按照上面的过程排序，得到两堆排好序的，每堆四张，最后再对这两堆排好序的牌使用上面的过程排序，得到最后的结果。

下面用代码来描述一下这个过程。首先定义一个函数叫Merge，它就是最上面对两堆牌排序的过程。

static void Merge(int[] array, int p, int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q;

    int[] leftArray = new int[n1];
    int[] rightArray = new int[n2];
    for (int i = 0; i < n1; i++)
    {
        leftArray[i] = array[i + p];
    }
    for (int i = 0; i < n2; i++)
    {
        rightArray[i] = array[i + q + 1];
    }

    int leftCursor = 0, rightCursor = 0;
    for (int i = p; i <= r; i++)
    {
        if (leftCursor == leftArray.Length)
        {
            array[i] = rightArray[rightCursor];
            rightCursor++;
            continue;
        }
        if (rightCursor == rightArray.Length)
        {
            array[i] = leftArray[leftCursor];
            leftCursor++;
            continue;
        }
        if (leftArray[leftCursor] <= rightArray[rightCursor])
        {
            array[i] = leftArray[leftCursor];
            leftCursor++;
        }
        else
        {
            array[i] = rightArray[rightCursor];
            rightCursor++;
        }
    }
}

它的输入是一个待排序的数组array，以及三个参数p,q,r，然后我们将数组p至q部分放到数组leftArray中，将q+1至r部分放到数组rightArray中，然后每次从leftArray或rightArray中那一个较小的书放到array的对应位置，直到把p至r部分的数组遍历一遍。

下面是关键的过程MergeSort

static void MergeSort(int[] array, int p, int r)
{
    if (p < r)
    {
        int q = (r + p) / 2;
        MergeSort(array, p, q);
        MergeSort(array, q + 1, r);
        Merge(array, p, q, r);
    }
}

下面是main方法来调用MergeSort

static void Main(string[] args)
{
    int[] myArray = { 7, 2, 101, 5, 21, 6, 1 };
    MergeSort(myArray, 0, myArray.Length - 1);
}

上面是合并排序的核心代码，我运行时还会加入一些打印输出的信息，以便更好的理解代码运行的过程。下面是打印输出

MergeSort:p=0,r=6
MergeSort:q=3
MergeSort:p=0,r=3
MergeSort:q=1
MergeSort:p=0,r=1
MergeSort:q=0
MergeSort:p=0,r=0
MergeSort直接返回
7, 2, 101, 5, 21, 6, 1,
MergeSort:p=1,r=1
MergeSort直接返回
7, 2, 101, 5, 21, 6, 1,
Merge:p=0,q=0,r=1
2, 7, 101, 5, 21, 6, 1,
2, 7, 101, 5, 21, 6, 1,
MergeSort:p=2,r=3
MergeSort:q=2
MergeSort:p=2,r=2
MergeSort直接返回
2, 7, 101, 5, 21, 6, 1,
MergeSort:p=3,r=3
MergeSort直接返回
2, 7, 101, 5, 21, 6, 1,
Merge:p=2,q=2,r=3
2, 7, 5, 101, 21, 6, 1,
2, 7, 5, 101, 21, 6, 1,
Merge:p=0,q=1,r=3
2, 5, 7, 101, 21, 6, 1,
2, 5, 7, 101, 21, 6, 1,
MergeSort:p=4,r=6
MergeSort:q=5
MergeSort:p=4,r=5
MergeSort:q=4
MergeSort:p=4,r=4
MergeSort直接返回
2, 5, 7, 101, 21, 6, 1,
MergeSort:p=5,r=5
MergeSort直接返回
2, 5, 7, 101, 21, 6, 1,
Merge:p=4,q=4,r=5
2, 5, 7, 101, 6, 21, 1,
2, 5, 7, 101, 6, 21, 1,
MergeSort:p=6,r=6
MergeSort直接返回
2, 5, 7, 101, 6, 21, 1,
Merge:p=4,q=5,r=6
2, 5, 7, 101, 1, 6, 21,
2, 5, 7, 101, 1, 6, 21,
Merge:p=0,q=3,r=6
1, 2, 5, 6, 7, 21, 101,
1, 2, 5, 6, 7, 21, 101,
排序后
1, 2, 5, 6, 7, 21, 101,

下面是完整的代码

class Program
{
    static void Main(string[] args)
    {
        int[] myArray = { 7, 2, 101, 5, 21, 6, 1 };
        MergeSort(myArray, 0, myArray.Length - 1);
        Console.WriteLine("排序后");
        PrintArray(myArray);
    }

    static void Merge(int[] array, int p, int q, int r)
    {
        Console.WriteLine("Merge:p={0},q={1},r={2}", p, q, r);
        int n1 = q - p + 1;
        int n2 = r - q;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];
        for (int i = 0; i < n1; i++)
        {
            leftArray[i] = array[i + p];
        }
        for (int i = 0; i < n2; i++)
        {
            rightArray[i] = array[i + q + 1];
        }

        int leftCursor = 0, rightCursor = 0;
        for (int i = p; i <= r; i++)
        {
            if (leftCursor == leftArray.Length)
            {
                array[i] = rightArray[rightCursor];
                rightCursor++;
                continue;
            }
            if (rightCursor == rightArray.Length)
            {
                array[i] = leftArray[leftCursor];
                leftCursor++;
                continue;
            }
            if (leftArray[leftCursor] <= rightArray[rightCursor])
            {
                array[i] = leftArray[leftCursor];
                leftCursor++;
            }
            else
            {
                array[i] = rightArray[rightCursor];
                rightCursor++;
            }
        }

        PrintArray(array);
    }

    static void MergeSort(int[] array, int p, int r)
    {
        Console.WriteLine("MergeSort:p={0},r={1}", p, r);
        if (p < r)
        {
            int q = (r + p) / 2;
            Console.WriteLine("MergeSort:q={0}", q);
            MergeSort(array, p, q);
            MergeSort(array, q + 1, r);
            Merge(array, p, q, r);
        }
        else
            Console.WriteLine("MergeSort直接返回");
        PrintArray(array);
    }

    static void PrintArray(int[] array)
    {
        for (int i = 0; i < array.Length; i++)
        {
            Console.Write(array[i].ToString() + ", ");
        }
        Console.WriteLine();
    }
}

秒客网

合并排序算法

相关文章