|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
28.11.2010, 08:26 | #1 |
Форумчанин
Регистрация: 29.10.2009
Сообщений: 259
|
Самая быстрая сортировка динамической структуры данных
Добрый день\вечер\ночь. Стоит задача: "имеется динамическая структура данных. Реализовать для неё наиболее оптимальный метод сортировки". Понятно, что в C# у стандартного класса List есть метод Sort(), но данная динамическая структура никак не привязывается к этому классу, поэтому нужно все делать "своими ручками". Знаю некоторые элементарные сортировки, которые можно применить в том числе и к динамическим структурам: "пузырьковая"(одна из наиболее медленных сортировок даже для массивов), "метод вставок" и ещё несколько штук. Подскажите, какой метод лучше использовать для сортировки, может за последние годы были разработаны более рациональные методы, чем "пузырьковая" сортировка и сортировка "методом вставок"?
Из всех классических книг, посвященных программированию, ненавижу всего одну - русский перевод книги Роберта Седжвика-"Фундаментальные алгоритмы C++". Предпочитаю читать её в оригинале.
|
28.11.2010, 10:02 | #2 |
Наркоман самоучка
Форумчанин
Регистрация: 22.07.2007
Сообщений: 276
|
http://algolist.manual.ru/sort/faq/q12.php
В общем случае: Малые массивы/списки - менее 20 элементов => InsertSort Большие массивы => QuickSort Длинные списки/файлы => MergeSort Для сортировок сравнениями давно доказана теорема о максимальном быстродействии: Omega(nlogn) операций. Если количество возможных различных ключей ненамного больше их общего числа - то наибыстрейшей будет распределяющая сортировка и ее вариации: Radix sort - 'радиксная', или 'распределяющая' сортировка. Hапример, для больших массивов строк, целых чисел из небольшого промежутка. Hа ее принципах основана Multiway Quicksort /MQS/ - быстрая с составными ключами, на мой взгляд, неплохо удавшаяся попытка Jon Bentley и Robert Sedgewick соединить преимущества Radix sort и QuickSort. Есть и другие шаги в этом направлении.. Существует еще очень много различных сортировок, которые выходят за рамки FAQ'а. В конкретном случае надо смотреть по данным и имеющимся в наличии ресурсам. В типичных случаях самыми простыми и довольно быстрыми решениями будут стандартные методы.
#include <мозг.h>
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
быстрая сортировка настолько быстрая | Serg12 | Помощь студентам | 8 | 28.03.2010 21:31 |
Быстрая сортировка | lennon | Общие вопросы C/C++ | 0 | 08.10.2009 23:23 |
Быстрая сортировка | Syltan | Общие вопросы C/C++ | 7 | 18.09.2009 17:35 |
Быстрая сортировка списка | ManU | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 08.12.2008 11:57 |
какая из трех сортировок (обменная,исчерпыванием,выбором) самая быстрая? | Cyberbest | Помощь студентам | 2 | 26.04.2008 10:34 |