合并排序演算法無法始終如一地作業并給出錯誤的輸出

我試圖實作合并排序，這是我的代碼：

import java.util.*;

public class MergeSort{
    public static void main(String args[]){
        int n;
        Scanner sc=new Scanner (System.in);
        System.out.println("Enter the size of array");
        n = sc.nextInt();
        int a[]=new int[n];

        System.out.println("Enter the elements into array");
        
        for(int i=0;i<n;i  ){
            a[i]=sc.nextInt();
        }
        divide(a,0,n-1);
    }

    public static void divide(int a[], int si, int ei){
        if(si>=ei){
            return;
        }
        int mid = si   (ei-si)/2;
        divide(a,si,mid);
        divide(a,mid 1,ei);
        conquer(a,si,mid,ei);
    }
    
    public static void conquer(int a[],int si,int mid, int ei){
        int newa[] = new int[ei 1];
        
        int i=si;
        int j=mid 1;
        int k=0;

        while(i<=mid && j<=ei){
            if(a[i]<=a[j]){
                newa[k]=a[i];
                i  ;
            }else{
                newa[k]=a[j];
                j  ;
            }
            k  ;
        }
        while(i<=mid){
            newa[k]=a[i];
            i  ;
            k  ;
        }
        while(j<=ei){
            newa[k]=a[j];
            j  ;
            k  ;
        }

        for(int p=0;p<=ei;p  ){
            System.out.println(newa[p]);
        }
        
    }
}

由于某種原因，該代碼適用于某些輸入，但不適用于其他輸入。例如 - 它在這里不起作用

輸入陣列 4 的大小 將元素輸入陣列 9 5 7 8 5 9 7 8 0 0 7 8 9 5

但它在這里作業

輸入陣列 4 的大小 將元素輸入陣列 7 5 6 4 7 5 6 0 0 4 5 6 7

我意識到我嘗試顯示排序陣列的方式不正確，即使在遞回呼叫期間它也會列印值。忽略這一點，我該如何解決排序問題？我試圖除錯但找不到代碼有什么問題

uj5u.com熱心網友回復：

您的演算法是正確的，只是缺少一件事，您沒有將修改后的即征服的元素存盤回陣列a。還有一件事，中間陣列的大小，即newa應該是ei-si。

這是修改后的代碼：

import java.util.*;

public class Main {
    public static void main(String args[]) {
        int n;
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the size of array");
        n = sc.nextInt();
        int a[] = new int[n];

        System.out.println("Enter the elements into array");

        for (int i = 0; i < n; i  ) {
            a[i] = sc.nextInt();
        }
        divide(a, 0, n - 1);
    }

    public static void divide(int a[], int si, int ei) {
        if (si >= ei) {
            return;
        }
        int mid = si   (ei - si) / 2;
        divide(a, si, mid);
        divide(a, mid   1, ei);
        conquer(a, si, mid, ei);
    }

    public static void conquer(int a[],int si,int mid, int ei){
        int newa[] = new int[ei-si 1];
        
        int i=si;
        int j=mid 1;
        int k=0;

        while(i<=mid && j<=ei){
            if(a[i]<=a[j]){
                newa[k]=a[i];
                i  ;
            }else{
                newa[k]=a[j];
                j  ;
            }
            k  ;
        }
        while(i<=mid){
            newa[k]=a[i];
            i  ;
            k  ;
        }
        while(j<=ei){
            newa[k]=a[j];
            j  ;
            k  ;
        }

        for(int p=0;p<=(ei-si);p  ){
            a[si p] = newa[p];
            System.out.print(newa[p]);
            System.out.print(" ");
        }
        System.out.println(" ");
        
    }
}

標籤：爪哇数组算法排序归并排序

上一篇：計算陣列中匹配物件數量的有效方法

下一篇：確定兩個未排序（短）陣列是否共享相同的元素？