如何使用自定义比较器对整数数组进行排序？

Question

我需要使用自定义比较器对int数组进行排序，但Java库不提供用于带有比较器的int排序函数（比较器只能与对象一起使用）。有没有简单的方法来做到这一点？

- Alexandru

---

你只是想将数组按降序排序，还是想执行更复杂的操作？ - Roman

更复杂的问题。我想使用绝对值作为关键字对int进行排序。 - Alexandru

Answer 1

如果您无法更改输入数组的类型，则以下内容可行：

final int[] data = new int[] { 5, 4, 2, 1, 3 };
final Integer[] sorted = ArrayUtils.toObject(data);
Arrays.sort(sorted, new Comparator<Integer>() {
    public int compare(Integer o1, Integer o2) {
        // Intentional: Reverse order for this demo
        return o2.compareTo(o1);
    }
});
System.arraycopy(ArrayUtils.toPrimitive(sorted), 0, data, 0, sorted.length);

这个方法使用了 ArrayUtils 这个来自 commons-lang 项目的工具类，方便地将 int[] 和 Integer[] 相互转换，它会创建一份数组副本，对其进行排序，然后再将排序后的数据复制回原数组中。

- Jon Freedman

---

为什么不使用Arrays.sort而是将数组 -> 列表 -> 数组进行转换？ - nanda

好的，我已经更新了。之前在尝试使用commons-primitives，但实际上并没有做任何有用的事情。 - Jon Freedman

我不知道commons-lang。谢谢你的提示。 - Alexandru

“return o2.compareTo(o1);”这句话正确吗？我认为这样排序会反转，就像我们期望的一样... 是的，这句话是正确的。它将使用o2和o1的比较结果来决定它们在排序结果中的顺序，因此可以实现所期望的反向排序。 - Pedro Dusso

是的，顺序被颠倒了，我选择这样做是为了证明它与“int”的自然顺序不同。 - Jon Freedman

Answer 2

考虑使用Java 8的流（Streams）如何？

int[] ia = {99, 11, 7, 21, 4, 2};
ia = Arrays.stream(ia).
    boxed().
    sorted((a, b) -> b.compareTo(a)). // sort descending
    mapToInt(i -> i).
    toArray();

或者原地进行：

int[] ia = {99, 11, 7, 21, 4, 2};
System.arraycopy(
        Arrays.stream(ia).
            boxed().
            sorted((a, b) -> b.compareTo(a)). // sort descending
            mapToInt(i -> i).
            toArray(),
        0,
        ia,
        0,
        ia.length
    );

- user3669782

---

我感到困扰的是在IntStream上我们无法使用sorted(IntComparator)。 - Hakanai

不要使用(a, b) -> b - a进行反向排序，这个比较器可能会溢出。请注意存在Comparator.reverseOrder()... - Holger

完全忽略了潜在的溢出问题。已经调整了答案。感谢Holger！ - user3669782

Answer 3

您可以使用来自fastutil库的IntArrays.quickSort(array, comparator)方法进行排序。

- leventov

Answer 4

如果您不想复制该数组（例如它非常大），您可以创建一个包装器List<Integer>，并在排序中使用它：

final int[] elements = {1, 2, 3, 4};
List<Integer> wrapper = new AbstractList<Integer>() {

        @Override
        public Integer get(int index) {
            return elements[index];
        }

        @Override
        public int size() {
            return elements.length;
        }

        @Override
        public Integer set(int index, Integer element) {
            int v = elements[index];
            elements[index] = element;
            return v;
        }

    };

现在，您可以使用自定义比较器对此包装器列表进行排序。

- user1460736

---

我更喜欢这个比被接受的回答。无需复制或转换数组内容，只需利用自定义实现的列表即可。 - OB1

看起来很整洁，但标准的sort实现将整个列表复制到数组中进行排序，然后将其写回。由于此列表没有实现RandomAccess标记，因此写回将使用ListIterator而不是只调用set。 - Holger

哇，Holger关于复制的说法是正确的。我甚至没有考虑过检查这个，因为我认为没有人会如此愚蠢地进行复制。 - user1460736

@user1460736 Javadocs中指出这是有意为之的，因为列表实现可能对随机访问效率低下。例如，LinkedList 直接排序会非常糟糕，因此它们进行了复制。为什么他们不检查 RandomAccess 不太清楚，我猜很少有人知道这个标记接口。 - Dmitry Avtonomov

扩展RandomAccess在将来进行此优化时不会有影响。然而，目前该方法未能实现其既定目标。 - Maarten Bodewes

Answer 5

您不需要外部库：

Integer[] input = Arrays.stream(arr).boxed().toArray(Integer[]::new);
Arrays.sort(input, (a, b) -> b - a); // reverse order
return Arrays.stream(input).mapToInt(Integer::intValue).toArray();

- XL Zheng

---

引用 Holgers 在另一个答案中的评论： "不要使用 (a, b) -> b - a 来进行倒序排序。这个比较器可能会溢出。请注意 Comparator.reverseOrder() 的存在。" - Hulk

Answer 6

通过将您的int数组转换为Integer数组，然后使用public static <T> void Arrays.sort(T[] a, Comparator<? super T> c)（第一步仅在我担心自动装箱可能无法在数组上工作时才需要）进行排序。

- Riduidel

Answer 7

如果你对性能和减少在过程中创建的对象数量感兴趣，考虑使用来自eclipse collections的实现。它使用自定义的IntComparator，可以操作原始类型，因此不需要装箱。

- Łukasz

Answer 8

Java 8：

Arrays.stream(new int[]{10,4,5,6,1,2,3,7,9,8}).boxed().sorted((e1,e2)-> e2-e1).collect(Collectors.toList());

- satyen

Answer 9

这里有一些代码（实际上并不是我最初认为的Timsort，但它确实很有效），可以在没有任何装箱/拆箱的情况下完成操作。在我的测试中，它比使用Collections.sort和围绕数组的List包装器快3-4倍。

// This code has been contributed by 29AjayKumar 
// from: https://www.geeksforgeeks.org/sort/

static final int sortIntArrayWithComparator_RUN = 32; 

// this function sorts array from left index to  
// to right index which is of size atmost RUN  
static void sortIntArrayWithComparator_insertionSort(int[] arr, IntComparator comparator, int left, int right) { 
    for (int i = left + 1; i <= right; i++)  
    { 
        int temp = arr[i]; 
        int j = i - 1; 
        while (j >= left && comparator.compare(arr[j], temp) > 0)
        { 
            arr[j + 1] = arr[j]; 
            j--; 
        } 
        arr[j + 1] = temp; 
    } 
} 

// merge function merges the sorted runs  
static void sortIntArrayWithComparator_merge(int[] arr, IntComparator comparator, int l, int m, int r) { 
    // original array is broken in two parts  
    // left and right array  
    int len1 = m - l + 1, len2 = r - m; 
    int[] left = new int[len1]; 
    int[] right = new int[len2]; 
    for (int x = 0; x < len1; x++)  
    { 
        left[x] = arr[l + x]; 
    } 
    for (int x = 0; x < len2; x++)  
    { 
        right[x] = arr[m + 1 + x]; 
    } 

    int i = 0; 
    int j = 0; 
    int k = l; 

    // after comparing, we merge those two array  
    // in larger sub array  
    while (i < len1 && j < len2)  
    { 
        if (comparator.compare(left[i], right[j]) <= 0)
        { 
            arr[k] = left[i]; 
            i++; 
        } 
        else 
        { 
            arr[k] = right[j]; 
            j++; 
        } 
        k++; 
    } 

    // copy remaining elements of left, if any  
    while (i < len1) 
    { 
        arr[k] = left[i]; 
        k++; 
        i++; 
    } 

    // copy remaining element of right, if any  
    while (j < len2)  
    { 
        arr[k] = right[j]; 
        k++; 
        j++; 
    } 
} 

// iterative sort function to sort the  
// array[0...n-1] (similar to merge sort)  
static void sortIntArrayWithComparator(int[] arr, IntComparator comparator) { sortIntArrayWithComparator(arr, lIntArray(arr), comparator); }
static void sortIntArrayWithComparator(int[] arr, int n, IntComparator comparator) { 
    // Sort individual subarrays of size RUN  
    for (int i = 0; i < n; i += sortIntArrayWithComparator_RUN)  
    { 
        sortIntArrayWithComparator_insertionSort(arr, comparator, i, Math.min((i + 31), (n - 1))); 
    } 

    // start merging from size RUN (or 32). It will merge  
    // to form size 64, then 128, 256 and so on ....  
    for (int size = sortIntArrayWithComparator_RUN; size < n; size = 2 * size)  
    { 
          
        // pick starting point of left sub array. We  
        // are going to merge arr[left..left+size-1]  
        // and arr[left+size, left+2*size-1]  
        // After every merge, we increase left by 2*size  
        for (int left = 0; left < n; left += 2 * size)  
        { 
              
            // find ending point of left sub array  
            // mid+1 is starting point of right sub array  
            int mid = Math.min(left + size - 1, n - 1);
            int right = Math.min(left + 2 * size - 1, n - 1); 

            // merge sub array arr[left.....mid] &  
            // arr[mid+1....right]  
            sortIntArrayWithComparator_merge(arr, comparator, left, mid, right); 
        } 
    } 
}

static int lIntArray(int[] a) {
  return a == null ? 0 : a.length;
}

static interface IntComparator {
  int compare(int a, int b);
}

- Stefan Reich

Answer 10

这是一个帮助方法来完成任务。

首先，您需要一个新的Comparator接口，因为Comparator不支持原始类型：

public interface IntComparator{
    public int compare(int a, int b);
}

当然，你可以使用自动装箱/拆箱来完成，但我不会这样做，那样很丑陋。

接下来，这里有一个帮助方法，使用这个比较器来对一个int数组进行排序：

public static void sort(final int[] data, final IntComparator comparator){
    for(int i = 0; i < data.length + 0; i++){
        for(int j = i; j > 0
            && comparator.compare(data[j - 1], data[j]) > 0; j--){
            final int b = j - 1;
            final int t = data[j];
            data[j] = data[b];
            data[b] = t;
        }
    }
}

下面是一些客户端代码。这个愚蠢的比较器将所有由数字“9”组成的数字按大小排列到前面（再次按大小排序），然后排列其它数字（无论有何好处）：

final int[] data =
    { 4343, 544, 433, 99, 44934343, 9999, 32, 999, 9, 292, 65 };
sort(data, new IntComparator(){

    @Override
    public int compare(final int a, final int b){
        final boolean onlyNinesA = this.onlyNines(a);
        final boolean onlyNinesB = this.onlyNines(b);
        if(onlyNinesA && !onlyNinesB){
            return -1;
        }
        if(onlyNinesB && !onlyNinesA){
            return 1;
        }

        return Integer.valueOf(a).compareTo(Integer.valueOf(b));
    }

    private boolean onlyNines(final int candidate){
        final String str = String.valueOf(candidate);
        boolean nines = true;
        for(int i = 0; i < str.length(); i++){
            if(!(str.charAt(i) == '9')){
                nines = false;
                break;
            }
        }
        return nines;
    }
});

System.out.println(Arrays.toString(data));

输出：

[9, 99, 999, 9999, 32, 65, 292, 433, 544, 4343, 44934343]

排序代码来自于 Arrays.sort(int[])，我只使用了针对小数组进行优化的版本。对于真正的实现，你可能需要查看 Arrays 类中的内部方法 sort1(int[], offset, length) 的源代码。

- Sean Patrick Floyd

---

Arrays.sort() 看起来使用快速排序，而提议的 sort() 则似乎使用插入排序。这样做会不会在渐近意义下变得更慢？ - Sudarshan S

是的，除非数组非常短，否则它的速度非常慢。 - Stefan Reich