如何制作通用的计数排序方法？

Question

好的，我是一个能够翻译文本的助手。以下是您需要翻译的内容：

好的，我是一个相当初级的Java编程员，目前遇到了一个问题。我需要创建一个通用方法（sort），按频率对Type数组进行排序，基本上，我正在采用CountingSort算法并将其变为通用方法。这就是我迷茫的地方。我似乎无法弄清楚如何做到这一点。

这是我的说明链接， https://classes.cs.siue.edu/pluginfile.php/7068/mod_assign/intro/150mp08.pdf

代码： 驱动程序类

package mp08;

public class Main {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
   Lists array = new Lists();
   array.populateLists();
    System.out.println("Original Int List: \n");
   array.sort(Lists.intList);
    System.out.println("Sorted Int List: \n");

    }

}

列表类

package mp08;

import java.util.Arrays;
import java.util.Random;


public class Lists {
public static Integer[] intList;
public static Integer[] sortedintList;
public static Integer[] frequency;
public static Character[] charList;
public static Character[] sortedcharList;
public static int MAX_SIZE = 101;
public static int lengthInt;
public static int lengthChar;

public Lists(){
    this.intList = new Integer[MAX_SIZE];
    this.sortedintList = new Integer[MAX_SIZE];
    this.charList = new Character[MAX_SIZE];
    this.sortedcharList = new Character[MAX_SIZE];
    this.frequency = new Integer[MAX_SIZE];
    this.lengthInt = 0;
    this.lengthChar = 0;
}

//Makes random integer for populated lists method.
public int randomInt(int min, int max){
    Random rand = new Random();
    int randomNum = rand.nextInt((max-min)+1)+min;
    return randomNum;
}

//Makes random character for populated lists method.
public char randomChar(){
    String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int N = alphabet.length();
    Random rand = new Random();

    char randomLet = alphabet.charAt(rand.nextInt(N));
    return randomLet;
}

//Populates intList and charList with random values.
public void populateLists(){
    for (int i = 0; i < MAX_SIZE; i++) {
       intList[i] = randomInt(1,100);
       lengthInt++;
    } 
    for (int i = 0; i < MAX_SIZE; i++) {
        charList[i] = randomChar();
        lengthChar++;    
    }    
}



//Returns sorted array
public Integer[] sorted(){
return intList;
}



  public static <T> void sort(T[] array) {

// array to be sorted in, this array is necessary
// when we sort object datatypes, if we don't, 
// we can sort directly into the input array     
Integer[] aux = new Integer[array.length];

// find the smallest and the largest value
int min = 1;
int max = 101;

// init array of frequencies
int[] counts = new int[max - min + 1];

// init the frequencies
for (int i = 0;  i < array.length; i++) {
  counts[array[i] - min]++;
}

// recalculate the array - create the array of occurence
counts[0]--;
for (int i = 1; i < counts.length; i++) {
  counts[i] = counts[i] + counts[i-1];
}

/*
  Sort the array right to the left
  1) Look up in the array of occurences the last occurence of the given value
  2) Place it into the sorted array
  3) Decrement the index of the last occurence of the given value
  4) Continue with the previous value of the input array (goto set1), 
     terminate if all values were already sorted
*/ 
for (int i = array.length - 1; i >= 0; i--) {
    aux[counts[array[i] - min]--] = array[i];
}


  }
     public static void main(String[] args) {

Integer [] unsorted = {5,3,0,2,4,1,0,5,2,3,1,4}; 
System.out.println("Before: " + Arrays.toString(unsorted));

Integer [] sorted = sort(unsorted);
System.out.println("After:  " + Arrays.toString(sorted));

  }
}

我显然还没有完成我的驱动程序课程，我会感激任何可以得到的帮助！

- Clint Sullivan

---

链接需要登录（和注册！）。您能否在此处粘贴说明？ - Mureinik

好的，稍等一下！1. https://gyazo.com/2aa207b057beabb600ef4a5172d3af14 - Clint Sullivan

抱歉，我無法識別圖片中的文字。請提供文字內容以便翻譯。 - Clint Sullivan

Answer 1

没有通用的方法可以让任何“Comparable”类型获取其序号。有时这样的数字根本不存在（例如，“String”是可比较的，但您无法将任何“String”映射到整数）。我可以提出两种解决方案。 第一种是不将计数存储在数组中，而是在“TreeMap”中创建新条目以响应需求（使用Java-8语法简洁起见）。

public static <T extends Comparable<T>> void sort(T[] array) {
    Map<T, Integer> counts = new TreeMap<>();

    for(T t : array) {
        counts.merge(t, 1, Integer::sum);
    }

    int i=0;
    for(Map.Entry<T, Integer> entry : counts.entrySet()) {
        for(int j=0; j<entry.getValue(); j++)
            array[i++] = entry.getKey();
    }
}

public static void main(String[] args) {
    Integer[] data = { 5, 3, 0, 2, 4, 1, 0, 5, 2, 3, 1, 4 };
    System.out.println("Before: " + Arrays.toString(data));

    sort(data);
    System.out.println("After:  " + Arrays.toString(data));

    Character[] chars = { 'A', 'Z', 'B', 'D', 'F' };
    System.out.println("Before: " + Arrays.toString(chars));

    sort(chars);
    System.out.println("After:  " + Arrays.toString(chars));
}

这种解决方案看起来很简洁，但可能不是非常优化的（虽然它的优点是它不关心所有数字是否都是从1到100）。另一种可能的解决方案是创建一些额外的接口，为给定类型定义排序。

public interface Ordering<T> {
    int toOrdinal(T obj);
    T toObject(int ordinal);
}

public class IntegerOrdering implements Ordering<Integer> {
    @Override
    public int toOrdinal(Integer obj) {
        return obj;
    }

    @Override
    public Integer toObject(int ordinal) {
        return ordinal;
    }
}

public class CharacterOrdering implements Ordering<Character> {
    @Override
    public int toOrdinal(Character obj) {
        return obj;
    }

    @Override
    public Character toObject(int ordinal) {
        return (char)ordinal;
    }
}

现在你可以让你的排序方法接受排序参数：

public static <T> void sort(T[] array, Ordering<T> ordering) { ... }

每当你需要通过T对象获取计数数组的索引时，只需调用ordering.toOrdinal(object)。每当你需要通过数组索引获取对象时，只需使用ordering.toObject(index)。因此，例如，可以使用以下代码：

counts[array[i] - min]++;

使用

counts[ordering.toOrdinal(array[i]) - min]++;

并且像这样调用排序方法：

sort(characterArray, new CharacterOrdering());

sort(integerArray, new IntegerOrdering());

- Tagir Valeev