排序算法

Question

我有一个数字列表，例如：list=[10,50,90,60]

我想对任意两个元素的和进行排序。以及它们的组合。

例如:输出列表应包含10+50,10+90,10+60,50+90,50+60,90+60 (按升序排序)。

即outputlist=[60,10,50,70,10,60....

类似于排列和组合中的握手问题

有谁能给点提示吗？

Answer 1

算法只是因为它是家庭作业。我会从一些简单的东西开始。根据您的示例，您不需要列表与自身的完全联接，而是一个列表，其中element1和element2与element2和element1相同。

list = [10,50,90,60].
// newlist is an object containing first and second element.
newlist = [].
for i1 = 1 to list.size() - 1:
    for i2 = i1 + 1 to list.size():
        newlist.append (list[i1], list[i2]).
sort newlist based on sum of fields.

换句话说，只需创建一个全新的列表，包含您需要的所有可能性，然后根据总和对其进行排序。

至于在Java中使用什么类型，原始列表可以只是一个int数组。我会选择一个独立的类来容纳每个组合(一个简单的类来容纳组成组合的两个int就足够了)和一个数组来容纳所有的东西。

实际的组合数组大小可以预先计算，示例组合如下：

size = 2 (ab    ) : (ab)             = 1
size = 3 (abc   ) : (ab,ac,
                        bc)          = 3
size = 4 (abcd  ) : (ab,ac,ad,
                        bc,bd,
                           cd)       = 6
size = 5 (abcde ) : (ab,ac,ad,ae,
                        bc,bd,be,
                           cd,ce,
                              de)    = 10
size = 6 (abcdef) : (ab,ac,ad,ae,af,
                        bc,cd,be,bf,
                           cd,ce,cf,
                              de,df,
                                 ef) = 15

因此，如果有N元素，就有N-1 + N-2 + N-3 + ... + 1组合，实际上就是(N x N - N) / 2或N x (N-1) / 2。知道了这一点，您实际上不需要任何可扩展的集合类(如Vector)，您只需使用如下内容：

int[] list = {10,50,90,60};
int n = list.length;
myclass[] comb_array = new myclass[n*(n-1)/2];

然后，使用与上面的伪代码类似的代码填充该数组的每个元素后，Java提供了public static void sort(Object[] a, Comparator c)，您可以使用它对实际的数组进行排序。

或者(因为这是家庭作业)，你可以实现你自己的排序功能，甚至是像冒泡排序这样的原始功能。由于Java提供了丰富的数据类型和方法，因此对于生产代码，我永远不会建议这样做，但对于家庭作业来说，这可能是可以接受的。

更新:实际上，我只是注意到作业标签是由其他人添加的，而不是OP。现在我完全意识到这很可能是家庭作业，但我们不能确定。既然SO是一个提供答案的地方，我将在下面提供一个实现。

公平警告：如果你想学习如何解决问题，从我上面提供的内容开始，在你至少花了几天时间试图弄清楚之前，不要阅读下面的内容。如果你只是想要一个问题的解决方案，那么请随意使用下面的代码作为起点。

如果你试图在家庭作业的情况下冒充你自己的工作，你会失败的，因为如果你认为你的教育者不能像你一样容易地看到这个网站，那你就太愚蠢了。你在那个案子里得到的一切都是你应得的，我不会同情你的。

我不会费心提供冒泡排序，因为它只适用于家庭作业问题，如果是这样的话，你就不会在这里阅读了，对吗？

首先，一个双整数类DoubleInt.java。这不是最难理解的，我也没有考虑过真正的封装(带有setter和getter的私有数据)，因为它只是一个helper类，不需要这样的奢侈品:-)

public class DoubleInt {
    public int n1, n2;
    public DoubleInt (int i1, int i2) { n1 = i1; n2 = i2; }
}

接下来，进行组合和排序的实际代码是Abhishek.java

// Need both these for sorting.

import java.util.Arrays;
import java.util.Comparator;

public class Abhishek implements Comparator<DoubleInt> {
    // The list of combinations.

    private DoubleInt[] dstList = null;

    // Inject a list to make the combinations out of.

    public void inject (int[] arr) {
        // This is from the algorithm given in the text above.

        dstList = new DoubleInt[arr.length * (arr.length - 1) / 2];
        for (int d = 0, s1 = 0; s1 < arr.length - 1; s1++)
            for (int s2 = s1 + 1; s2 < arr.length; s2++)
                dstList[d++]  = new DoubleInt(arr[s1], arr[s2]);
        Arrays.sort(dstList, this);
    }

    // Comparison function for Arrays.sort().

    public int compare (DoubleInt d1, DoubleInt d2) {
        if (d1.n1 + d1.n2 > d2.n1 + d2.n2) return 1;
        if (d1.n1 + d1.n2 < d2.n1 + d2.n2) return -1;
        return 0;
    }

    // Dump the array in index order for checking.

    public void dump() {
        for (int i = 0; i < dstList.length; i++) {
            System.out.println (i + ": " +
                // Note to educators: this
                // code plagiarized
                // from stackoverflow.com
                (dstList[i].n1 + dstList[i].n2) + " (" +
                dstList[i].n1 + "," + dstList[i].n2 + ")");
        }
    }

    // Test program to combine, sort and check.

    public static void main (String[] args) {
        abhishek a = new abhishek();
        a.inject (new int[] {10,50,90,60});
        a.dump();
    }
}

输出结果是(格式化后看起来更好)：

0:  60 (10,50)
1:  70 (10,60)
2: 100 (10,90)
3: 110 (50,60)
4: 140 (50,90)
5: 150 (90,60)

它按各个值的总和排序。将注入管路更改为a.inject (new int[] {10,3,50,90,2,60,12,24,36,1});会导致：

 0:   3 ( 2, 1)          23:  60 (10,50)
 1:   4 ( 3, 1)          24:  60 (24,36)
 2:   5 ( 3, 2)          25:  61 (60, 1)
 3:  11 (10, 1)          26:  62 (50,12)
 4:  12 (10, 2)          27:  62 ( 2,60)
 5:  13 (10, 3)          28:  63 ( 3,60)
 6:  13 (12, 1)          29:  70 (10,60)
 7:  14 ( 2,12)          30:  72 (60,12)
 8:  15 ( 3,12)          31:  74 (50,24)
 9:  22 (10,12)          32:  84 (60,24)
10:  25 (24, 1)          33:  86 (50,36)
11:  26 ( 2,24)          34:  91 (90, 1)
12:  27 ( 3,24)          35:  92 (90, 2)
13:  34 (10,24)          36:  93 ( 3,90)
14:  36 (12,24)          37:  96 (60,36)
15:  37 (36, 1)          38: 100 (10,90)
16:  38 ( 2,36)          39: 102 (90,12)
17:  39 ( 3,36)          40: 110 (50,60)
18:  46 (10,36)          41: 114 (90,24)
19:  48 (12,36)          42: 126 (90,36)
20:  51 (50, 1)          43: 140 (50,90)
21:  52 (50, 2)          44: 150 (90,60)
22:  53 ( 3,50)          

你可以看到重复求和的行为(13，60和62) --如果我没记错的话，Java数组排序是稳定的。

Answer 2

首先是基本选择:您可以先生成排列，然后对其进行排序，或者以从头开始对其进行排序的方式生成它们。如果性能不是很重要，我会选择第一个，因为它更容易。

生成排列很简单，然后可以使用Collections.sort对它们进行排序。