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

Question

我正在研究一种合并排序方法，它可以对int[]进行排序。我的mergeSort方法接受数组、startindex和endindex。我还在main方法中输出了之前和之后的内容。after数组的结果与前面的相同。我看不出我的alg做错了什么。我一直在查看其他人对合并排序的看法，看起来我做得很对。显然不是，因为列表没有排序..我在合并排序算法中做错了什么？

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

被合并的两个列表是{2 3 2 5 2 6 4 2} & {1 8 5 4 8 32 7}，与原来的{2 3 2 5 2 64 2 8 5 4 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

上半场

2

下半场

3 2

合并

2 3 2 0 0 0

上半场

64

下半场

2

合并

2 64 0 0 0

上半场

52

下半场

64 2

合并

52 64 2 0 0 0

上半场

2 3 2

下半场

52 64 2

合并

2 3 2 52 64 2 0 0 0

上半场

8

下半场

54

合并

8 54 0 0 0

上半场

1

下半场

8 54

合并

1 8 54 0 0 0

上半场

32

下半场

7

合并

7 32 0 0 0

上半场

8

下半场

32 7

合并

8 32 7 0 0 0

上半场

1 8 54

下半场

8 32 7

合并

1 8 8 32 7 54 0 0 0

上半场

2 3 2 52 64 2

下半场

1 8 54 8 32 7

合并

1 2 3 2 8 52 54 8 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 8 32 7 64 2

Answer 1

给你..。这是一个使用分而治之算法的递归过程，因此可能很难理解。如果您不知道它所基于的算法，请访问merge sort algorith {easy for understanding with figure}

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++;
            }

    }
}