用比较器和交换函数进行java排序
我需要使用自定义比较器和交换function对函数进行排序。 我可以自己写一个，但我想知道其他人是否还没有这样做。 Java运行时包含许多专门的排序函数，用于排序基本类型，对象等数组，但它们都没有将交换函数作为参数。 谷歌搜索也没有找到任何有用的东西。
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); 这就是我要找的东西。 它基于java运行时算法对整数进行排序。 通过正确实现Sortable接口，它可以对任何事物进行排序。
public class Sort {
public static void sort（Sortable sortable，int off，int len）{
//在最小的数组上插入排序
if（len <7）{
for（int i = off; i off && sortable.compare（j - 1，j）> 0; j--）{
sortable.swap（j，j - 1）;
}
}
返回;
}
// 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* (
}
我需要在两个数组中交换索引。 我知道我可以排序二维数组，但这会增加所需的内存。
不。如果我理解正确，它不会导致任何开销。
请记住，Java不会将数组或对象直接存储在变量（或数组！）中。 它存储引用。 即使从数组引用的每个元素大40字节，它也将作为引用存储在数组中。
因此，我建议你使用内置的排序机制。 它们不会随机播放大量数据，只会引用参考文献。
因为Object数组的sort()是稳定的 ，所以您可以在自定义Comparator获取有用的信息。 这个按String长度排序时计算交换。
import java.util.Arrays; import java.util.Comparator; /** @see http://stackoverflow.com/questions/4983746 */ public class SortTest { private static class LengthComparator implements Comparator { private int count; public int compare(String s1, String s2) { int a = s1.length(); int b = s2.length(); if (a < b) { return -1; } else if (a > b) { count++; return 1; } else { return 0; } } } public static void main(String[] args) throws Exception { String[] sa = {"One", "Two", "Three", "Four", "Five"}; System.out.println(Arrays.toString(sa)); LengthComparator byLength = new LengthComparator(); Arrays.sort(sa, byLength); System.out.println(Arrays.toString(sa)); System.out.println(byLength.count); } }
安慰：
[一二三四五] [一，二，四，五，三] 2
关于swap：Java按值传递参数，因此方法swap(int a, int b)和swap(Object a, Object b)不能按预期工作。
如果你提出这些接口，至少要添加一些注释来说明它们应该做什么。 从讨论中我得到了你想要的东西：
/** * A Sortable represents a indexed collection of comparable * elements. * It does not offer direct access to its elements, only * comparison and swapping by indices. * * In the method specifications we are using this[i] to * mean the */ public interface Sortable { /** * Compares two elements by their indices. * @return -1 if this[first] < this[second], * 0 if this[first] = this[second] * 1 if this[first] > this[second] * @throws IndexOutOfBoundsException if one * or both indices are outside of the * limits of this sequence. */ public int compare(int first, int second); /** * Swaps two elements by their indices. * This is roughly equivalent to this sequence: ** temp = this[first]; * this[first] = this[second]; * this[second] = temp; **/ public void swap(int first, int second); } interface Sorter { /** * sorts an interval of a sequence. * @param sequence the sequence to be sorted. * @param off the start of the interval to be sorted. * @param the length of the interval to be sorted. */ public void sort(Sortable sequence, int off, int len); }
然后你可以让你的排序算法实现
Sorter，而你的数据结构实现了Sortable。 当然，人们可以在IndexComparator和IndexSwapper分离Sortable的两个函数（而不是像你命名的Int …），但它们都直接耦合到你的数据结构（由你的两个数组组成）。