选择排序不返回排序数组

Question

我正在尝试编写一个选择排序，在其中以int上边界为界的（子）数组中找到最大值，然后将当前值与最大值交换。

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

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; 
   }

我生成一个随机数组并调用sort并打印出“ sorted”数组，但所打印的数组根本没有排序...

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]

Answer 2

由于可比是原始类型。泛型类型Comparable的引用应参数化。不建议使用原始数据类型，除非有必要。

以下程序对您的代码进行了少量修改。您可以进行比较，并且它的运行复杂度为O（n ^ 2）。

您代码中的主要问题是在findMax（）函数中，通过对值进行硬编码使该函数静态化。

import java.util.Arrays;

public class XYZ {
    public static void main(String args[]) {
        sort(new Integer[] { 1, 5, 2, 11, 4 });
    }

    public static void sort(Comparable[] array) {
        int maxindex = 0;
        for (int k = 0; k < array.length; k++) { 
            maxindex = findMax(array, k);
            if (maxindex > k)
                swap(array, k, maxindex);
            //  System.out.println(Arrays.toString(array));
        }
    }

    public static int findMax(Comparable[] array, int startIndex) {
        Comparable max = array[startIndex];
        int maxindex = 0;
        for (int i = startIndex; i < array.length; 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;
    }
}