递归合并排序结果与原始结果相同

Question

我正在研究一个合并排序，它对int[]进行排序。我的mergeSort方法接受数组、startindex和EndIndex。我还输出了main方法中的before和after。after数组的结果与before相同。我看不出我的ALG做错了什么。我一直在查阅其他人对合并的看法，看起来我做得很对。显然不是，因为列表没有排序…我的合并排序算法做错了什么？

更新：所以我对我的代码做了一些修改，看起来分割过程工作得很好，但是当合并代码时，并没有合并排序的列表。相反，它只是使用被划分的原始的排序。这一点可以在合并的最后一步看到。它正在合并的两个数组应该进行排序，这样当您逐个比较每个索引时，两个数组中较小的一个数组应该以正确的顺序放入新列表中。

正在合并的两个列表分别为{2 3 2 52 64 2}&{1 8 54 8 32 7}，这与刚分成2的原始{2 3 2 52 64 2 1 8 54 8 32 7}相同。

新代码：

public static void main(String [] args) {
    int [] array = {2,3,2,52,64,2,1,8,54,8,32,7};

    int[] newarray = mergeSort(array, 0 ,array.length);


    System.out.println("\n");
    System.out.println("Unsorted List:");
    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }

    System.out.println("\n");
    System.out.println("Sorted List:");
    for (int i = 0; i < newarray.length; i++) {
        System.out.print(newarray[i] + " ");
    }
}


public static int[] mergeSort(int[] list, int start, int end) {
    if ((end-start) <= 1) {
        return list;
    }

        int mid = (start+end)/2;

        mergeSort(list, start, mid);
        mergeSort(list, mid, end);
        return merge(list, start, mid, end);
        //return list;
    }

public static int[] merge(int[]list, int start, int mid, int end) {
    int[] tempList = new int[list.length];

    System.out.println("First half");
    for (int i = start; i < mid; i++) {
        System.out.print(list[i] + " ");
    }
    System.out.println();
    System.out.println("Second half");
    for (int i = mid; i < end; i++) {
        System.out.print(list[i] + " ");
    }
    System.out.println();

    int i=start;
    int j=mid;
    int k=0;


    while (i < mid && j < end) {
        if (list[i] <= list[j]) {
            tempList[k] = list[i];
            i++;
            k++;
        } else {
            tempList[k] = list[j];
            j++;
            k++;
        }
    }

    while (i < mid) {
        tempList[k] = list[i];
        i++;
        k++;
    }
    while (j < end) {
        tempList[k] = list[j];
        j++;
        k++;
    }

    System.out.println("Merged");
    for (int z= 0 ; z < tempList.length; z++) {
        System.out.print(tempList[z] + " ");
    }
    System.out.println("\n");

    return tempList;
}

控制台输出:
上半场
3下半场
2
合并
2 3 0 0 0 0 0 0 0 0 0

上半场
2
下半场
3 2
合并
2 3 2 0 0 0 0 0 0 0 0

上半年
64
下半年
2
合并
2 64 0 0 0 0 0 0 0 0 0

上半场
52
下半场
64 2
合并
52 64 2 0 0 0 0 0 0 0 0

上半场
2 3 2
下半场
52 64 2
合并
2 3 2 52 64 2 0 0 0 0 0 0

上半年
8
下半年
54
合并
8 54 0 0 0 0 0 0 0 0 0

上半场
1
下半场
8 54
合并
1 8 54 0 0 0 0 0 0 0 0

上半年
32
下半年
7
合并
7 32 0 0 0 0 0 0 0 0 0

上半场
8
下半场
32 7
合并
8 32 7 0 0 0 0 0 0 0 0

上半场
1 8 54
下半场
8 32 7
合并
1 8 8 32 7 54 0 0 0 0 0 0

上半场
2 3 2 52 64 2
下半场
1 8 54 8 32 7
合并
1 2 3 2 8 52 54 8 32 7 64 2

未排序列表:
2 3 2 52 64 2 1 8 54 8 32 7

已排序列表:
1 2 3 2 8 52 54 8 32 7 64 2

Answer 1

这是一个递归过程，有分而治之的算法，所以很难理解。如果您不知道它是基于什么算法，请访问merge sort algorith{易于理解，有图}

1.概述

Mergesort算法可用于对对象集合进行排序。Mergesort是一种所谓的分而治之算法。各个击破算法将原始数据分成更小的数据集来解决问题。

2.合并

在Mergesort过程中，集合的对象被分成两个集合。要拆分集合，Mergesort将获取集合的中间部分，并将集合拆分为左部分和右部分。

结果集合再次通过Mergesort算法进行递归排序。

一旦两个集合的排序过程结束，两个集合的结果就被合并。要组合这两个集合，Mergesort将在每个集合的开始处启动。它选择较小的对象并将该对象插入到新集合中。对于这个集合，它现在选择下一个元素，并从两个集合中选择较小的元素。

在新集合中插入了两个集合中的所有元素后，Mergesort就成功地对该集合进行了排序。

为了避免创建过多的集合，通常会创建一个新的集合，并将左侧和右侧视为不同的集合。

3.执行

创建以下程序。

public class Mergesort {
    private int[] numbers;
    private int[] helper;

    private int number;

    public void sort(int[] values) {
            this.numbers = values;
            number = values.length;
            this.helper = new int[number];
            mergesort(0, number - 1);
    }

    private void mergesort(int low, int high) {
            // check if low is smaller then high, if not then the array is sorted
            if (low < high) {
                    // Get the index of the element which is in the middle
                    int middle = low + (high - low) / 2;
                    // Sort the left side of the array
                    mergesort(low, middle);
                    // Sort the right side of the array
                    mergesort(middle + 1, high);
                    // Combine them both
                    merge(low, middle, high);
            }
    }

    private void merge(int low, int middle, int high) {

            // Copy both parts into the helper array
            for (int i = low; i <= high; i++) {
                    helper[i] = numbers[i];
            }

            int i = low;
            int j = middle + 1;
            int k = low;
            // Copy the smallest values from either the left or the right side back
            // to the original array
            while (i <= middle && j <= high) {
                    if (helper[i] <= helper[j]) {
                            numbers[k] = helper[i];
                            i++;
                    } else {
                            numbers[k] = helper[j];
                            j++;
                    }
                    k++;
            }
            // Copy the rest of the left side of the array into the target array
            while (i <= middle) {
                    numbers[k] = helper[i];
                    k++;
                    i++;
            }

    }
}