插入排序无重复值的随机数生成[duplicate]

Question

你好，我一直在研究数字集合的插入排序。我可以将它们添加到数组中以执行排序，但是我无法生成具有大量数字的唯一值来执行1000个值的排序（即：e）。我是否有可能生成唯一的随机数来执行排序，而不向数组中添加值？

public class InsertionBinary
{

    public static void main(String Args [])
    {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 24};
        print(nums);
        insertionsort(nums);
        print(nums);
        int loc = binarySearch(nums, 3);
        System.out.println("2 is in position" + loc);
    }

    private static void swap(int[] list, int from, int to)
    {
        int temp = list[from];
        list[from] = list[to];
        list[to] = temp;
    }

    private static void print(int[] list)
    {
        for (int i = 0; i < list.length - 1; i++)
            System.out.
        print(list[i] + ", ");
        System.out.println(list[list.length - 1]);
    }


    private static void insertionsort(int[] list)
    {
        int key;
        int spot;
        for (int pass = 1; pass < list.length; pass++)
        {
            key = list[pass];
            for (spot = pass - 1; spot >= 0 && list[spot] > key; spot--)
                list[spot + 1] = list[spot];
            list[spot + 1] = key;

        }
    }
}

Answer 1

一个简单的解决方案是使用Set生成随机数，并将它们插入集合中，Set不允许重复的数字，比如：

Random rnd= new Random();
Set<Integer> randomSet = new LinkedHashSet<Integer>();
while (randomSet.size() < 1000)
{
    Integer randomNum = rnd.nextInt(max) + 1;
    randomSet.add(randomNum);
}

但是理论上生成这样一个集合可能需要无限的时间，但是它的概率很低。

Answer 2

您可以使用Math.random（）并添加一个条件，该条件将检查，数组是否包含该数字，如果不包含则添加，否则不添加。

Answer 3

如果您只需要一组用于排序的唯一数字，我想说最简单的方法是使用循环生成一个大小为N的数组，其中包含数字0到N-1（或1到N，如果您愿意）：

int size = 1000;
int[] nums = new int[size];
for(int i = 0; i < size; i++) {
    nums[i] = i;
}

然后你需要做的就是将其洗牌，你可以使用已经实现的swap（）方法和以下有用的答案：

数组的随机洗牌

这样做的好处是，它将在O（n）时间内运行（如果你选择随机数，然后只在它们不存在的情况下插入它们，那么它可能是无限时间）。

编辑：您也可以使用Java内置的shuffle方法https://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#shuffle（java.util.列表）