在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屋！