递归和非递归合并排序算法之间的 time/space 复杂度是否存在差异？

Question

我已经使用分而治之的方法实现了合并排序算法，其中一个数组被分成两个子数组。

在我的代码中，我重新使用插入排序算法对合并排序中的子数组进行排序。这是正确的方法还是我必须使用不同的排序方法对合并排序中的子数组进行排序？

对于归并排序算法的理解，一切都清楚了，但是当涉及到归并排序的实现时，如何不使用递归策略将一个数组划分为n个子数组

递归或非递归是实现合并排序的有效方法吗？

下面是我在 github 中的代码片段： https://github.com/vamsikankipati/algorithms-in-java/blob/master/src/com/algorithms/sort/MergeSort.java

我从实现的角度了解到我的代码是错误的，因为我将数组分成两个子数组而不是 n 个子数组。

从算法实现的角度清楚地理解归并排序所需的任何帮助。

代码如下：

package com.algorithms.sort;

public class MergeSort {

    public static int[] increasing(int[] arr) {
        int[] result = new int[arr.length];
        int q = arr.length / 2;
        System.out.println("q: " + q);
        int[] left = new int[q];
        int[] right = new int[q];
        for (int i = 0; i < q; i++) {
            left[i] = arr[i];
        }
        int k = 0;
        for (int j = q; j < arr.length; j++) {
            right[k] = arr[j];
            k += 1;
        }
        left = InsertionSort.increasing(left);
        right = InsertionSort.increasing(right);

        // Printing
        for (int e : left) {
            System.out.print(e);
        }
        System.out.println("\n");
        for (int e : right) {
            System.out.print(e);
        }
        System.out.println("\n");

        int i = 0;
        int j = 0;
        int s = 0;
        while ((i < left.length) && (j < right.length)) {
            if (left[i] <= right[j]) {
                result[s] = left[i];
                i++;
            } else {
                result[s] = right[j];
                j++;
            }
            s++;
        }
        while (i < left.length) {
            result[s] = left[i];
            i++;
            s++;
        }
        while (j < right.length) {
            result[s] = right[j];
            j++;
            s++;
        }
        return result;
    }

    /**
     * Main method to test an example integer array
     */
    public static void main(String[] args) {
        int[] ar = { 18, 12, 11, 6, 55, 100 };
        int[] res = increasing(ar);
        for (int a : res) {
            System.out.print(a + " ");
        }
    }
}

Answer 1

两者的时间复杂度都是O( n log n)。

关于 space 的复杂性，实现可能因您的数据结构选择而异。在递归如果你选择数组： space 复杂度：N log N 如果你选择链表： space 复杂度为 O(1) 在迭代中：如果你选择数组： space 复杂度：N （根据您的实现，它是 O ( N log N) 因为您在每个划分状态下都创建了一个新的子数组，将它减少到 O(n) 你应该使用一个额外的数组作为原始数组的大小和索引）如果你选择链表： space 复杂度为 O(1)

如您所见，链表最适合排序。除此之外，由于函数框架的创建，递归可能会消耗比基于编程语言预期更多的内存。

Source

Answer 2

比优化更重要的是，首先要做到正确。 increasing 静态方法中有一个错误：如果数组参数的大小不是偶数，则 right 子数组分配的大小不正确：int[] right = new int[q]; 应该是

int[] right = new int[arr.length - q];

此外，如果数组太小，您不应该尝试拆分它。

关于优化，您应该只在子数组大小低于阈值（介于 16 到 128 个元素之间）时回退到 InsertionSort()。使用不同的阈值和各种分布进行仔细的基准测试将有助于为您的系统确定一个好的阈值。

按照目前的实现，您的函数的时间复杂度为 O(N²) 因为它遵循 InsertionSort除了最后一个合并阶段之外的所有阶段。要将复杂度降低到 O(N.log(N))，您必须递归子数组，直到它们的大小低于固定阈值。

这是修改后的版本：

package com.algorithms.sort;

public class MergeSort {

    public static int threshold = 32;

    public static int[] increasing(int[] arr) {
        if (arr.length <= threshold)
            return InsertionSort.increasing(arr);

        int len1 = arr.length / 2;
        int[] left = new int[len1];
        for (int i = 0; i < len1; i++) {
            left[i] = arr[i];
        }
        int len2 = arr.length - len1;
        int[] right = new int[len2];
        for (int i = 0; i < len2; i++) {
            right[i] = arr[i + len1];
        }
        left = increasing(left);
        right = increasing(right);

        int[] result = new int[len1 + len2];
        int i = 0;
        int j = 0;
        int s = 0;
        while (i < len1 && j < len2) {
            if (left[i] <= right[j]) {
                result[s] = left[i];
                i++;
            } else {
                result[s] = right[j];
                j++;
            }
            s++;
        }
        while (i < len1) {
            result[s] = left[i];
            i++;
            s++;
        }
        while (j < len2) {
            result[s] = right[j];
            j++;
            s++;
        }
        return result;
    }

    /**
     * Main method to test an example integer array
     */
    public static void main(String[] args) {
        int[] ar = { 18, 12, 11, 6, 55, 100 };
        int[] res = increasing(ar);
        for (int a : res) {
            System.out.print(a + " ");
        }
    }
}

递归和非递归合并排序算法之间的 time/space 复杂度是否存在差异？

is there a difference in time/space complexity between recursive and non-recursive merge sort algorithm?

java

sorting

algorithm

recursion

mergesort