调试: Mergesort

Question

试图在Java中实现合并排序。我已经在脑海中读了一堆我的代码，我觉得它应该起作用了，但是很明显我做错了什么。这是代码

    public static void mergeSort(int[] input, int start, int end) {
        if (end - start < 2)
            return;
        
        int mid = (start + end) / 2;
        mergeSort(input, start, mid);
        mergeSort(input, mid + 1, end);
        merge(input, start, mid, end);
    }

    public static void merge(int[] input, int start, int mid, int end) {
        if (input[mid - 1] <= input[mid])
            return;
         
        int i = start;
        int j = mid;
        int tempIndex = 0;
        int[] temp = new int[end - start]; //combined size of both arrays being merged
        
        /*if i is >= mid, then that means the left portion of the array is done being sorted
          and vice versa if j >= end. Once this happens, we should be able to
          just copy the remaining elements into the temp array 
        */
        while (i < mid && j < end) {
            temp[tempIndex++] = (input[i] <= input[j]) ? input[i++] : input[j++];
        }
        
        //Copying left over elements in left portion
        while (i < mid)
            temp[tempIndex++] = input[i++];
        
        //Copying left over elements in right portion
        while (j < end)
            temp[tempIndex++] = input[j++];
        
        //Copy the sorted temp array into the original array
        //This is where I think I must be messing up
        for (int k = 0; k < temp.length; k++) {
            input[start + k] = temp[k];    
        }
     }

我认为，我肯定没有正确地将带有排序元素的temp数组复制回原始数组，但我不确定。我在代码上写了一些注释来解释我的逻辑。

Answer 1

请看一看以下更改：

1. 计算mid

int = start + (end )/ 2;

1. 正确地分配指针i、j。

int i= start；int j= mid+1;

1. 正确大小的临时数组。

int [] temp =新的intend-start+1;

1. 修正了代码中的while循环条件。

类解决方案{公共静态空mergeSort(int[] input，int start，int end) { if (end == start)返回；int = start + (end - start )/ 2；mergeSort(input，start，mid)；mergeSort(input，mid+1，end)；merge(输入，开始，中间，结束)；}公共静态无效合并(int[]输入、int start、int mid、int end ){ //不需要下面提到的指令// if(inputmid-1 <= inputmid)返回；int i= start；int j= mid+1；int tempIndex = 0；int [] temp =新意愿-启动+1；//合并的两个数组的组合大小为>= mid，这意味着数组的左边部分被排序，如果j >=结束，反之亦然。一旦发生这种情况，我们应该能够将剩余的元素复制到temp数组*/ while(i <= mid &j <= end){ temptempIndex++ = (inputi <= inputj)中？inputi++：inputj++；}/复制左侧部分中的剩余元素，而(i <= mid) temptempIndex++ = inputi++；//复制右侧部分中的剩余元素，而(j <= end) temptempIndex++ = inputj++；//将排序好的临时数组复制到原始数组/这是我认为我必须搞砸(int k= 0；k< temp.length；k++){ inputstart+k =tempk的地方；}}公共静态空洞主(String[] args){ int[]输入= {9,4,6,8,5,7,0,2}；mergeSort(输入，0，7)；for(int I: input) System.out.println(i)；}