Hiểu cách sắp xếp hợp nhất hoạt động

Question

private void merge(int[] array, int[] aux, int low, int mid, int hi) { 
    int i = low, j = mid + 1, k; 

    for (k = low; k <= hi; k++) { 
     aux[k] = array[k]; 
    } 
    for (k = low; k <= hi; k++) { 
     if (i > mid) { 
      array[k] = aux[j++]; 
     } else if (j > hi) { 
      array[k] = aux[i++]; 
     } else if (aux[j] < aux[i]) { 
      array[k] = aux[j++]; 
     } else /* if (aux[i] <= aux[j] */ { 
      array[k] = aux[i++]; 
     } 
    } 
} 

private void sort(int[] array, int[] aux, int lo, int hi) { 
    if (hi <= lo) { 
     return; 
    } 

    int mid = lo + (hi - lo)/2; 
    sort(array, aux, lo, mid); 
    sort(array, aux, mid + 1, hi); 
    merge(array, aux, lo, mid, hi); 
} 

public void mergeSort() {  
    int aux[] = new int[n]; 
    sort(ar, aux, 0, n - 1); 
} 

Mã hoạt động nhưng tôi không hiểu.

1. tôi hiểu mục đích của

   if (hi <= lo) { 
       return; 
   } 
   

   nhưng tôi không biết những gì sẽ xảy ra khi lợi nhuận được thực thi.

2. Tôi không hiểu tại sao người cuối cùng khác trong hàm hợp nhất tồn tại. Nếu thuật toán tách ra cho đến khi aux là [3,5] và tôi muốn sắp xếp tăng dần, thì else if sẽ so sánh 5 < 3 sẽ chuyển sang giá trị khác và nó sẽ trao đổi 2 giá trị.

Chỉnh sửa: Tôi đã chơi một chút với trình gỡ lỗi và cho ví dụ này (3 33 1 55 66 34 67 45 23) nó đạt đến hàm kết hợp với 2 giá trị đầu tiên. Người cuối cùng khác nếu so sánh 33 < 3 và nhập người khác cuối cùng. Nếu các giá trị này theo thứ tự đúng thì điểm của dòng mã này là gì? Sau mảng [k] = aux [i ++]; được thực hiện giá trị của mảng [0] là như nhau mà là số lẻ vì aux [i ++] là mảng [1]

Answer 1

1. Trong sort phương pháp vấn đề được chia thành tiểu vấn đề nhỏ hơn. Khi phạm vi sắp xếp chỉ là một hoặc không rộng thì không có gì để làm và phương pháp có thể được đóng lại. Đó là bởi vì một phần tử một mình được sắp xếp theo định nghĩa. Đây là điều kiện dừng của đệ quy like m0skit0 said.

2. Các phần tử không được hoán đổi trong thuật toán này. Phương thức trys để hợp nhất hai mảng được sắp xếp. Có hai chỉ số i và j. Khi i đến giữa, tất cả các phần tử ở phần bên phải sẽ được thêm vào mảng kết quả. Nếu j đạt đến đường viền bên phải, tất cả các phần tử của phần bên trái sẽ được thêm vào kết quả. Đó là hai trường hợp đầu tiên.
   Bây giờ trong hai trường hợp cuối cùng, thuật toán sẽ cố gắng tìm ra các phần tử hiện tại được đánh số bởi i và j là mức tối thiểu và thêm nó vào mảng kết quả. Trong trường hợp thứ ba, phần tử tại j nhỏ hơn và được thêm vào mảng kết quả. Trong trường hợp đầu tiên, phần tử tại i được chọn.