Rắc rối với Hợp nhất Sắp xếp

Question

Đối với bài tập về nhà java của tôi Tôi đang đấu tranh để viết một lớp sắp xếp hợp nhất đệ quy. Hiện tại tôi có 3 phương thức là một "trình điều khiển" phương pháp để bắt đầu đệ quy, phương pháp đệ quy mergeSort và phương pháp merge. Tùy thuộc vào những biến tôi thay đổi đầu ra của tôi là một mảng của tất cả các số không hoặc mảng ban đầu của tôi theo cùng một thứ tự. Điều duy nhất là phương thức mergeSort gốc phải có trong một mảng và phương thức merge không thể trả về bất kỳ thứ gì. Bất kỳ trợ giúp nào được đánh giá cao

import java.util.Arrays; 
public class merge2 { 
    public static void main(String[] args){ 
     int []a={22,45,1,4,89,7,0}; 
     mergeSort(a); 
     System.out.println(Arrays.toString(a));     
    } 

    public static void mergeSort(int [] a){ 
     mergeSort(a,0,a.length-1); 
    } 

    public static void mergeSort(int []a, int beg,int end){ 
     if(beg<end){ 
      int mid=(beg+end)/2; 
      mergeSort(a,beg,mid); 
      mergeSort(a,mid+1,end); 
      merge(a,beg,mid,end); 
     } 
    } 

    private static void merge(int []a, int beg, int middle, int end){ 
     int [] d=new int[a.length]; 
     int mid=middle+1; //start of second half of array 
     for(int i=0;i<d.length;i++){ 
      if(beg<=middle && mid<=end){ 
       if(a[beg]<=a[mid]) { 
       d[i]=a[beg]; 
       beg++; 
       } else if(a[mid]<=a[beg]){ 
         d[i]=a[mid]; 
         mid++; 
       } 
      }else if(beg>middle){ 
       d[i]=a[mid]; 
       mid++; 
      }else if(mid==a.length){ 
       d[i]=a[beg]; 
       beg++; 
      } 
     } 
     for(int w=0;w<d.length;w++){ 
      a[w]=d[w]; 
     } 
    } 
} 

Answer 1

Ok tôi đã khắc phục giải pháp của bạn. Vấn đề chính của bạn là trên dòng được đánh dấu bằng //<= here. Khi mid chạy trên chỉ mục kết thúc, bạn đã không chỉ định giá trị từ a đến d sao cho nó được để lại đầy 0. Bạn phải thay thế == bằng >= để khắc phục sự cố này.
Tôi cũng đã sửa công việc của bạn với các chỉ mục. Bạn không phải chạy trên toàn bộ mảng trên mỗi cấp độ. Cũng phức tạp của bạn bị theo cách này. Tôi nghĩ về nó khoảng O(n^2). Nó đủ để chạy chỉ trên một phần của mảng được xử lý trên mức đệ quy này để giữ với độ phức tạp O(nlog(n)).

thuật toán cố định sau

public static void main(String[] args){ 
    int []a={22,45,1,4,89,7,0}; 
    mergeSort(a); 
    System.out.println(Arrays.toString(a)); 

} 

public static void mergeSort(int [] a){ 
    mergeSort(a,0,a.length-1); 
} 

public static void mergeSort(int []a, int beg,int end){ 
    if(beg<end){ 
     int mid=(beg+end)/2; 
     mergeSort(a,beg,mid); 
     mergeSort(a,mid+1,end); 
     merge(a,beg,mid,end); 
    } 
} 

private static void merge(int []a, int beg, int middle, int end){ 
    int [] d=new int[a.length]; 
    int mid=middle+1; //start of second half of array 
    int beg1=beg; 
    for(int i=beg1;i<=end;i++){ 
     if(beg<=middle && mid<=end){ 
      if(a[beg]<=a[mid]) { 
      d[i]=a[beg]; 
      beg++; 
      } else if(a[mid]<=a[beg]){ 
        d[i]=a[mid]; 
        mid++; 
      } 
     }else if(beg>middle){   
      d[i]=a[mid]; 
      mid++; 
     }else if(mid>=end){ //<= here 
      d[i]=a[beg]; 
      beg++; 
     } 
    } 
    for(int w=beg1;w<=end;w++){ 
     a[w]=d[w]; 
    } 
} 

Answer 2

Đây là mã giả cho phương thức hợp nhấtPhương pháp nhập. Tôi thấy rằng bạn đã bỏ qua các trường hợp cơ sở cho một hoặc hai yếu tố:

if (sublist has only one value) 
    do nothing 
else if (sublist has two values) 
    switch if necessary 
else // recursion, divide list into two halves 
    Find midpoint of current sublist 
    Call mergeSort and process left sublist 
    Call mergeSort and process right sublist 
    merge left and right sublists 

Đối với phương pháp hợp nhất của bạn, nó đang tạo ra một mảng mới thay vì sửa đổi existing array. Tôi khuyên bạn nên sử dụng ArrayLists để triển khai:

private void merge(int[] a, int first, int mid, int last) 
    { 
    ArrayList<Integer> left = new ArrayList<Integer>(mid - first + 1), right = new ArrayList<Integer>(last - mid); 
    for(int m = first; m <= mid; ++m) //initialize left sublist 
    { 
     left.add(a[m]); 
    } 
    for(int m = mid + 1; m <= last; ++m) //initialize right sublist 
    { 
     right.add(a[m]); 
    } 
    int i = first; 
    while(!left.isEmpty() || !right.isEmpty()) //while either list has an element 
    { 
     if(left.isEmpty()) 
     { 
     a[i++] = right.remove(0); 
     } 
     else if(right.isEmpty()) 
     { 
     a[i++] = left.remove(0); 
     } 
     else if (left.get(0) < right.get(0)) 
     { 
     a[i++] = left.remove(0); 
     } 
     else 
     { 
     a[i++] = right.remove(0); 
     } 
    } 
    }