初始数据
36 15 27 57 4 32 69 46 76 99 21 31 92 31 90 13
# 自底向上的构建过程中也包含了自顶向下的排序过程
步长为: 1, 序列长: 2, 15 36
步长为: 1, 序列长: 2, 57 27
步长为: 1, 序列长: 2, 4 32
步长为: 1, 序列长: 2, 69 46
步长为: 1, 序列长: 2, 76 99
步长为: 1, 序列长: 2, 31 21
步长为: 1, 序列长: 2, 31 92
步长为: 1, 序列长: 2, 90 13
步长为: 2, 序列长: 4, 15 27 57 36
步长为: 1, 序列长: 4, 15 27 36 57
步长为: 2, 序列长: 4, 69 46 4 32
步长为: 1, 序列长: 4, 69 46 32 4
步长为: 2, 序列长: 4, 31 21 76 99
步长为: 1, 序列长: 4, 21 31 76 99
步长为: 2, 序列长: 4, 90
92 31 13
步长为: 1, 序列长: 4, 92 90 31 13
步长为: 4, 序列长: 8, 15 27 32 4 69 46 36 57
步长为: 2, 序列长: 8, 15 4 32 27 36 46 69 57
步长为: 1, 序列长: 8, 4 15 27 32 36 46 57 69
步长为: 4, 序列长: 8, 92 90 76 99 21 31 31 13
步长为: 2, 序列长: 8, 92 99 76 90 31 31 21 13
步长为: 1, 序列长: 8, 99 92
90 76 31 31 21 13
双调序列
4 15 27 32 36 46 57 69 99 92 90 76 31 31 21 13
# 自顶向下完成双调序列的排序
步长为: 8, 序列长: 16, 4 15 27 32 31 31 21 13 99 92 90 76 36 46 57 69
步长为: 4, 序列长: 16, 4 15 21 13 31 31 27 32 36 46 57 69 99 92 90 76
步长为: 2, 序列长: 16, 4 13 21
15 27 31 31 32 36 46 57 69 90 76 99 92
步长为: 1, 序列长: 16, 4 13 15 21 27 31 31 32 36 46 57 69 76 90 92 99
双调排序
4 13 15 21 27 31 31 32 36 46 57 69 76 90 92 99
"""
Python program for Bitonic Sort.
Note that this program works only when size of input is a power of 2.
"""
from typing import List
def comp_and_swap(array: List[int], index1: int, index2: int, direction: int) -> None:
"""Compare the value at given index1 and index2 of the array and swap them as per
the given direction.
The parameter direction indicates the sorting direction, ASCENDING(1) or
DESCENDING(0); if (a[i] > a[j]) agrees with the direction, then a[i] and a[j] are
interchanged.
>>> arr = [12, 42, -21, 1]
>>> comp_and_swap(arr, 1, 2, 1)
>>> print(arr)
[12, -21, 42, 1]
>>> comp_and_swap(arr, 1, 2, 0)
>>> print(arr)
[12, 42, -21, 1]
>>> comp_and_swap(arr, 0, 3, 1)
>>> print(arr)
[1, 42, -21, 12]
>>> comp_and_swap(arr, 0, 3, 0)
>>> print(arr)
[12, 42, -21, 1]
"""
if (direction == 1 and array[index1] > array[index2]) or (
direction == 0 and array[index1] ):
array[index1], array[index2] = array[index2], array[index1]
def bitonic_merge(array: List[int], low: int, length: int, direction: int) -> None:
"""
It recursively sorts a bitonic sequence in ascending order, if direction = 1, and in
descending if direction = 0.
The sequence to be sorted starts at index position low, the parameter length is the
number of elements to be sorted.
>>> arr = [12, 42, -21, 1]
>>> bitonic_merge(arr, 0, 4, 1)
>>> print(arr)
[-21, 1, 12, 42]
>>> bitonic_merge(arr, 0, 4, 0)
>>> print(arr)
[42, 12, 1, -21]
"""
if length > 1:
middle = int(length / 2)
for i in range(low, low + middle):
comp_and_swap(array, i, i + middle, direction)
bitonic_merge(array, low, middle, direction)
bitonic_merge(array, low + middle, middle, direction)
def bitonic_sort(array: List[int], low: int, length: int, direction: int) -> None:
"""
This function first produces a bitonic sequence by recursively sorting its two
halves in opposite sorting orders, and then calls bitonic_merge to make them in the
same order.
>>> arr = [12, 34, 92, -23, 0, -121, -167, 145]
>>> bitonic_sort(arr, 0, 8, 1)
>>> arr
[-167, -121, -23, 0, 12, 34, 92, 145]
>>> bitonic_sort(arr, 0, 8, 0)
>>> arr
[145, 92, 34, 12, 0, -23, -121, -167]
"""
if length > 1:
middle = int(length / 2)
bitonic_sort(array, low, middle, 1)
bitonic_sort(array, low + middle, middle, 0)
bitonic_merge(array, low, length, direction)
if __name__ == "__main__":
user_input = input("Enter numbers separated by a comma:\n").strip()
unsorted = [int(item.strip()) for item in user_input.split(",")]
bitonic_sort(unsorted, 0, len(unsorted), 1)
print("\nSorted array in ascending order is: ", end="")
print(*unsorted, sep=", ")
bitonic_merge(unsorted, 0, len(unsorted), 0)
print("Sorted array in descending order is: ", end="")
print(*unsorted, sep=", ")
