powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Java [игнор отключен] [закрыт для гостей] / быстродейсвенный алгоритм сортировки
13 сообщений из 13, страница 1 из 1
быстродейсвенный алгоритм сортировки
    #39473240
dimkalimit
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Имеется например лист ArrayList =[234,2143,23,542,2,42,254,3].(размер листа будет большой)

Нужно его отсортировать причем, чтобы временная сложность была наименьшей должно использоваться мало памяти.
Хотел использовать метод из класса Collections: Collections.sort(list);
есть ли более лучший способ ?
...
Рейтинг: 0 / 0
быстродейсвенный алгоритм сортировки
    #39473247
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dimkalimitчтобы временная сложность была наименьшей должно использоваться мало памяти
Фтопку "временную сложность". Нужна производительность - тратим память. Нужна память - теряем в производительность. Стандартный trade off.
...
Рейтинг: 0 / 0
быстродейсвенный алгоритм сортировки
    #39473249
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dimkalimit,

Можно существенно выиграть в производительности, если выкинуть обертки для целых чисел и перейти на массив и примитивы.
...
Рейтинг: 0 / 0
быстродейсвенный алгоритм сортировки
    #39473269
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
быстродейсвенный алгоритм сортировки
    #39473305
dimkalimit
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Т.е. оптимальный вариант использовать quicksort
...
Рейтинг: 0 / 0
быстродейсвенный алгоритм сортировки
    #39473308
dimkalimit
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
dimkalimitТ.е. оптимальный вариант использовать quicksort
???
...
Рейтинг: 0 / 0
быстродейсвенный алгоритм сортировки
    #39473311
Фотография Usman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dimkalimit,

YouTube Video
...
Рейтинг: 0 / 0
быстродейсвенный алгоритм сортировки
    #39473314
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dimkalimitТ.е. оптимальный вариант использовать quicksort
В определённых обстоятельствах - да. В других, возможно, нет. Я же привел ссылку.
...
Рейтинг: 0 / 0
быстродейсвенный алгоритм сортировки
    #39473549
vas0
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если диапазон допустимых значений в списке небольшой, то лучше вообще не сортировать, а подсчитать количество вхождений каждого элемента. Потом "воссоздать" нужный список.

Трудоемкость будет линейная (n), а не как у одного из алгоритмов быстрой сортировки n * log(n).

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 2, 2, 1};
        int[] b = {0, 0, 0, 0};

        for (int elem : a) {
            b[elem]++;
        }

        for (int elem : b) {
            System.out.print(elem + " ");
        }
    }
...
Рейтинг: 0 / 0
быстродейсвенный алгоритм сортировки
    #39473551
Фотография Usman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
vas0,

Напомнили про bitmap .
...
Рейтинг: 0 / 0
быстродейсвенный алгоритм сортировки
    #39473667
dimkalimit
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
vas0Если диапазон допустимых значений в списке небольшой, то лучше вообще не сортировать, а подсчитать количество вхождений каждого элемента. Потом "воссоздать" нужный список.

Трудоемкость будет линейная (n), а не как у одного из алгоритмов быстрой сортировки n * log(n).

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 2, 2, 1};
        int[] b = {0, 0, 0, 0};

        for (int elem : a) {
            b[elem]++;
        }

        for (int elem : b) {
            System.out.print(elem + " ");
        }
    }



не понял этого решения. Здесь же мы не получим отсортированный список ?
...
Рейтинг: 0 / 0
быстродейсвенный алгоритм сортировки
    #39473672
Фотография Usman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dimkalimitне понял этого решения. Здесь же мы не получим отсортированный список ?vas0Потом "воссоздать" нужный список.
...
Рейтинг: 0 / 0
быстродейсвенный алгоритм сортировки
    #39473680
Фотография Usman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
13 сообщений из 13, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / быстродейсвенный алгоритм сортировки
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]