在 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

这是我编写的示例Comparator，用于按第一个元素对多维数组进行排序：

    private static class FirstItemComparator implements Comparator<int[]> {
        public int compare(int[] first, int[] second) {
            if (first[0] < second[0]) {
                return -1;
            } else if (first[0] == second[0]) {
                return 0;
            } else {
                return 1;
            }
        }
    }

    int[][] test = {{0,1},{4,8},{3,5}, {10,12}, {9,10}};
    Arrays.sort(input, new FirstItemComparator());
    // test is now {{0,1},{3,5},{4,8},{9,10},{10,12}}

通常，如果要将比较器传递给比较两个实例的静态方法，您只会编写比较器（传递比较器本质上就像传递其他语言中的函数）。您可以编写不同的比较器以几种不同的方式对同一类型的对象进行排序。

如果你想将一个实例与另一个实例进行比较，那么你将在 class 本身上实现接口 Comparable（而不是像我那样创建一个新的 class ).但是，这会强制对对象进行排序，因此您不能编写三个或四个 compareTo 方法以不同的方式对对象进行排序。

Answer 2

WifiData 应该通过比较 this 的 SSID 和 other.

来实现 Comparable<WifiData> 接口

您的方法的签名将变为：

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

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

Using comparator in custom quicksort in java

java

quicksort

comparator