Сбой Сортировка выходов Неправильно

Question

Merge Sort.

/* 
* To change this license header, choose License Headers in Project Properties. 
* To change this template file, choose Tools | Templates 
* and open the template in the editor. 
*/ 
package algorithms; 

import java.util.Arrays; 

/** 
* 
* @author Navin 
*/ 
public class MergeSort { 

    int [] left; 
    int [] right; 

    public void Merge_Sort(int [] array){ 
     if(array.length<2){ 
      return; 
     }  

     int mid = array.length/2; 
     left = new int[mid]; 
     right = new int[array.length-mid]; 

     for(int i =0;i<mid;i++){ 
      left[i] = array[i]; 
     } 

     for(int j =mid;j<array.length;j++){ 
      right[j-mid] = array[j]; 

     } 

     System.out.println(Arrays.toString(left)); 
     System.out.println(Arrays.toString(right)); 

     Merge_Sort(left); 
     Merge_Sort(right); 
     Merge(left,right,array); 
    }  


    public void Merge(int [] left, int [] right, int [] array){ 

     int i=0; 
     int j=0; 
     int k=0; 

     while(i<left.length && j<right.length){ 

      if(left[i] < right[j]){ 
       array[k] = left[i]; 
       i++; 
      }else{ 
       array[k] = right[j]; 
       j++; 
      } 
      k++; 
     } 

    } 

    public static void main(String[] args) { 
     int [] array = {2,4,1,6,8,5,3,7}; 
     MergeSort ms = new MergeSort(); 

     ms.Merge_Sort(array); 
     System.out.println(Arrays.toString(array)); 
    } 
} 

Я не уверен, что случилось с выше, логика и реализация является правильным, но вывод несортированный массив, который является таким же, как на входе.

Выход: [2, 4, 1, 6, 8, 5, 3, 7]

Answer 1

я тестировал код и ваш метод слияния является неправильным. Используйте этот код, и все должно быть прекрасно:

public void merge(int[] left, int[] right, int[] array) { 
    int i = 0, j = 0, k = 0; 

    while (i < left.length && j < right.length) { 
     if (left[i] < right[j]) 
      array[k++] = left[i++]; 
     else   
      array[k++] = right[j++];    
    } 

    while (i < left.length) 
     array[k++] = left[i++]; 

    while (j < right.length)  
     array[k++] = right[j++]; 

    return; 
} 

Read this great SO post для получения информации о том, как объединить два отсортированных массивов в Java.

Answer 2

Здесь полная реализация Java из сортировки слиянием.

public void mergeSort(int[] a) { 
    int n = a.length; 

    // Base case for partitioning 
    // Array with single element is already sorted 
    if (n == 1) 
    return; 

    int middle = n/2; 
    // Create sub arrays 
    int[] left = new int[middle]; 
    int[] right = new int[n - middle]; 

    // Fill sub arrays 
    for (int i = 0; i < middle; i++) { 
    left[i] = a[i]; 
    } 
    for (int i = middle; i < n; i++) { 
    right[i - middle] = a[i]; 
    } 

    // recursively partition until 1 element is there 
    mergeSort(left); 
    mergeSort(right); 

    // Merge sub arrays 
    Merge(left, right, a); 

} 

public void Merge(int[] left, int[] right, int[] a) { 

    int leftArrItems = left.length; 
    int rightArrItems = right.length; 

    // i for left array looping 
    // j for right array looping 
    // k for a array looping 
    int i = 0; 
    int j = 0; 
    int k = 0; 

    while (i < leftArrItems && j < rightArrItems) { 

    // Decides from what sub array to pick to fill final array 
    if (left[i] < right[j]) { 
    a[k++] = left[i++]; 
    } else { 
    a[k++] = right[j++]; 
    } 
    } 

    // Just in case if any sub array is left over 
    // with additional elements 
    while (i < leftArrItems) { 
    a[k++] = left[i++]; 
    } 
    while (j < rightArrItems) { 
    a[k++] = right[j++]; 
    } 

} 

Вы можете увидеть логику слияния сортировки here