为什么这种合并排序会给出错误的结果？

Question

我的任务是使用用户填充的int数组合并两个数组，我们必须假设用户最多有10000个输入，用户输入负数停止。然后将数组从最小到最大排序并打印出来。起初我以为这很容易，但当我完成时，我开始得到如下输出：

Enter the values for the first array, up to 10000 values, enter a negative number to quit: 1  
3  
5  
-1  
Enter the values for the second array, up to 10000 values, enter a negative number to quit  
2   
4  
6  
-1  
First Array:  
1   
3   
5  
Second Array:   
2  
4   
6   
Merged Array:  
6 1 2 3 4 5     

正如你所看到的，这六个是不合适的，我不知道如何修复它。这是源代码，我已经包括了大量的评论，因为我真的希望你们能帮助我尽你们最大的能力。如果可以使用相同的技术而不在代码中实现新的技术和方法，请这样做。我知道java中有一些方法可以在一行中完成所有这一切，但它是用于更基本级别的赋值。

import java.util.Scanner;

public class Merge

{


    public static void main(String [] args)    
    {
        Scanner scan = new Scanner(System.in);

    int [] first = new int[10000];          //first array, assume 10k inputs max
    int [] second = new int[10000];         //first array, assume 10k inputs max

    boolean legal = true; //WILL IMPLIMENT LATER


    int end = 0; // set how many elements to put in my "both" array
    int end2 = 0;// set how many elements to put in my "both" array


    System.out.print("Enter the values for the first array, up to 10000 values, enter a negative number to quit");
    //get values
    for(int i = 0; i<first.length; i++)
    {
          first[i] = scan.nextInt(); //fill first with user input

          if(first[i] <0) //if negative number, stop loop
          {
            end = i; //get position of end of user input
            break;
          }
    }

    System.out.println("Enter the values for the second array, up to 10000 values, enter a negative number to quit");

    for(int i = 0; i<second.length; i++) //exact same as the first get values loop
    {
      second[i] = scan.nextInt();

      if(second[i] <0)
      {
        end2 = i;
        break;
      }
    }

    System.out.print("First Array:\n");

    for(int i = 0; i<first.length; i++) //print first array
    {
      if(i == end) //this prevents from printing thousands of zeros, only prints values that user inputed
        break;
      System.out.println(first[i] + " ");
    }


    System.out.print("Second Array:\n"); 

    for(int i = 0; i<second.length; i++) //same as printing first array 
    {
          if(i == end2)
            break;
          System.out.println(second[i] + " ");
    }

    int [] both = new int[(end)+(end2)]; //instanciate an int array to hold only inputted values from first[] and second[]
    int [] bothF = new int[(end)+(end2)]; //this is for my simple sorter algotithm loop

    for(int i = 0; i<both.length; i++) //fill both with the first array that was filled
    {
      both[i] = first[i];
    }

    int temp = end; // see below
    for(int i = 0;i<both.length; i++) //fill array with the second array that was filled(starting from the end of the first array so that the first set is not overwritten
    {
      if(temp<both.length){ //this prevents an out of bounds
      both[temp] = second[i];

        temp++;}
    }

    //simple sorting algorithm
    for(int d = both.length -1;d>=0;d--)
    {    
          for(int i = 0; i<both.length; i++)
           {
                if(both[d]<both[i])
                {
                      bothF[d] = both[d];
                      both[d] = both[i];
                      both[i] = bothF[d];          
                }      
          }
    }

    System.out.println("Merged Array:"); //print the results
    for(int i = 0; i<both.length; i++)
    {
        System.out.print(both[i] + " ");

    }

    //System.out.println("ERROR: Array not in correct order");    
}

Answer 1

首先，我将从一些建议开始：

1. 一,。给end1和end2初始值作为数组长度

现在来看主要问题——为什么不将两个数组中的数字插入到join数组中，以保持它们的排序？

指导：

>

为每个数组保留一个标记

如果arr1[marker1]，则迭代新的联接数组

（别忘了选择如果两者相等会发生什么情况）。

这可以实现，因为数组首先被排序。

好好练习！

Answer 2

当然，你可以这样做

for (int i = 0; i < end; i++) {
    both[i] = first[i];
}
for (int i = 0; i < end2; i++) {
    both[i + end] = second[i];
}

// simple sorting algorithm
for (int d = both.length - 1; d >= 0; d--) {
    for (int i = 0; i < d; i++) {
        if (both[i] > both[d]) {
            int t = both[d];
            both[d] = both[i];
            both[i] = t;
        }
    }
}

产出-

Enter the values for the first array, up to 10000 values, enter a negative number to quit3
5
-1
Enter the values for the second array, up to 10000 values, enter a negative number to quit
2
4
6
-1
First Array:
3 
5 
Second Array: 
2 
4 
6
-1 
Merged Array:
2 3 4 5 6 

Answer 3

你的排序算法有问题。

它类似于选择排序，在这一点上，你可以选择两个元素，如果它们不合适，就交换它们。但是，在应该停止比较的时候不要停止：当索引d小于索引i时，比较和交换基于arr[d]

内部循环应以i=d终止。

你这种人的逻辑是这样的：

在第d个循环中，d1和右边的元素被正确排序（较大的数字）。这在开头是正确的，因为在最右边的元素的右边有0个元素被正确排序。

在每个外部循环上（使用d计数器），将第d个最大的元素槽与每个未排序的元素进行比较，如果另一个元素较大，则进行交换。

这足以对数组进行排序，但如果您开始将d个最大元素槽与其右侧已排序的元素进行比较，则槽中的数字最终会比应该的大。因此，内部循环应该在到达d时终止。