|
|
|
быстродейсвенный алгоритм сортировки
|
|||
|---|---|---|---|
|
#18+
Имеется например лист ArrayList =[234,2143,23,542,2,42,254,3].(размер листа будет большой) Нужно его отсортировать причем, чтобы временная сложность была наименьшей должно использоваться мало памяти. Хотел использовать метод из класса Collections: Collections.sort(list); есть ли более лучший способ ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.06.2017, 16:01 |
|
||
|
быстродейсвенный алгоритм сортировки
|
|||
|---|---|---|---|
|
#18+
dimkalimitчтобы временная сложность была наименьшей должно использоваться мало памяти Фтопку "временную сложность". Нужна производительность - тратим память. Нужна память - теряем в производительность. Стандартный trade off. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.06.2017, 16:12 |
|
||
|
быстродейсвенный алгоритм сортировки
|
|||
|---|---|---|---|
|
#18+
dimkalimit, Можно существенно выиграть в производительности, если выкинуть обертки для целых чисел и перейти на массив и примитивы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.06.2017, 16:14 |
|
||
|
быстродейсвенный алгоритм сортировки
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.06.2017, 16:33 |
|
||
|
быстродейсвенный алгоритм сортировки
|
|||
|---|---|---|---|
|
#18+
Т.е. оптимальный вариант использовать quicksort ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.06.2017, 16:56 |
|
||
|
быстродейсвенный алгоритм сортировки
|
|||
|---|---|---|---|
|
#18+
dimkalimitТ.е. оптимальный вариант использовать quicksort ??? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.06.2017, 16:57 |
|
||
|
быстродейсвенный алгоритм сортировки
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.06.2017, 16:59 |
|
||
|
быстродейсвенный алгоритм сортировки
|
|||
|---|---|---|---|
|
#18+
dimkalimitТ.е. оптимальный вариант использовать quicksort В определённых обстоятельствах - да. В других, возможно, нет. Я же привел ссылку. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.06.2017, 17:02 |
|
||
|
быстродейсвенный алгоритм сортировки
|
|||
|---|---|---|---|
|
#18+
Если диапазон допустимых значений в списке небольшой, то лучше вообще не сортировать, а подсчитать количество вхождений каждого элемента. Потом "воссоздать" нужный список. Трудоемкость будет линейная (n), а не как у одного из алгоритмов быстрой сортировки n * log(n). Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.06.2017, 10:09 |
|
||
|
быстродейсвенный алгоритм сортировки
|
|||
|---|---|---|---|
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.06.2017, 10:13 |
|
||
|
быстродейсвенный алгоритм сортировки
|
|||
|---|---|---|---|
|
#18+
vas0Если диапазон допустимых значений в списке небольшой, то лучше вообще не сортировать, а подсчитать количество вхождений каждого элемента. Потом "воссоздать" нужный список. Трудоемкость будет линейная (n), а не как у одного из алгоритмов быстрой сортировки n * log(n). Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. не понял этого решения. Здесь же мы не получим отсортированный список ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.06.2017, 21:16 |
|
||
|
быстродейсвенный алгоритм сортировки
|
|||
|---|---|---|---|
|
#18+
dimkalimitне понял этого решения. Здесь же мы не получим отсортированный список ?vas0Потом "воссоздать" нужный список. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.06.2017, 21:56 |
|
||
|
|

start [/forum/topic.php?fid=59&msg=39473680&tid=2122831]: |
0ms |
get settings: |
11ms |
get forum list: |
13ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
90ms |
get topic data: |
12ms |
get forum data: |
2ms |
get page messages: |
54ms |
get tp. blocked users: |
1ms |
| others: | 249ms |
| total: | 438ms |

| 0 / 0 |
