Асимптотическая временная сложность и пространственная сложность для MSD Radix-сортировки - PullRequest
Новая
       20

Асимптотическая временная сложность и пространственная сложность для MSD Radix-сортировки

0 голосов
/ 26 марта 2019

Я реализовал сортировку MSD Radix с помощью Интернета. Моя домашняя работа просит меня определить асимптотическую временную сложность и пространственную сложность для этой версии радикальной сортировки. Но я понятия не имею об этом. Так может кто-нибудь помочь мне с этим?

открытый класс RadixSort {

public static void radix(String arr[])
{
    msdRadix(arr, 0 , arr.length, 0);
}

public static void msdRadix(String arr[], int low, int high, int d)
{
    if(high <= low+1) 
        return;

    int count[] = new int[256+1];
    String temp[] = new String[256+1];

    for(int i = 0; i < arr.length; i++)
        count[arr[i].charAt(d)+1]++;

    for(int k = 1; k < 256; k++)
        count[k] += count[k-1];

    for(int i = 0; i < arr.length; i++)
        temp[count[arr[i].charAt(d)]++] = arr[i];

    for(int i = 0; i < arr.length; i++)
        arr[i] = temp[i];

    for(int i = 0; i < arr.length; i++)
        msdRadix(arr, 1+count[i], 1+count[i+1], d+1);
}

public static void main(String args[])
{
    String[] arr = {"baa","abb","bbb","aba","bba","aab","aaa"}; // my string array to be sorted by radix sort method.

    radix(arr); // calling radix-sort method

    for(int i = 0; i < arr.length-1; i++)
        System.out.print(arr[i]+", ");
    System.out.println(arr[arr.length-1]);
}

}

...