合并排序实现查询

Question

我在教程网页上在线找到了这个合并排序算法示例，我一直在尝试了解代码如何实现该算法。我发现的示例使用递归和临时数组对未排序算法的数组进行排序。我的查询处于流程的最后一步。将临时数组的元素复制到原数组中，对数组进行排序时。为什么算法递减右属性而不是递增左属性？当我增加 left left 值时，算法不起作用。

class Assignment1
{
    static void Main(string[] args)
    {
        Console.WriteLine("Size of array:");
        int n = Convert.ToInt16(Console.ReadLine());
        int[] unsorted = new int[n];

        for(int i = 0; i < n; i++)
        {
            Console.WriteLine("Enter a number:");
            unsorted[i] = Convert.ToInt16(Console.ReadLine());
        }

        Console.WriteLine("--------Sort---------");

        Recursion_Sort(unsorted, 0, n - 1);
        for (int i = 0; i < n; i++)
        {
              Console.WriteLine(unsorted[i]);
        }
    }

    static public void Merge(int[] numbers, int left, int mid, int right, int n)
    {

        int[] tempArray = new int[n];

        int i, lEnd, size, pos;



        lEnd = mid - 1;
        pos = left;
        size = (right - left + 1);


        while ((left <= lEnd) && (mid <= right))
        {

            if (numbers[left] <= numbers[mid])
            {

                tempArray[pos] = numbers[left];
                pos++;
                left++;
            }

            else
            {

                tempArray[pos] = numbers[mid];
                pos++;
                mid++;
            }
        }



        while (left <= lEnd)
        {
            tempArray[pos] = numbers[left];
            pos++;
            left++;
        }


        while (mid <= right)
        {
            tempArray[pos] = numbers[mid];
            pos++;
            mid++;
        }
        Console.WriteLine(tempArray.Length);


        for (i = 0; i < size; i++)
        {
            numbers[right] = tempArray[right];
            right--;
        }
    }

    static public void Recursion_Sort(int[] numbers, int left, int right)
    {

        int mid;

        if (right > left)
        {
            mid = (right + left) / 2;


            Recursion_Sort(numbers, left, mid);
            Recursion_Sort(numbers, (mid + 1), right);
            // we then merge the sorted sub arrays using the merge method
            Merge(numbers, left, (mid + 1), right, numbers.Length);
        }
    }
}

Answer 1

冒着不回答问题的风险，我建议 LINQ。这不是特别的合并排序，而是两个数组的连接，然后排序。

如果您的数组不是很大以至于性能很重要，您可能想要采用这种方法，因为它简单且代码更少（这总是好的）。

int[] arr1 = new[] { 1, 2, 3, 7, 8, 10 };
int[] arr2 = new[] { 4, 6, 9, 12, 15 };

int[] merged = arr1.Concat(arr2).OrderBy(n => n).ToArray();

此外，我 post 如果其他人对此感兴趣。

Answer 2

left 值在合并期间发生变化，因为您有代码块

while (left <= lEnd)
{
//...
left++;
}

left最终会赋值给lEnd + 1（while循环结束条件）
否则 right 不会改变并且是当前操作序列的最后一个索引。

合并排序实现查询

merge sort implementation query

c#

algorithm

sorting

mergesort