错误地合并排序输出
Merge Sort Outputs Wrongly
合并排序。
/*
* 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]
这是合并排序的完整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
我测试了你的代码,你的合并方法是错误的。使用此代码,一切都应该没问题:
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;
}
阅读 this great SO post 了解如何在 Java 中合并两个排序数组的信息。
合并排序。
/*
* 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]
这是合并排序的完整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
我测试了你的代码,你的合并方法是错误的。使用此代码,一切都应该没问题:
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;
}
阅读 this great SO post 了解如何在 Java 中合并两个排序数组的信息。