Пользовательская сортировка алго / оптимизированная сортировка пузырьком


Я новичок и начал дайвинг в структуры и алгоритмы данных. Я был недавно учил пузырьковой сортировки, и я обнаружил, что оригинальный алгоритм сортировки пузырьком настолько неэффективно, поэтому я написал изменен, но простой вариант.

Алгоритм:

  1. Цикл через массив и хранения индекса максимального элемента
  2. Поменять местами последний элемент с максимальным элементом
  3. Сокращение общего цикла длины 1 и повторить

Код:

import java.util.Scanner;


class Methods extends Main
  {
    int[] getArray(int len)
      {
        int[] array = new int[len];

        for (int i = 0; i < array.length; i++)
          {
            array[i] = sc.nextInt();
          }
        return array;
      }



    int [] pushMaxSort(int[] arr)
      {
        int len = arr.length;

        while (len>0)
          {
            int max=arr[0];
            int index=0;
            for(int i=0; i<len;i++)
              {
                if(arr[i]>max)
                  {
                    max = arr[i];
                    index = i;
                  }
              }
            int temp = arr[len-1];
            arr[len-1] = arr[index];
            arr[index] = temp;
            len--;
          }

        return arr;
      }

    void printArr(int []arr)
      {
        System.out.println("sorted array :");
        for(int i=0;i<arr.length;i++)
          {
            System.out.print("\t" +arr[i]);
          }
      }

  }




class Main
  {
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args)
      {
        long t = System.currentTimeMillis();
        Methods o = new Methods();
        o.printArr(o.pushMaxSort(o.getArray(sc.nextInt())));
        long t2 = System.currentTimeMillis();
        System.out.println("\n\n time " + (t2-t));
      }
  }

Кроме того, мне нужно научиться описывать сложности (используя нотацию Большого о). Я смутно предполагаю, это \$о(н \журнал{н})\$ но, пожалуйста, дайте мне знать точное время.



158
1
задан 1 февраля 2018 в 11:02 Источник Поделиться
Комментарии
1 ответ

Дизайн не имеет никакого смысла с точки зрения объектно-ориентированных принципов:


  1. Отношение наследования между двумя классами имеет никакого логического смысла. Это, кажется, служат единственной цели делиться scanner экземпляр. Наследование-это больше чем механизм для обмена переменных. Он имеет приложение (ака бизнес) смысл. Он определяет "вид" отношения: Dog вид Animal.

  2. Имена классов сказать абсолютно ничего о том, что код делает. Ну, можно возразить, что Main служит программа начального пункта. Я видел этот "именования" в реальных Java-проектах, так что это сносно. Я бы назвал это что-то вроде ArraySorter. Это также приемлемо, чтобы добавить main() метод другие методы вместо того, чтобы положить в отдельный класс. Methods класс-это другое дело: там еще лучше имя, которое описывает то, что набор методов сделать. В заключение, это до вас Ли PushMaxSorter имеет свой собственный main() способ или храните его отдельно.

  3. Так, если мы посмотрим на Methods как PushMaxSorter то есть класс, который реализует свой улучшенная сортировка пузырьком алгоритм, то getArray() можно рассматривать как конструктор. и она должна принять Scanner экземпляр в качестве аргумента.

  4. Итак, из вышесказанного конструктор, мы приходим к выводу, что PushMaxSorter держит инт массив в качестве внутренней структуры данных. Поэтому метод сортировки должен принимать никаких аргументов и возвращает void и если вы хотите, вы можете добавить getArray() это "классический" геттер метод: позволяет получить доступ к переменной экземпляра.

  5. о printArr(): так что мы теперь можем сделать вывод, что этот метод также несет арг. Считается "лучшей parctice", что класс с структура данных (или просто куча переменных) будет иметь строковое представление своего внутреннего состояния посредством переопределения ObjecttoString() метод. Это позволяет вызывающему и. для вывода String написано.

Что касается сложности, я признаю это не моя компетенция. Однако, я не вижу никаких признаков экспоненциального итерации по структуре данных. Ваш алгоритм может улучшить производительность классической пузырьковой сортировки, но сложность заключалась в том, масштабирование: сравнение производительности же алгоритм на вход, которая увеличивается в размерах. Я бы сказал, что сложность здесь такая же, как в классическом пузырьковой сортировки, который является o(п^2)

Примечание: более надежная и расширяемая конструкция будет сказать, что вы должны отделить структуры данных алгоритм сортировки (так же, как платформы наборов Java), так что вы можете применить улучшенный алгоритм не только массив целых чисел. Но я думаю, что это "продвинутая" тема, которая требует более глубокого изучения современных принципов ОО.

4
ответ дан 1 февраля 2018 в 01:02 Источник Поделиться