我正在尝试实现一种方法,使用快速排序算法对键的数组列表进行排序。这是用于赋值的,因此我们只允许使用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。
任何帮助都将不胜感激!谢谢您。
1条答案
按热度按时间wmvff8tz1#
首先,你说v必须扩展comparable,但这是毫无意义的,因为你是排序键k,其次,你使用comparable作为一个原始类型,你不应该这样做
Comparable<K>
所以你的公共方法应该声明为然后对私有方法也应用相同的更改。
我还建议在方法声明中使用接口而不是类,以获得更大的灵活性