java - 在java中的自定义快速排序中使用比较器

Question

我有一个自己实现的快速排序方法。我向该方法提供了一个对象数组。如何使用比较器来告诉方法对象将按哪个属性排序？ 我用谷歌搜索了一下，找到了如何实现比较器，但没有找到如何在搜索方法中使用它，因为我发现的每个示例都只是使用了 arrays.sort()。

我需要不同的 getter 方法来获取不同的属性，我不知道比较器如何帮助实现这一点？

我只需要一点帮助来启动整个事情，或者也许有人可以设法在网上找到一个很好的例子？

    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;
}

Answer 1

WifiData应该实现Comparable<WifiData>通过比较SSID界面的this和other .

您的方法的签名将变为:

public Comparable[] qsort(Comparable[] array, int left, int right)

而且实现会更加抽象，所以:

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;
    }
}

更新
阅读下面的评论后，您的问题更清楚了。你应该做的是使用 Comparator :您可以实现不同的比较器，每个比较器按不同的属性排序。

请参阅以下示例:

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());
        }
    }
}