Мне нужна помощь в сортировке массива в Java на основе частоты в этом конкретном способе - PullRequest
Новая
       9

Мне нужна помощь в сортировке массива в Java на основе частоты в этом конкретном способе

0 голосов
/ 31 октября 2019

нужна помощь для получения массива, подсчета частоты, помещения другого массива с индексом массива, действующим на число, и отдельным значением, действующим в качестве частоты в Java

Вы можете отсортировать большой массив из m целых чисел, которыев диапазоне от 1 до n с помощью подсчета массива из n записей для подсчета количества вхождений каждого целого числа в массиве. Например, рассмотрим следующий массив A из 14 целых чисел в диапазоне от 1 до 9 (обратите внимание, что в этом случае m = 14 и n = 9): 

9 2 4 8 9 4 3 2 8 1 2 7 2 5

Формирует счетчик массива из 9такие элементы, что count [i-1] содержит количество раз, которое я встречаю в массиве для сортировки. Таким образом, число равно 

1 4 1 2 1 0 1 2 2

В частности,

  • count[0] = 1, поскольку 1 встречается один раз в A.
  • count [1] = 4, так как происходит 24 раза в A.
  • count [2] = 1, поскольку 3 встречается один раз в A.
  • count [3] = 2, поскольку 4 встречается 2 раза в A.

Используйте массив count для сортировки исходного массива A. Реализуйте этот алгоритм сортировки в функции 

public static void countingSort(int[] a, int n )

и проанализируйте время его наихудшего случая в терминах m (длина массива a) и n,После вызова countingSort () a должен быть отсортированным массивом (не сохранять результат сортировки во временном массиве).

edit: это то, что я пробовал 

 public static void countingSort1(int[] a, int n) {
    int [] temp = new int[n];
    int [] temp2 = new int[n];
    int visited = -1;
    for (int index = 0; index < n; index++) {
        int count = 1;
        for (int j = index +1; j < n; j++) {
            if(a[index] == a[j]) {
                count++;
                temp[j] = visited;
            }

        }
        if (temp[index]!= visited) {
            temp[index] = count;
        }
    }
    for(int i = 1; i < temp.length; i++) {
        if (temp[i] != visited) {
            System.out.println("  " +a[i] + "  |   " +temp[i]);
        }
    }

Просто чтобыпосчитать частоту, но я думаю, что я делаю это неправильно

1 Ответ

0 голосов
/ 31 октября 2019

Что-то вроде приведенного ниже должно работать:

  • Поскольку вы уже знаете, какое наибольшее значение, в примере 9, создайте частотный массив с пространством для девяти элементов.
  • переберите ваш входной массив и для каждого найденного значения увеличьте значение на индекс значения в вашем частотном массиве на один
  • создайте счетчик для индекса и инициализируйте его с 0
  • итерируйте ваш частотный массив во вложенном цикле и замените значения во входном массиве на индексы вашего частотного массива.

Я оставляю вам анализ сложности 

public static void countingSort(int[] a, int n ){
    //counting
    int[] freq = new int[n];
    for(int i = 0; i<a.length; i++){
        freq[a[i]-1]++;
    }
    //sorting
    int index = 0;
    for(int i = 0; i< freq.length; i++){
        for(int j = 0;j < freq[i];j++){
            a[index++]= i+1;                
        }            
    }
    System.out.println(Arrays.toString(a));
}
...