Этот метод может быть более сложным, если элементы изначально расположены в массиве. В этом случае, необходимо перемещать элементы из массива в связный список и обратно в массив после завершения сортировки. Для создания связного списка также требуется дополнительная память. Следующий код демонстрирует алгоритм блочной сортировки с применением связных списков:
Public Sub LinkBucketSort(ListTop As ListCell)
Dim count As Long
Dim min_value As Long
Dim max_value As Long
Dim Value As Long
Dim item As ListCell
Dim nxt As ListCell
Dim bucket() As New ListCell
Dim value_scale As Double
Dim bucket.num As Long
Dim i As Long
Set item = ListTop.NextCell
If item Is Nothing Then Exit Sub
' Подсчитать элементы и найти значения min и max.
count = 1
min_value = item.Value
max_value = min_value
Set item = item.NextCell
Do While Not (item Is Nothing)
count = count + 1
Value = item.Value
If min_value > Value Then min_value = Value
If max_value < Value Then max_value = Value
Set item = item.NextCell
Loop
' Если min_value = max_value, значит, есть единственное
' значение, и список отсортирован.
If min_value = max_value Then Exit Sub
' Если в списке не более, чем CutOff элементов,
' завершить сортировку процедурой LinkInsertionSort.
If count <= CutOff Then
LinkInsertionSort ListTop
Exit Sub
End If
' Создать пустые блоки.
ReDim bucket(1 To count)
value_scale = _
CDbl(count - 1) / _
CDbl(max_value - min_value)
' Разместить элементы в блоках.
Set item = ListTop.NextCell
Do While Not (item Is Nothing)
Set nxt = item.NextCell
Value = item.Value
If Value = max_value Then
bucket_num = count
Else
bucket_num = _
Int((Value - min_value) * _
value_scale) + 1
End If
Set item.NextCell = bucket (bucket_num).NextCell
Set bucket(bucket_num).NextCell = item
Set item = nxt
Loop
' Рекурсивная сортировка блоков, содержащих
' более одного элемента.
For i = 1 To count
If Not (bucket(i).NextCell Is Nothing) Then _
LinkBucketSort bucket(i)
Next i
' Объединить отсортированные списки.
Set ListTop.NextCell = bucket(count).NextCell
For i = count - 1 To 1 Step -1
Set item = bucket(i).NextCell
If Not (item Is Nothing) Then
Do While Not (item.NextCell Is Nothing)
Set item = item.NextCell
Loop
Set item.NextCell = ListTop.NextCell
Set ListTop.NextCell= bucket(i).NextCell
End If
Next i
End Sub
=========257-258
Эта версия блочной сортировки намного быстрее, чем сортировка вставкой с использованием связных списков. В тесте на компьютере с процессором Pentium с тактовой частотой 90 МГц сортировке вставкой потребовалось 6,65 секунд для сортировки 2000 элементов, блочная сортировка заняла 1,32 секунды. Для более длинных списков разница будет еще больше, так как производительность сортировки вставкой порядка O(N2).
Блочную сортировку также можно реализовать в массиве, используя идеи подобные тем, которые используются при сортировке подсчетом. При каждом вызове алгоритма, вначале подсчитывается число элементов, которые относятся к каждому блоку. Потом на основе этих данных рассчитываются смещения во временном массиве, которые затем используются для правильного расположения элементов в массиве. В конце концов, блоки рекурсивно сортируются, и отсортированные данные перемещаются обратно в исходный массив.
Public Sub ArrayBucketSort(List() As Long, Scratch() As Long, _
min As Long, max As Long, NumBuckets As Long)
Dim counts() As Long
Dim offsets() As Long
Dim i As Long
Dim Value As Long
Dim min_value As Long
Dim max_value As Long
Dim value_scale As Double
Dim bucket_num As Long
Dim next_spot As Long
Dim num_in_bucket As Long
' Если в списке не более чем CutOff элементов,
' закончить сортировку процедурой SelectionSort.
If max - min + 1 < CutOff Then
Selectionsort List(), min, max
Exit Sub
End If
' Найти значения min и max.
min_value = List(min)
max_value = min_value
For i = min + 1 To max
Value = List(i)
If min_value > Value Then min_value = Value
If max_value < Value Then max_value = Value
Next i
' Если min_value = max_value, значит, есть единственное
' значение, и список отсортирован.
If min_value = max_value Then Exit Sub
' Создать пустой массив с отсчетами блоков.
ReDim counts(l To NumBuckets)
value_scale = _
CDbl (NumBuckets - 1) / _
CDbl (max_value - min_value)
' Создать отсчеты блоков.
For i = min To max
If List(i) = max_value Then
bucket_num = NumBuckets
Else
bucket_num = _
Int((List(i) - min_value) * _
value_scale) + 1
End If
counts(bucket_num) = counts(bucket_num) + 1
Next i
' Преобразовать отсчеты в смещение в массиве.
ReDim offsets(l To NumBuckets)
next_spot = min
For i = 1 To NumBuckets
offsets(i) = next_spot
next_spot = next_spot + counts(i)
Next i
' Разместить значения в соответствующих блоках.
For i = min To max
If List(i) = max_value Then
bucket_num = NumBuckets
Else
bucket_num = _
Int((List(i) - min_value) * _
value_scale) + 1
End If
Scratch (offsets (bucket_num)) = List(i)
offsets(bucket_num) = offsets(bucket_num) + 1
Next i
' Рекурсивная сортировка блоков, содержащих
' более одного элемента.
next_spot = min
For i = 1 To NumBuckets
If counts(i) > 1 Then ArrayBucketSort _
Scratch(), List(), next_spot, _
next_spot + counts(i) - 1, counts(i)
next_spot = next_spot + counts(i)
Next i
' Скопировать временный массив назад в исходный список.
For i = min To max
List(i) = Scratch(i)
Next i
End Sub
Из‑за накладных расходов, которые требуются для работы со связными списками, эта версия блочной сортировки работает намного быстрее, чем версия с использованием связных списков. Тем не менее, используя методы работы с псевдоуказателями, описанные во 2 главе, можно улучшить производительность версии с использованием связных списков, так что обе версии станут практически эквивалентными по скорости.
Новую версию также можно сделать еще быстрее, используя функцию API MemCopy для копирования элементов из временного массива обратно в исходный список. Эта усовершенствованную версию алгоритма демонстрирует программа FastSort.
===========259-261
В таб. 9.4 приведены преимущества и недостатки алгоритмов сортировки, описанных в этой главе, из которых можно вывести несколько правил, которые могут помочь вам выбрать алгоритм сортировки.
Эти правила, изложенные в следующем списке, и информация в табл. 9.4 может помочь вам подобрать алгоритм, который обеспечит максимальную производительность:
* если вам нужно быстро реализовать алгоритм сортировки, используйте быструю сортировку, а затем при необходимости поменяйте алгоритм;
* если более 99 процентов списка уже отсортировано, используйте пузырьковую сортировку;
* если список очень мал (100 или менее элементов), используйте сортировку выбором;
* если значения находятся в связном списке, используйте блочную сортировку на основе связного списка;
* если элементы в списке — целые числа, разброс значений которых невелик (до нескольких тысяч), используйте сортировку подсчетом;
* если значения лежат в широком диапазоне и не являются целыми числами, используйте блочную сортировку на основе массива;
* если вы не можете тратить дополнительную память, которая требуется для блочной сортировки, используйте быструю сортировка
Если вы знаете структуру данных и различные алгоритмы сортировки, вы можете выбрать алгоритм, наиболее подходящий для ваших нужд.
@Таблица 9.4. Преимущества и недостатки алгоритмов сортировки
=========263
После того, как список элементов отсортирован, может понадобиться найти определенный элемент в списке. В этой главе описаны некоторые алгоритмы для поиска элементов в упорядоченных списках. Она начинается с краткого описания сортировки методом полного перебора. Хотя этот алгоритм выполняется не так быстро, как другие, метод полного перебора является очень простым, что облегчает его реализацию и отладку. Из‑за простоты этого метода, сортировка полным перебором также выполняется быстрее других алгоритмов для очень маленьких списков.
Далее в главе описан двоичный поиск. При двоичном поиске список многократно разбивается на части, при этом для больших списков такой поиск выполняется намного быстрее, чем полный перебор. Заключенная в этом методе идея достаточно проста, но реализовать ее довольно сложно.
Затем в главе описан интерполяционный поиск. Так же, как и в методе двоичного поиска, исходный список при этом многократно разбивается на части. При использовании интерполяционного поиска, алгоритм делает предположения о том, где может находиться искомый элемент, поэтому он выполняется намного быстрее, если данные в списках распределены равномерно.
В конце главы обсуждаются методы следящего поиска. Применение этого метода иногда уменьшает время поиска в несколько раз.
Программа Search демонстрирует все описанные в главе алгоритмы. Введите значение элементов, которые должен содержать список, и затем нажмите на кнопку Make List (Создать список), и программа создаст список на основе массива, в котором каждый элемент больше предыдущего на число от 0 до 5. Программа выводит значение наибольшего элемента в списке, чтобы вы представляли диапазон значений элементов.
После создания списка выберите алгоритмы, которые вы хотите использовать, установив соответствующие флажки. Затем введите значение, которое вы хотите найти и нажмите на кнопку Search (Поиск), и программа выполнит поиск элемента при помощи выбранного вами алгоритма. Так как список содержит не все возможные элементы в заданном диапазоне значений, то вам может понадобиться ввести несколько различных значений, прежде чем одно из них найдется в списке.
Программа также позволяет задать число повторений для каждого из алгоритмов поиска. Некоторые алгоритмы выполняются очень быстро, поэтому для того, чтобы сравнить их скорость, может понадобиться задать для них большое число повторений.
=======265
На рис. 10.1 показано окно программы Search после поиска элемента со значением 250.000. Этот элемент находился на позиции 99.802 в списке из 100.000 элементов. Чтобы найти этот элемент, потребовалось проверить 99.802 элемента при использовании алгоритма полного перебора, 16 элементов — при использовании двоичного поиска и всего 3 — при выполнении интерполяционного поиска.