Достигает ли этот метод асимптотической записи O (n log n)? - PullRequest
0 голосов
/ 27 октября 2019

Метод вызывается в классе, который использует универсальные объекты.

Я пытаюсь правильно понять, как максимизировать эффективность кода путем сокращения времени выполнения до O (n log n). Я знаю, что методы быстрой сортировки могут иногда достигать наименьшей эффективности O (n ^ 2), но я также исследовал, что в среднем правильно реализованный метод быстрой сортировки должен в среднем достигать времени выполнения O (n log n).

public void quickSort(int low, int high)
    {
        if (data == null || length() == 0)
        return;
        if (low >= high)
        return;

        int middle = low + (high - low)/2;
        E pivot = data[middle];

        int i = low; 
        int j = high;
        if (i < j)
        {
            while (((Comparable)data[i]).compareTo(pivot) < 0)
            {
                i++;
            }
            while(((Comparable)data[j]).compareTo(pivot) > 0)
            {
                j--;
            }

            if (i <= j)
            {
                E temp = data[i];
                data[i] = data[j];
                data[j] = temp;
                i++;
                j--;
            }
        }
        if (low < j)
            quickSort(low, j);
        if (high > i)
            quickSort(i,high);
    }
...