合并排序程序没有给出正确的结果?
Merge sort program is not giving the correct result?
我正在开发一个合并排序程序,但没有给出正确的结果,而且它没有将我的列表分成两个相等的部分,请看下面我的程序:
import java.util.Arrays;
public class MyProgram {
public static void main(String[] args){
int[] list = {64, 7, 52, 68, 19, 10, 11, 14, 17, 18, 19};
System.out.println("\t**AFTER SPLITING**");
System.out.println("Left List: "+Arrays.toString(leftList(list)));
System.out.println("Right List: "+Arrays.toString(rightList(list)));
System.out.println("\n\n\t**BEFORE MERGE SORT**");
System.out.println(Arrays.toString(list));
mergeSort(list);
System.out.println("\t**AFTER MERGE SORT**");
System.out.println(Arrays.toString(list));
}
private static void mergeSort(int[] array){
if(array.length > 1){
int[] left = leftList(array);
int[] right = rightList(array);
mergeSort(left); //recursion
mergeSort(right); //recursion
//Merging the sorted half into equal parts.
merge(array, left, right);
}
}
private static int[] leftList(int[] array){
int size = array.length/2;
int left[] = new int[size];
for(int i=0; i<size; i++){
left[i] = array[i];
}
return left;
}
private static int[] rightList(int[] array){
int size1 = array.length/2;
int size2 = array.length - size1;
int right[] = new int[size2];
for(int i=0; i<size2; i++){
right[i] = array[i+size1];
}
return right;
}
private static void merge(int[] result, int[] left, int[] right){
int i1 = 0; //left index.
int i2 = 0; //right index.
for(int i=0; i<result.length; i++){
if(i1 < left.length && i2 < right.length){
if(left[i1] <= right[i2]){
result[i1] = left[i1];
i1++;
}
else{
result[i2] = right[i2];
i2++;
}
}
else if(i1 < left.length){
result[i1] = left[i1];
i1++;
}
else{
result[i2] = right[i2];
i2++;
}
}
}
}
它给出以下输出:
**AFTER SPLITING**
Left List: [64, 7, 52, 68, 19]
Right List: [10, 11, 14, 17, 18, 19]
**BEFORE MERGE SORT**
[64, 7, 52, 68, 19, 10, 11, 14, 17, 18, 19]
**AFTER MERGE SORT**
[68, 19, 19, 68, 19, 19, 11, 14, 17, 18, 19]
正如您在上面看到的,我的 leftList and rightList
被分成相等的部分但没有对我的结果进行排序。
不胜感激!!
在 merge
中,您使用 i1
和 i2
索引到 result
,而不是 i
。
private static void merge(int[] result, int[] left, int[] right){
int i1 = 0; //left index.
int i2 = 0; //right index.
for(int i=0; i<result.length; i++){
if(i1 < left.length && i2 < right.length){
if(left[i1] <= right[i2]){
result[i] = left[i1];
i1++;
}
else{
result[i] = right[i2];
i2++;
}
}
else if(i1 < left.length){
result[i] = left[i1];
i1++;
}
else{
result[i] = right[i2];
i2++;
}
}
}
我正在开发一个合并排序程序,但没有给出正确的结果,而且它没有将我的列表分成两个相等的部分,请看下面我的程序:
import java.util.Arrays;
public class MyProgram {
public static void main(String[] args){
int[] list = {64, 7, 52, 68, 19, 10, 11, 14, 17, 18, 19};
System.out.println("\t**AFTER SPLITING**");
System.out.println("Left List: "+Arrays.toString(leftList(list)));
System.out.println("Right List: "+Arrays.toString(rightList(list)));
System.out.println("\n\n\t**BEFORE MERGE SORT**");
System.out.println(Arrays.toString(list));
mergeSort(list);
System.out.println("\t**AFTER MERGE SORT**");
System.out.println(Arrays.toString(list));
}
private static void mergeSort(int[] array){
if(array.length > 1){
int[] left = leftList(array);
int[] right = rightList(array);
mergeSort(left); //recursion
mergeSort(right); //recursion
//Merging the sorted half into equal parts.
merge(array, left, right);
}
}
private static int[] leftList(int[] array){
int size = array.length/2;
int left[] = new int[size];
for(int i=0; i<size; i++){
left[i] = array[i];
}
return left;
}
private static int[] rightList(int[] array){
int size1 = array.length/2;
int size2 = array.length - size1;
int right[] = new int[size2];
for(int i=0; i<size2; i++){
right[i] = array[i+size1];
}
return right;
}
private static void merge(int[] result, int[] left, int[] right){
int i1 = 0; //left index.
int i2 = 0; //right index.
for(int i=0; i<result.length; i++){
if(i1 < left.length && i2 < right.length){
if(left[i1] <= right[i2]){
result[i1] = left[i1];
i1++;
}
else{
result[i2] = right[i2];
i2++;
}
}
else if(i1 < left.length){
result[i1] = left[i1];
i1++;
}
else{
result[i2] = right[i2];
i2++;
}
}
}
}
它给出以下输出:
**AFTER SPLITING**
Left List: [64, 7, 52, 68, 19]
Right List: [10, 11, 14, 17, 18, 19]
**BEFORE MERGE SORT**
[64, 7, 52, 68, 19, 10, 11, 14, 17, 18, 19]
**AFTER MERGE SORT**
[68, 19, 19, 68, 19, 19, 11, 14, 17, 18, 19]
正如您在上面看到的,我的 leftList and rightList
被分成相等的部分但没有对我的结果进行排序。
不胜感激!!
在 merge
中,您使用 i1
和 i2
索引到 result
,而不是 i
。
private static void merge(int[] result, int[] left, int[] right){
int i1 = 0; //left index.
int i2 = 0; //right index.
for(int i=0; i<result.length; i++){
if(i1 < left.length && i2 < right.length){
if(left[i1] <= right[i2]){
result[i] = left[i1];
i1++;
}
else{
result[i] = right[i2];
i2++;
}
}
else if(i1 < left.length){
result[i] = left[i1];
i1++;
}
else{
result[i] = right[i2];
i2++;
}
}
}