0

我无法理解合并排序中的阈值以及如何确定它。我用谷歌搜索但没有结果。谁能为我解释一下？当阈值交叉使用插入排序时，我想使用合并排序对数组 [50000] 进行排序。

private int[] MergeSort(int[] lst)
    {
        int hl = lst.Length - 0;

        if (hl < 5 || hl < 10 || hl < 15 || hl < 20 || hl < 25 || hl < 30 || hl < 35 || hl < 40 || hl < 45 || hl < 50)
        {
            RunTime run = new RunTime();
            run.X = hl;
            InsertionSort(lst);
            run.Ttime = Process.GetCurrentProcess().TotalProcessorTime.Milliseconds;

                _listRunTime.Add(run);



        }

        if (lst.Length == 1)
            return lst;
        int middle = lst.Length / 2;
        int[] left = new int[middle];
        for (int i = 0; i < middle; i++)
        {
            left[i] = lst[i];
        }
        int[] right = new int[lst.Length - middle];
        for (int i = 0; i < lst.Length - middle; i++)
        {
            right[i] = lst[i + middle];
        }
        left = MergeSort(left);
        right = MergeSort(right);

        int leftptr = 0;
        int rightptr = 0;

        int[] sorted = new int[lst.Length];
        for (int k = 0; k < lst.Length; k++)
        {
            if (rightptr == right.Length || ((leftptr < left.Length) && (left[leftptr] <= right[rightptr])))
            {
                sorted[k] = left[leftptr];
                leftptr++;
            }
            else if (leftptr == left.Length || ((rightptr < right.Length) && (right[rightptr] <= left[leftptr])))
            {
                sorted[k] = right[rightptr];
                rightptr++;
            }
        }
        return sorted;
    }

    private void InsertionSort(int[] arr)
    {
        int i, j, tmp;
        for (i = 1; i < arr.Length; i++)
        {
            j = i;
            while (j > 0 && arr[j - 1] > arr[j])
            {
                tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;
                j--;
            }
        }
    }

我必须使用阈值而不是if (hl < 5 || hl < 10 || hl < 15 || hl < 20 || hl < 25 || hl < 30 || hl < 35 || hl < 40 || hl < 45 || hl < 50).

4

1 回答 1

0

看看这个讨论这个主题的问题：为什么要在合并排序中的阈值交叉后使用插入排序

基本上，阈值只是一个数字 n，如果在运行归并排序后还有 n 个未排序的元素，我们切换到插入排序。我相信 n 非常模棱两可，您可以在代码上对其进行测试，以查看哪个 n 优化了性能。所以不，除非您尝试一堆不同的值并测试性能，否则无法确定阈值数。

顺便说一句，你的巨大 if 语句与完全相同

if(hl < 50)

?

于 2013-04-30T16:02:54.207 回答