Генерация случайных чисел без дубликатов значений для сортировки вставки

Question

Здравствуйте, я работал над сортировкой вставки по набору чисел. Я могу добавить их в массив для выполнения сортировки, но я не смог генерировать уникальные значения с большим набором чисел для выполнения сортировки (i: e) для 1000 значений. Есть ли какая-либо возможность, я могу генерировать уникальные случайные числа для выполняя сортировку без добавления значений в массив?

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

вы можете использовать Math.random(), а также добавить одно условие, которое будет проверять, массив содержит это число или нет, если не содержит, то добавьте в противном случае не добавляйте.

Answer 2

Одно простое решение с помощью 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 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() метод и этот полезный ответ:

Random shuffling of an array

Это имеет то преимущество, что это будет r un в O (n) времени (вместо потенциально бесконечного времени, если вы выбираете случайные числа, а затем только вставляете их, если их еще нет).

Edit: Вы можете также использовать встроенный метод перетасовки в Java https://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#shuffle(java.util.List)