java - 选择排序不返回排序数组

Question

我正在尝试编写一个选择排序，在其中找到以 int upper 为界的(子)数组中的最大值，并将当前值与最大值交换。

我编写了三个单独的方法 - 一个用于查找数组中最大值的索引的方法，一个用于交换两个值的方法，以及一个用于实际排序的排序方法。我尝试过调试，但不太擅长......

public static void sort(Comparable[] array)
   {
      int maxindex = 0;
      for(int k=0; k<array.length; k++)
      {
         maxindex = findMax(array, array.length-k);
         if(maxindex < k)
            swap(array, k, maxindex); 
      }   
   }

public static int findMax(Comparable[] array, int upper)
   {  //"upper" controls where the inner loop of the selection sort ends
      Comparable max = array[0];
      int maxindex = 0;
      for(int i = 1; i<upper; i++)
      {
         if(max.compareTo(array[i])<0)
         {
            max = array[i];
            maxindex = i;
         }
      }
      return maxindex;
   }

public static void swap(Object[] array, int a, int b)
   {
      Object save = array[b];
      array[b] = array[a];
      array[a] = save; 
   }

我生成一个随机数组并调用排序并打印出“已排序”数组，只不过打印的数组根本没有排序...

Answer 1

我采用了您的代码并对 sort 以及 findMax 函数进行了一些修改。现在，我们得到了正确的输出。

1. sort 函数:我不确定为什么在交换之前有条件，它会阻止某些 findMax 交换。另外，我猜测您正在执行 array.length - k ，因为您可能希望将最大值保留在最后一个索引中，然后循环查找下一个最大值，依此类推。这样做你的逻辑似乎是错误的。

2. findMax 函数:索引应从 0 开始，一直到 upper。

详情请参阅以下代码:

public static void sort(int[] array) {
    int maxindex = 0;
    for(int k=array.length - 1; k >= 0; k--) {
        maxindex = findMax(array, k);
        swap(array, k, maxindex);
    }
}

public static int findMax(int[] array, int upper) {  
    //"upper" controls where the inner loop of the selection sort ends
    int max = array[0];
    int maxindex = 0;
    for(int i = 0; i <= upper; i++) {
        if(max < array[i]) {
            max = array[i];
            maxindex = i;
        }
    }
    return maxindex;
}

输入:[4, 2, 3, 8, 7, 1, 9, 10, 15, 12, 11, 13]

输出:[1, 2, 3, 4, 7, 8, 9, 10, 11, 12, 13, 15]