排序数组列表-不存在类型变量的示例,因此k符合可比较的

iklwldmw  于 2021-06-30  发布在  Java
关注(0)|答案(1)|浏览(330)

我正在尝试实现一种方法,使用快速排序算法对键的数组列表进行排序。这是用于赋值的,因此我们只允许使用java.util.arraylist、java.util.hashmap和java.util.map.entry(尽管我相信其他工具可以更轻松地实现这一点)。
这是我目前的代码:

//public method to return an array list containing all keys, quickly ordered in descending order
public static <K, V extends Comparable> ArrayList<K> fastSort(HashMap<K, V> results) {
    //create a new array list of type K to store the ordered key list in
    ArrayList<K> sortedUrls = new ArrayList<K>();

    //insert all the keys of the specified hash map to the new list
    sortedUrls.addAll(results.keySet());

    //call the quicksort method to sort the array list
    quicksort(sortedUrls,0, sortedUrls.size()-1);

    return sortedUrls;
}

private static <K, V extends Comparable> void swap(ArrayList<K> elements, int i, int j){
    //Method to swap 2 elements in an arraylist
    K temp = elements.get(i);
    elements.set(i, elements.get(j));
    elements.set(j, temp);
}

private static <K extends Comparable> void quicksort(ArrayList<K> elements, int beg, int end){
    //make sure that beginning and end indexes are proper
    if(beg>=end) return;
    if(beg<0) return;
    if(end>elements.size()-1) return;

    //update the pivot and swap appropriate elements using the partition helper method
    int pivot = partition(elements, beg, end);

    //recursively call quicksort on either side of the pivot
    quicksort(elements, beg, pivot-1);
    quicksort(elements, pivot+1, end);
}

private static <K extends Comparable> int partition(ArrayList<K> elements, int beg, int end){

    //Get a random pivot between beg and end
    int random = beg + ((int)Math.random()*(elements.size()))/(end-beg+1);

    //New position of pivot element
    int last=end;

    //Move the pivot element to right edge of the array
    swap(elements, random, end);
    end--;

    while(beg<=end){
        if(elements.get(beg).compareTo(elements.get(last)) < 0) beg++; //Accumulate smaller elements to the left
        else {
            swap(elements, beg, end);
            end--;
        }
    }

    //Move pivot element to its correct position
    swap(elements, beg, last);

    return beg;
}

在公共fastsort中调用quicksort方法时,我在arraylist sortedurls上遇到了这个编译错误:
原因:不存在类型变量的示例,因此k符合可比性。
我非常不习惯泛型类型,所以我肯定我在这方面做了一些错误的事情。但我不知道是什么,因为我已经声明k扩展了comparable,而sortedurls是k类型的arraylist。
任何帮助都将不胜感激!谢谢您。

wmvff8tz

wmvff8tz1#

首先,你说v必须扩展comparable,但这是毫无意义的,因为你是排序键k,其次,你使用comparable作为一个原始类型,你不应该这样做 Comparable<K> 所以你的公共方法应该声明为

public static <K extends Comparable<K>, V> ArrayList<K> fastSort(HashMap<K, V> results)

然后对私有方法也应用相同的更改。
我还建议在方法声明中使用接口而不是类,以获得更大的灵活性

public static <K extends Comparable<K>, V> List<K> fastSort(Map<K, V> results)

相关问题