在Java中按照最小值-最大值-最小值排序列表

Question

我希望把一组数据排序，使其看起来像概率分布函数的直方图（目前假设为正态分布）。

我有一个条目列表：

private static final class SortableDatasetEntry{
    Number value;
    Comparable key;
    public SortableDatasetEntry(Number value, Comparable key){
      this.value = value;
      this.key = key;
    }
}

一个示例： 我有这些项目：{1,2,3,4,5,6,7,8,9} 编辑： 我想要排序后的列表：{1,3,5,7,9,8,6,4,2}（或类似的内容）。数字不一定那么整齐（即仅按奇偶性排序也行不通）。我有一个部分解决方案，涉及按常规顺序排序（从低到高），然后通过每次插入到中间将该列表复制到另一个列表中，因此最后插入的项目（到中间）是最大的。我仍然希望找到一种使用比较器完成这项任务的方法。

删除线：这很棘手，因为它不是按value的绝对值进行排序，而是按其在集合中距离平均值（value）的距离进行排序，然后以某种方式移动，使得那些最接近平均值的值居中。我知道compareTo函数必须是“可逆”的（我忘记了正确的术语）。

额外加分：如何确定数据的正确分布（即如果它不是正态分布，就像假定的那样）。

- Zack Newsham

---

你能给出一个手动的例子，包含10-15个条目吗？ - Mshnik

你是指反射吗？另外，你展示的是一个初始化类字段的构造函数。这就是你想分享的所有代码吗？ - Chetan Kinger

@AndersonVieira 您是正确的，我不需要平均值 - 忽略问题的第二部分。第一部分是正确的，我想要列表的 PDF。 - Zack Newsham

@ Mshnik，现在会进行编辑。 - Zack Newsham

@AndyThomas，我很乐意听取你的建议。我认为两种方式都可以，但如果它们能均匀分布在两侧，那就更好了。 - Zack Newsham

Answer 1

首先计算平均值，将其存储在名为 "mean" 的变量中。接下来，在将条目插入 SortableDatasetEntry 时，使用 "value - mean" 作为每个条目的实际值，而不是 "value"。

- reservoirman

---

@ZackNewsham，移除Math.abs是否等同于按值排序？我认为Double.compare(v1 - mean, v2 - mean) == Double.compare(v1, v2)。 - Anderson Vieira

好的，但现在你需要两倍的内存 :) 如果你的数据集一开始就不大，那就没什么大问题了。 - reservoirman

@reservoirman 我同意，这是一种拙劣的解决方案 - 仍然希望有人能提出更好的东西，请参见编辑。 - Zack Newsham

@SashaSalauyou 我对随机性没问题，只要中间值最高，边缘值最低。我认为添加一个额外的字段会起作用。 - Zack Newsham

@ZackNewsham 是的，只需要一个额外的字段（比如说 r）就可以了。从源中获取元素时，将其随机分配为 -1 或 1。在比较器中，首先按 r 进行比较，如果相等，则按 distance * r 进行比较。 - Alex Salauyou

Answer 2

你会发现使用 Map 来构建直方图会更加容易。

public static Map<Integer, List<Number>> histogram(List<Number> values, int nBuckets) {
    // Get stats on the values.
    DoubleSummaryStatistics stats = values.stream().mapToDouble((x) -> x.doubleValue()).summaryStatistics();
    // How big must each bucket be?
    int bucketSize = (int) (stats.getMax() - stats.getMin()) / nBuckets;
    // Roll them all into buckets.
    return values.stream().collect(Collectors.groupingBy((n) -> (int) ((n.doubleValue() - stats.getMin()) / bucketSize)));
}

注意直方图的意图

构建直方图的第一步是将值范围“分组”——即将整个值范围分成一系列小间隔，然后计算落入每个间隔的值的数量。

- OldCurmudgeon

---

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Andy Thomas

@AndyThomas - 我的担忧是，如果OP已经有了桶计数，那么他们不需要排序，因为它们已经有序了——如果OP有值，则应首先对其进行分桶。假设一些高斯分布来排序它们可能是错误的。直方图不是一个值绘图，而是一个每个桶计数的绘图。 - OldCurmudgeon

如果OP试图构建直方图，则这是一个好的观点。明确的请求是进行一个类似于直方图的小/大/小排序。不清楚他们为什么想要这个顺序。 - Andy Thomas

Answer 3

类似这样的东西：

 public List<Integer> customSort(List<Integer> list) {
    Collections.sort(list);
    List<Integer> newList = new ArrayList<Integer>();
    for (int i = 0; i < list.size(); i += 2) {
        newList.add(list.get(i));
    }
    if (list.size() % 2 == 0) {
        for (int i = 1; i < list.size(); i += 2) {
            newList.add(list.get(list.size() - i));
        }
    } else {
        for (int i = 1; i < list.size(); i += 2) {
            newList.add(list.get(list.size() - i - 1));
        }
    }
    return newList;
}

这个程序怎么工作的？我输入 {1,2,3,4,5,6,7,8,9}，得到的结果是 {1,3,5,7,9,8,6,4,2}，而输入 {1,2,3,4,5,6,7,8} 则得到 {1,3,5,7,8,6,4,2}。

- M. Shaw

---

OP 不想要额外的列表。而你提出的方法使用 Deque 实现起来更加容易。 - Alex Salauyou

Answer 4

仅通过自定义 Comparator 无法在单个排序中完成此操作。

但是，仍然可以原地完成它，而无需其他引用集合。

您当前的方法不是原位的，但可能是最容易实现和理解的。除非内存中集合的大小是一个问题，否则请考虑使用您当前的方法。

单一排序中的自定义比较器

您所需的顺序取决于升序。对于未排序的数据，在进行第一次排序时，您的 Comparator 没有升序。

原地方法

您可以在现场创建所需的顺序。

以下假设为0索引。

一种方法是使用两个排序。首先，按升序排序。将每个对象与其索引标记。在第二个排序的比较器中，所有具有偶数索引的对象都将小于所有具有奇数索引的对象。具有偶数索引的对象将按升序排序。具有奇数索引的对象将按降序排序。

另一种方法是使用自定义排序算法，支持从虚拟索引到物理索引的映射。排序算法将在虚拟索引空间中创建升序顺序。您的索引映射将按照您所需的顺序在物理内存中排列。以下是索引映射的未经测试的草图：

private int mapVirtualToPhysical( int virtualIndex, int countElements ) {
    boolean isEvenIndex = ( 0 == (index % 2));
    int physicalIndex = isEvenIndex ? (index / 2) : (countElements - (index/2) - 1);
    return physicalIndex;
}

最好的方法是先进行一次初始排序，然后再进行O(n)次交换。但是，我还没有确定交换的顺序。到目前为止，我想到的最好的方法是将左侧排序，但右侧需要进行后续排序或使用堆栈。

- Andy Thomas

Answer 5

对于大量数据，您可以使用以下方法：在SortableEntry构造函数中，使用随机数生成器确定该特定条目将占据图表的哪一侧（左侧或右侧），以此来处理数据。

static final class SortableEntry<T>{

    Number value;
    Comparable<T> key;
    int hr;
    static Random rnd = new Random();

    public SortableEntry(Number value, Comparable<T> key){
        this.value = value;
        this.key = key;
        this.hr = rnd.nextInt(2) == 0 ? -1 : 1;  // here
    }
}

额外添加 hr 变量的目的是使任何“右”条目都大于任何“左”条目，反之亦然。如果两个比较条目的 hr 相同，则按实际的 key 进行比较，考虑 hr 的符号：

static final class SortableEntryComparator<T> implements Comparator<SortableEntry<T>> {

    @Override
    public int compare(SortableEntry<T> e1, SortableEntry<T> e2) {
        if (e1.hr == e2.hr) 
            return e1.hr < 0 ? e1.key.compareTo((T) e2.key) : e2.key.compareTo((T) e1.key);
        else 
            return e1.hr - e2.hr;
    }
}

现在进行一个小测试：

@Test
public void testSort() {
    List<Integer> keys = Arrays.asList(10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 
                                       12, 25, 31, 33, 34, 36, 39, 41, 26, 49,
                                       52, 52, 58, 61, 63, 69, 74, 83, 92, 98);
    List<SortableEntry<Integer>> entries = new ArrayList<>();
    for (Integer k : keys) {
        entries.add(new SortableEntry<Integer>(0, k)); 
    }
    entries.sort(new SortableEntryComparator<Integer>());
    System.out.println(entries);
}
// output: 
// [12, 26, 33, 36, 39, 40, 49, 50, 52, 60, 61, 63, 80, 90, 98, 100, 92, 83, 74, 70, 69, 58, 52, 41, 34, 31, 30, 25, 20, 10]
// the highest key (100) is not precisely in the center,
// but it will tend to occur in the center when dataset is large.

- Alex Salauyou

---

接近了，但是很遗憾可能会将所有低值（或可能是所有值）随机分配到图表的一侧，这样就会崩溃。 - Zack Newsham

@zack 对于大量数据集。我应该再重复一遍。对于大量数据集。对于大量数据集。你先说可以有一些随机性，现在又希望它严格对称。 - Alex Salauyou

随机性没问题，我不在乎每个元素在图表的哪一侧，只要大致对称即可。然而，将所有大值分配到图表的一侧是不可以的。我猜这是对随机性含义的误解。 - Zack Newsham

Answer 6

据我所见，您可能希望获得一个"平均距离"元组值，并按第一项"平均距离"对元组列表进行排序。

- JFPicard