带有比较器和交换功能的java排序

Question

我需要使用自定义比较器和交换函数对函数进行排序。我可以自己写一个，但我想知道是否其他人还没有这样做。 Java 运行时包含许多用于对基本类型数组、对象等进行排序的专用排序函数，但它们都没有将交换函数作为参数。 Google 搜索也没有找到任何有用的信息。

public interface IntComparator
{
    int compare(int a, int b);
}
public interface IntSwap
{
    void swap(int a, int b);
}
public static void sort(IntComparator compFn, IntSwap swapFn, int off, int len);

Answer 1

这就是我要找的。它基于用于对整数进行排序的 java 运行时算法。通过正确实现 Sortable 接口(interface)，它几乎可以对任何内容进行排序。

public class Sort {
    public static void sort(Sortable sortable, int off, int len) {
        // Insertion sort on smallest arrays
        if (len < 7) {
            for (int i = off; i < len + off; i++) {
                for (int j = i; j > off && sortable.compare(j - 1, j) > 0; j--) {
                    sortable.swap(j, j - 1);
                }
            }
            return;
        }


    // Choose a partition element, v
    int m = off + (len >> 1); // Small arrays, middle element
    if (len > 7) {
        int l = off;
        int n = off + len - 1;
        if (len > 40) { // Big arrays, pseudomedian of 9
            int s = len / 8;
            l = med3(sortable, l, l + s, l + 2 * s);
            m = med3(sortable, m - s, m, m + s);
            n = med3(sortable, n - 2 * s, n - s, n);
        }
        m = med3(sortable, l, m, n); // Mid-size, med of 3
    }

    // Establish Invariant: v* (<v)* (>v)* v*
    int a = off, b = a, c = off + len - 1, d = c;
    while (true) {
        while (b <= c && sortable.compare(b, m) <= 0) {
            if (sortable.compare(b, m) == 0) {
                sortable.swap(a, b);
                m = a;
                a++;
            }
            b++;
        }
        while (c >= b && sortable.compare(c, m) >= 0) {
            if (sortable.compare(c, m) == 0) {
                sortable.swap(c, d);
                m = d;
                d--;
            }
            c--;
        }
        if (b > c) {
            break;
        }
        sortable.swap(b++, c--);
    }

    // Swap partition elements back to middle
    int s, n = off + len;
    s = Math.min(a - off, b - a);
    vecswap(sortable, off, b - s, s);
    s = Math.min(d - c, n - d - 1);
    vecswap(sortable, b, n - s, s);

    // Recursively sort non-partition-elements
    if ((s = b - a) > 1) {
        sort(sortable, off, s);
    }
    if ((s = d - c) > 1) {
        sort(sortable, n - s, s);
    }
}

private static int med3(Sortable sortable, int a, int b, int c) {
    return sortable.compare(a, b) < 0 ? (sortable.compare(b, c) < 0 ? b : sortable.compare(a, c) < 0 ? c : a)
            : sortable.compare(b, c) > 0 ? b : sortable.compare(a, c) > 0 ? c : a;
}

private static void vecswap(Sortable sortable, int a, int b, int n) {
    for (int i = 0; i < n; i++, a++, b++) {
        sortable.swap(a, b);
    }
}