在Java自定义quicksort中使用比较器 [英] Using comparator in custom quicksort in java
问题描述
我有一个自己实现的快速排序方法.我给该方法的对象数组.我如何使用比较器告诉方法对象将按哪个属性排序?我四处搜寻,发现了如何实现一个比较器,但是没有找到如何在搜索方法中使用它,因为每个示例ive都只使用arrays.sort().
I have a quicksort method that i implemented myself. i give an array of objects to that method. how do i use a comparator to tell the method which attribute the objects will be sorted by? I have googled around and found out how to implement a comparator, but not how to use it in the search method as every example ive found just used arrays.sort().
我需要不同的getter方法来获得不同的属性,我看不到比较器如何帮助您?
i need different getter-methods to get to the different attributes, i dont see how a comparator helps with that?
我只需要一点帮助就可以启动整个过程,或者也许有人可以设法在网上找到一个很好的例子?
i just need a little help to kickstart the whole thing, or maybe someone can manage to find a good example online?
public WifiData[] qsortSSID(WifiData[] array, int left, int right){
int ll=left;
int rr=right;
if (rr>ll){
String pivot=array[(ll+rr)/2].getSSID();
//System.out.println(pivot);
while (ll <=rr){
//finde erstes element >= pivot
while(ll<right && array[ll].getSSID().compareTo(pivot) < 0){
ll +=1;
}
//finde letztes elemtn kleiner gleich pivot
while(rr>left && array[rr].getSSID().compareTo(pivot) > 0){
rr -=1;
}
if (ll <=rr){
swap(array, ll ,rr);
ll +=1;
rr -=1;
}
}
if (left < rr){
qsortSSID(array,left,rr);
}
if (ll<right){
qsortSSID(array,ll,right);
}
}
return array;
}
推荐答案
WifiData
应该通过比较 SSID
来实现 Comparable< WifiData>
接口 this
和 other
.
WifiData
should implement Comparable<WifiData>
interface by comparing the SSID
of this
and other
.
您的方法的签名将变为:
The signature of your method would then become:
public Comparable[] qsort(Comparable[] array, int left, int right)
,实现将更加抽象,所以:
and the implementation will be more abstract, so:
String pivot=array[(ll+rr)/2].getSSID();
将变为:
Comparable pivot=array[(ll+rr)/2];
和
while(ll<right && array[ll].getSSID().compareTo(pivot) < 0){
将变为:
while(ll<right && array[ll].compareTo(pivot) < 0){
等
示例:
class WifiData implements Comparable<WifiData> {
String SSID;
public String getSSID() {
return SSID;
}
@Override
public int compareTo(WifiData o) {
return this.SSID.compareTo(o.getSSID());
}
public Comparable[] qsort(Comparable[] array, int left, int right){
int ll=left;
int rr=right;
if (rr>ll){
Comparable pivot = array[(ll+rr)/2];
while (ll <=rr){
while(ll<right && array[ll].compareTo(pivot) < 0){
ll +=1;
}
while(rr>left && array[rr].compareTo(pivot) > 0){
rr -=1;
}
if (ll <=rr){
swap(array, ll ,rr);
ll +=1;
rr -=1;
}
}
if (left < rr){
qsort(array,left,rr);
}
if (ll<right){
qsort(array,ll,right);
}
}
return array;
}
void swap(Comparable[] arr, int l, int r) {
Comparable t = arr[l];
arr[l] = arr[r];
arr[r] = t;
}
}
更新
阅读下面的评论后,您的问题就更清楚了.您应该使用比较器:您可以实现不同的比较器,每个比较器按不同的属性排序.
UPDATE
After reading your comment below your question is clearer. What you should do is use a Comparator: you can implement different Comparators, each of which sorts by a different property.
请参见以下示例:
class WifiData {
String SSID;
public String getSSID() {
return SSID;
}
// example how to use it
public static void main(String[] args) {
Comparator<WifiData> comp = new SSIDComparator();
WifiData[] arr = new WifiData[10];
// ... fill the array
arr = qsort(arr, 0, arr.length-1, comp);
}
public static WifiData[] qsort(WifiData[] array,
int left,
int right,
Comparator<WifiData> comp){
int ll=left;
int rr=right;
if (rr>ll){
WifiData pivot = array[(ll+rr)/2];
while (ll <=rr){
// that's how we'll use the comparator:
while(ll<right && comp.compare(array[ll], pivot) < 0){
ll +=1;
}
while(rr>left && comp.compare(array[rr], pivot) > 0){
rr -=1;
}
if (ll <=rr){
swap(array, ll ,rr);
ll +=1;
rr -=1;
}
}
if (left < rr){
qsort(array,left,rr, comp);
}
if (ll<right){
qsort(array, ll, right, comp);
}
}
return array;
}
// an example of Comparator that sorts by SSID
static class SSIDComparator implements Comparator<WifiData>{
@Override
public int compare(WifiData o1, WifiData o2) {
return o1.getSSID().compareTo(o2.getSSID());
}
}
}
这篇关于在Java自定义quicksort中使用比较器的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!