时间戳

首页 > 解决方案 > k个部分的归并排序

java - k个部分的归并排序

问题描述

我真的很感谢对这项任务的一些帮助。任务是开发一种合并排序算法，将输入数组递归地“拆分”为 k 个数组。我最初编写了两种方法来合并排序，分为两部分，即合并排序和合并。我试图概括这个算法

public class MergeSort {

    public static int[] mergeSort(int[] a, int p, int r) {
        // p is left bound
        // r is right bound
        if (p < r) {
            int q = (int)Math.floor((p + r) / 2);
            mergeSort(a, p, q);
            mergeSort(a, q + 1, r);
            return merge(a, p, q, r);
        } else
            return a;
    }

    // p ist linke grenze
    // r ist rechte grenze
    public static int[] merge(int[] a, int p, int q, int r) {
        int n1 = q - p + 1; //length of first array
        int n2 = r - q;     //length of second array
        int[] lt = new int[n1 + 1];
        int[] rt = new int[n2 + 1];
        for (int i = 0; i < n1; i++) {
            lt[i] = a[p + i];
        }
        for (int j = 0; j < n2; j++) {
            rt[j] = a[q + j + 1];
        }
        lt[n1] = 1000000000; //sentinels
        rt[n2] = 1000000000;
        int i = 0;
        int j = 0;

        for (int k = p; k <= r; k++) { //comparing the values of the arrays and merging
            if (lt[i] <= rt[j]) {
                a[k] = lt[i];
                i++;
            } else {
                a[k] = rt[j];
                j++;
            }
        }
        return a;
    }

    public static int[] mergeSortK(int[] a, int k, int p, int r) {
        // k number of steps; p is first index of array; r is last index of array;
        if (p < r) {
            int[] pos = new int[k + 1]; //array for saving the indices of the "splits"
            for (int i = 0; i <= k; i++) {
                pos[i] = (int) Math.floor(p + (r - p) / k * i); //saving the array indices
            }
            for (int i = 0; i < k; i++) {
                mergeSortK(a, k, pos[i], pos[i + 1]); //sorting the arrays
            }
            for (int i = 0; i < k - 1; i++) {
                merge(a, pos[i], pos[i + 1], pos[i + 2]); //merging the arrays pairwise
            }
        }
        return a;
    }


    public static void main(String[] args) {
        // task 2.1.a)
        // Example Values:
        int[] list = { 2, 1, 5, 6, 2, 12 };
        int k = 4;

        // use MergeSort
        int[] newlist = mergeSortK(list, k, 0, list.length);
        printList(newlist);
    }

    // Helper function to print the elements of a list
    private static void printList(int[] list) {
        for(int i = 0; i < list.length; i++) {
            System.out.println(list[i]);
        }
    }
}

main 方法中给出的输入导致{2, 1, 2, 5, 6, 12}

非常感谢任何帮助！对不起，如果我做错了，我是来学习的，我真的希望你们能帮助我！

标签： javasortingmergesort

解决方案

你的代码有几个问题：

  • 不需要Math.floor()截断整数除法的结果，与 Javascript 不同，Java/对int参数和浮点参数使用不同的语义。(p + r) / 2是积分商，但您可能需要编写p + (r - p) / 2以避免潜在的溢出p + r。
  • 当您list.length从main(). 这实际上是一种非常方便的约定，可以避免+1在计算切片大小时进行调整。删除那些错误的调整并依赖包含/排除的约定。
  • 不要使用哨兵：使用哨兵会阻止您正确排序包含大于或等于哨兵值的值的数组1000000000。这种方法没有必要，应该被禁止。只需将索引变量与切片长度进行比较，并在其中一个切片用完时复制剩余的元素。
  • 您对切片边界的计算mergeSortK不正确：p + (r - p) / k * i使用整数算术计算，因此(r - p) / k在乘法之前四舍五入。r如果r - p不是 的倍数，则最后一个切片结束索引将不相等k。在除法之前进行乘法可以解决此问题，但可能会超出 type 的范围int。
  • mergeSortK不进行 k 路合并，而是进行一系列对 . 不够的部分合并k > 2。
  • 你的测试集有点小。

这是一个更正的版本：

public class MergeSort {

    public static int[] mergeSort(int[] a, int p, int r) {
        // p is left bound (included)
        // r is right bound (excluded)
        if (r - p >= 2) {
            int q = p - (r - p) / 2;
            mergeSort(a, p, q);
            mergeSort(a, q, r);
            return merge(a, p, q, r);
        } else {
            return a;
        }
    }

    // p is left bound (included)
    // q is start of right slice
    // r is end of right slice (excluded)
    public static int[] merge(int[] a, int p, int q, int r) {
        int n1 = q - p;  // length of first array
        int n2 = r - q;  // length of second array
        int[] lt = new int[n1];
        for (int i = 0; i < n1; i++) {
            lt[i] = a[p + i];
        }
        int i = 0;  // index into lt
        int j = q;  // index into a for right slice
        int k = p;  // index into a for merged list

        while (i < n1 && j < r) { //comparing the values of the arrays and merging
            if (lt[i] <= a[j]) {
                a[k] = lt[i];
                i++;
                k++;
            } else {
                a[k] = a[j];
                j++;
                k++;
            }
        }
        while (i < n1) { // copy remaining elements from right slice
            a[k] = lt[i];
            i++;
            k++;
        }
        // remaining elements from right slice are already in place
        return a;
    }

    public static int[] mergeSortK(int[] a, int k, int p, int r) {
        // k amount of steps; p is first index of slice; r is last index of slice (excluded);
        if (r - p >= 2) {
            if (k > r - p)
                k = r - p;
            int[] pos = new int[k + 1]; //array for saving the indices of the "splits"
            for (int i = 0; i <= k; i++) {
                pos[i] = p + (r - p) * i / k; //saving the array indices
            }
            for (int i = 0; i < k; i++) {
                mergeSortK(a, k, pos[i], pos[i + 1]); //sorting the arrays
            }
            while (k > 1) {
                int i, n = 1;
                for (i = 0; i < k - 1; i += 2) {
                    // merge slices 2 at a time: this will produce the expected output
                    //  but is not a direct k-way merge.
                    merge(a, pos[i], pos[i + 1], pos[i + 2]);
                    pos[n++] = pos[i + 2];
                }
                if (i < k)
                    pos[n++] = pos[i + 1];
                k = n - 1;
            }
        }
        return a;
    }

    public static void main(String[] args) {
        // task 2.1.a)
        // Example Values:
        int[] list = {
            64, 36, 46, 31, 45, 52,  4, 48, 74, 59,
            12, 16, 70, 67, 71, 26, 73, 34, 46, 84,
            60, 16, 26, 68, 56, 57, 97,  6, 39, 74,
            25, 69, 29, 69, 77, 26, 44, 53, 20,  6,
            77, 31, 71, 91, 28,  6, 24, 75, 26, 33,
             3, 20, 55, 94, 17, 81, 88, 32, 94, 32,
             3, 90, 76, 69,  9, 96, 76, 53, 78, 14,
            97, 32, 17, 15, 61, 63, 21,  0, 16, 14,
            61,  4, 81, 86, 29, 29, 27, 57, 85,  5,
            91, 54,  6, 68, 40, 88, 41,  9, 90, 51 };
        int k = 4;  // must be at least 2

        // use MergeSort
        int[] newlist = mergeSortK(list, k, 0, list.length);
        printList(newlist);
    }

    // Helper function to print the elements of a list
    private static void printList(int[] list) {
        for (int i = 0; i < list.length; i++) {
            System.out.println(list[i]);
        }
    }
}

我没有在末尾写一个正确的 k 路合并阶段，mergeSortK上面的代码应该可以工作，但会合并 ceil(log2(k)) 通道中的 k 个切片。直接单程 k 路合并很棘手，通常不值得。

推荐阅读