Я использую Queue Abstract Data Type, который основан на Single Linked List. Я хочу сортировать данные, которые Queue хранит тремя способами: сначала с сортировкой слияния, второй с быстрой сортировкой, третий с сортировкой кучи. Так может ли кто-нибудь помочь в этом?Использование алгоритмов сортировки в очереди?
Обычно очередь сортируется по порядку вставки - элементы сортируются по порядку, в который они были вставлены в очередь. Похоже, вы хотите нарушить необходимое качество очереди.
Я только собираюсь покрыть сортировку слияния с этим ответом. Надеемся, что другие будут охватывать другие алгоритмы, или вы можете сами их вывести.
Один связанный список можно рассматривать как список списков, просто зная, когда заканчивается один список, а другой начинается. Для сортировки слияния вам нужно начать с отсортированных списков - если каждый список имеет длину 1, он сортируется просто потому, что другой порядок невозможен. Слияние двух связанных списков в одно легко - вы берете наименьший элемент из каждого из двух списков и связываете его с новым списком, пока оба списка не будут исчерпаны. Итак, для первого прохода вы разбиваете список на подсписные буквы длины 1 и объединяете их в подсписках длины 2. Второй проход вы объединяете подсписные буквы длины 2 в подсписные буквы длины 4. Каждый проход удваивает размер отсортированных подписок , Вы закончили, когда размер отсортированного подсписок больше или равен размеру всего вашего списка.
Что вам нужно, в частности, вам нужна помощь? –
@OliCharlesworth Не знаю, где в очереди или где деактивировать мои алгоритмы сортировки. – noDispName
Один простой способ сделать это - сбросить очередь в обычный массив, выполнить сортировку по массиву и затем перенести все обратно в очередь. –