如何使用整数比较器实现选择排序？

Question

我一直在尝试使用比较器在 Java 中实施选择排序程序。

但是，虽然该程序对字符串可以正常工作，但对整数和混合大小写字符会失败（还没有尝试过浮点值！）

这是我的代码：

package edu.princeton.cs.algs4;

import java.util.Comparator;

public class Selection {

public static void sort(Comparable[] a) {
    int n = a.length;
    for (int i = 0; i < n; i++) {
        int min = i;
        for (int j = i+1; j < n; j++) {
            if (less(a[j], a[min])) min = j;
        }
        exch(a, i, min);
        assert isSorted(a, 0, i);
    }
    assert isSorted(a);
}

public static void sort(Object[] a, Comparator comparator) {
    int n = a.length;
    for (int i = 0; i < n; i++) {
        int min = i;
        for (int j = i+1; j < n; j++) {
            if (less(comparator, a[j], a[min])) min = j;
        }
        exch(a, i, min);
        assert isSorted(a, comparator, 0, i);
    }
    assert isSorted(a, comparator);
}

private static boolean less(Comparable v, Comparable w) {
    return v.compareTo(w) < 0;
}

private static boolean less(Comparator comparator, Object v, Object w) 
{
    return comparator.compare(v, w) < 0;
}

private static void exch(Object[] a, int i, int j) {
    Object swap = a[i];
    a[i] = a[j];
    a[j] = swap;
}

private static boolean isSorted(Comparable[] a) {
    return isSorted(a, 0, a.length - 1);
}

private static boolean isSorted(Comparable[] a, int lo, int hi) {
    for (int i = lo + 1; i <= hi; i++)
        if (less(a[i], a[i-1])) return false;
    return true;
}

private static boolean isSorted(Object[] a, Comparator comparator) {
    return isSorted(a, comparator, 0, a.length - 1);
}

private static boolean isSorted(Object[] a, Comparator comparator, int 
lo, int hi) {
    for (int i = lo + 1; i <= hi; i++)
        if (less(comparator, a[i], a[i-1])) return false;
    return true;
}


private static void show(Comparable[] a) {
    for (int i = 0; i < a.length; i++) {
        StdOut.println(a[i]);
    }
}

public static void main(String[] args) {
    String[] a = StdIn.readAllStrings();
    Selection.sort(a);
    show(a);
    }
}

对了，"StdIn"是普林斯顿大学提供的class标准输入，readAllStringsreturns是从file/standard输入中读取的所有字符串的数组。

以上代码对字符串数据非常有效。但是，当我想为整数数据测试相同的代码时，编译失败了。

这是我修改 main() 部分代码的方式：

public static void main() {
      Integer[] a = StdIn.readAllInts();
      Selection.sort(a);
      Selection.show(a);
}

readAllInts() 类似于 readAllStrings()。它读取所有整数和 returns 整数数组。

但是，编译时出现以下错误：

int[] 无法转换为 Integer[]

因此我再次替换了代码如下：

public static void main(String[] args) {
       int[] a = StdIn.readAllInts();
       Selection.sort(a);
       Selection.show(a);
}

但是，我又遇到了错误：

Selection.java:80: 错误：class 中显示的方法无法应用于给定类型；原因：参数不匹配； int 无法转换为 Comparable[]

这个错误：

Selection.java:79: 错误: 找不到合适的排序方法(int[])

谁能告诉我如何解决这个问题？我找到了一种可行的方法，但我需要先初始化整数数组并提供值。

这意味着我无法像读取 String 那样读取文件。

以下是各个 API 的链接以供进一步参考：

Selection Sort

StdIn API

提前致谢！！

Answer 1

这里有一个经典的 "impedence mismatch" 情况：

StdIn.readAllInts() 给你一个 int[]
Selection.sort() 和 Selection.show() 更喜欢 Integer[]

除了根据 Mike 的建议重写 StdIn.readAllInts 之外，没有灵丹妙药。您需要获取从 StdIn.readAllInts() 获得的 int[]，创建一个相同长度的 Integer[]，并将数字从 int[] 复制到 Integer[] 一个一个地使用循环。

Answer 2

Integer[] a = StdIn.readAllInts();
Selection.sort(a);

throws int[] cannot be converted to Integer[] 因为方法readAllInts() returns int[]顾名思义，不同基类型的数组不能相互转换

int[] a = StdIn.readAllInts();
Selection.sort(a);

抛出另一个异常，因为您的 sort() 方法需要一个 Comparable 数组（即对象数组）并获得一个 int 数组...

由于 int 不是 Class，它没有实现接口 Comparable。

您还可以编写一个采用 int 数组的 sort() 版本。（还有一些其他原始类型，如果你需要...）

另请查看 the methods of class Arrays：除了泛型或 Object 之外，它们中的大多数都有原始版本。

如何使用整数比较器实现选择排序？

How to implement Selection Sort using comparators for integers?

java

compare

comparable

comparator

selection-sort