Сортировка Шелла в Python
Python3 ПримерыСортировка Шелла, также известная как алгоритм сортировки с уменьшающимся приращением, представляет собой более эффективную улучшенную версию сортировки вставками. Однако сортировка Шелла — это неустойчивый алгоритм сортировки.
Основная идея сортировки Шелла состоит в следующем: сначала разделить всю последовательность записей, подлежащих сортировке, на несколько подпоследовательностей и выполнить прямую сортировку вставками для каждой подпоследовательности отдельно. Когда записи во всей последовательности «в основном упорядочены», выполнить прямую сортировку вставками для всех записей последовательно.
Пример
def shellSort(arr):
n = len(arr)
gap = int(n/2)
while gap > 0:
for i in range(gap,n):
temp = arr[i]
j = i
while j >= gap and arr[j-gap] >temp:
arr[j] = arr[j-gap]
j -= gap
arr[j] = temp
gap = int(gap/2)
arr = [ 12, 34, 54, 2, 3]
n = len(arr)
print ("Перед сортировкой:")
for i in range(n):
print(arr[i]),
shellSort(arr)
print ("\nПосле сортировки:")
for i in range(n):
print(arr[i]),
Выполнение приведённого выше кода выводит следующий результат:
排序前: 12 34 54 2 3 排序后: 2 3 12 34 54Другие расширения