您有重量为的项目：

• 物料A，重量42
• 物料B，重量5
• 物料C，重量96
• 物品D，重量33

首先将所有重量相加：42 + 5 + 96 + 33 = 176个
现在，从0到权重之和之间选取一个随机数r：0〈= r〈176。我使用了整数，但是如果需要的话，你可以使用实数。
将r与权重定义的范围进行比较：

• 0〈= r〈42：选择项目A。
• 42〈= r〈47（= 42 + 5）：选择项目B。
• 47〈= r〈143（= 47 + 96）：选择项目C。
• 143〈= r〈176（= 143 + 33）：选择项目D。

当你挑选完第一件物品后，对剩下的三件物品重复这个过程，并减少所有物品的重量。不断重复，直到没有更多的物品可供挑选。

这似乎很有效：

// Can do a weighted sort on weighted items.
public interface Weighted {
    int getWeight();
}

/**
 * Weighted sort of an array - orders them at random but the weight of each
 * item makes it more likely to be earlier.
 *
 * @param values
 */
public static void weightedSort(Weighted[] values) {
    // Build a list containing as many of each item to make up the full weight.
    List<Weighted> full = new ArrayList<>();
    for (Weighted v : values) {
        // Add a v weight times.
        for (int i = 0; i < v.getWeight(); i++) {
            full.add(v);
        }
    }
    // Shuffle it.
    Collections.shuffle(full);
    // Roll them out in the order required.
    int i = 0;
    do {
        // Get the first one in the shuffled list.
        Weighted next = full.get(0);
        // Put it back into the array.
        values[i++] = next;
        // Remove all occurrences of that one from the list.
        full.remove(next);
    } while (!full.isEmpty());
}

// A bunch of weighted items.
enum Heavies implements Weighted {

    Rare(1),
    Few(3),
    Common(6);
    final int weight;

    Heavies(int weight) {
        this.weight = weight;
    }

    @Override
    public int getWeight() {
        return weight;
    }
}

public void test() {
    Weighted[] w = Heavies.values();
    for (int i = 0; i < 10; i++) {
        // Sort it weighted.
        weightedSort(w);
        // What did we get.
        System.out.println(Arrays.toString(w));
    }
}

基本上，对于每一个要排序的项目，我都会根据需要多次将其添加到一个新列表中，然后对列表进行洗牌，将最上面的项目拉出，并从剩余的项目中清除所有出现的项目。
上次测试运行生成：

[Rare, Common, Few]
[Common, Rare, Few]
[Few, Common, Rare]
[Common, Few, Rare]
[Common, Rare, Few]
[Few, Rare, Common]

这似乎是正确的。
NB -至少在以下条件下，该算法将失败：
1.原始数组中多次包含同一对象。
1.这些物品的重量大得吓人。
1.零或负权重几乎肯定会影响结果。

已添加

这实现了Rossum的想法--请务必将算法归功给予他。

public static void weightedSort2(Weighted[] values) {
    // Calculate the total weight.
    int total = 0;
    for (Weighted v : values) {
        total += v.getWeight();
    }
    // Start with all of them.
    List<Weighted> remaining = new ArrayList(Arrays.asList(values));
    // Take each at random - weighted by it's weight.
    int which = 0;
    do {
        // Pick a random point.
        int random = (int) (Math.random() * total);
        // Pick one from the list.
        Weighted picked = null;
        int pos = 0;
        for (Weighted v : remaining) {
            // Pick this ne?
            if (pos + v.getWeight() > random) {
                picked = v;
                break;
            }
            // Move forward by that much.
            pos += v.getWeight();
        }
        // Removed picked from the remaining.
        remaining.remove(picked);
        // Reduce total.
        total -= picked.getWeight();
        // Record picked.
        values[which++] = picked;
    } while (!remaining.isEmpty());
}

public class RandomPriorityQueue {

    private TreeMap<Integer, List<WeightedElement>> tree = new TreeMap();
    private Random random = new Random();

    public void add(WeightedElement e) {
        int priority = random.nextInt(e.getWeight());
        if (tree.containsKey(priority)) {
            List<WeightedElement> list = new LinkedList();
            list.add(e);
            tree.put(priority, list);
        } else {
            List<WeightedElement> list = tree.get(priority);
            list.add(random.nextInt(list.size()), e);
        }
    }

    public WeightedElement poll() {
        Map.Entry<Integer, List<WeightedElement>> entry = tree.lastEntry();
        if (entry == null){
            return null;
        }
        List<WeightedElement> list = entry.getValue();
        if (list.size() == 1){
            tree.remove(entry.getKey());
        }
        return list.remove(0);
    }
}

当然，如果我们重写TreeMap，使其允许我们添加重复键，我们会有更好性能。

我已经找到了另一个答案的解决方案-现在找不到，但它使用指数分布：
对于权重为w_i的i-th元素，分配一个键power(random(0,1),1.0/w_i)（伪代码），然后按键对元素进行排序，这将花费O(n*log(n))时间，复杂度与实际权重无关。

无论如何，对于N个项目，你将需要N-1个随机数（至少）。然后，让我们思考有效的方法来选择项目的随机数。
如果项目不是太多，我会使用迭代的方法，类似于你的递归方法。我会添加布尔标记到项目，跳过在以前的迭代中选择的项目。当我在当前迭代中选择一个项目时，我会将它的标记设置为true，下次我将从计算中跳过它。从和中减去它的权重，并进行下一次迭代。
如果项目的数量很大，同一个集合将被多次使用，那么不同的方法是更好的。使他们排序的列表，并使用这个列表的副本在您的递归方法。并在每个递归步骤-二分搜索，然后删除选择的项目。
实际上，最后一个也可以迭代完成。