def radix(array):
"""
LSD基数排序
:param array:
:return:
"""
size = 10
div = 1
most_bit = len(str(max(array)))
buckets = [[] for i in range(size)]
while most_bit:
for one in array:
buckets[one // div % size].append(one)
i = 0
for bucket in buckets:
while bucket:
array[i] = bucket.pop(0)
i += 1
div *= 10
most_bit -= 1
return array
print(radix([123, 1, 23, 1, 121, 2, 12]))
def merge_method(left, right):
result = []
while left and right:
if left[0] > right[0]:
result.append(right.pop(0))
else:
result.append(left.pop(0))
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0))
return result
def merge(array):
"""
归并排序
:param array:
:return:
"""
import math
if len(array) < 2:
return array
mid = math.floor(len(array) / 2)
left, right = array[0:mid], array[mid:]
return merge_method(merge(left), merge(right))
print(merge([123, 2, 13, 1, 23, 1, 23, 12, 31]))
def bucket(array, default_size=5):
"""
桶排序
:param array:
:param default_size:
:return:
"""
max_val, min_val = max(array), min(array)
bucket_size = default_size
temp = (max_val - min_val) // bucket_size + 1
buckets = [[] for i in range(temp)]
for one in array:
buckets[(one - min_val) // bucket_size].append(one)
array.clear()
for bucket in buckets:
bucket = merge(bucket)
array += bucket
return array
print(bucket([123, 21, 12, 222, 12, 1, 21]))
def exchange(array, i, j):
array[i], array[j] = array[j], array[i]
def heapify(array, i):
left = 2 * i + 1
right = 2 * i + 2
largest = i
if left < array_len and array[left] > array[largest]:
largest = left
if right < array_len and array[right] > array[largest]:
largest = right
if largest != i:
exchange(array, i, largest)
heapify(array, largest)
def build_max_heap(array):
import math
for i in range(math.floor(len(array) / 2), -1, -1):
heapify(array, i)
def heap(array):
"""
堆排序
:param array:
:return:
"""
global array_len
array_len = len(array)
build_max_heap(array)
for i in range(len(array) - 1, 0, -1):
exchange(array, i, 0)
array_len -= 1
heapify(array, 0)
return array
print(heap([231, 2, 31, 2, 12, 1, 2, 311]))
def count(array):
"""
计数排序
:param array:
:return:
"""
size = max(array) + 1
buckets = [0] * size
for i in range(len(array)):
if not buckets[array[i]]:
buckets[array[i]] = 0
buckets[array[i]] += 1
sort = 0
for j in range(len(buckets)):
while buckets[j] > 0:
array[sort] = j
buckets[j] -= 1
sort += 1
return array
print(count([1, 23, 12, 1231, 12, 22, 3]))
def partition(array, left, right):
pivot = left
index = pivot + 1
i = index
while i <= right:
if array[pivot] > array[i]:
exchange(array, i, index)
index += 1
i += 1
exchange(array, pivot, index - 1)
return index - 1
def quick(array, left=None, right=None):
"""
快速排序
:param array:
:param left:
:param right:
:return:
"""
left = 0 if not isinstance(left, (int, float)) else left
right = len(array) - 1 if not isinstance(right, (int, float)) else right
if left < right:
partition_index = partition(array, left, right)
quick(array, left, partition_index - 1)
quick(array, partition_index + 1, right)
return array
print(quick([123, 23, 1, 1, 2, 1, 2, 1, 21, 22]))
def shell(array):
"""
希尔排序
:param array:
:return:
"""
gap = 1
while gap < len(array):
gap = gap * 3 + 1
while gap > 0:
for i in range(gap, len(array)):
pre_index = i - gap
current = array[i]
while pre_index >= 0 and array[pre_index] > current:
array[pre_index + gap] = array[pre_index]
pre_index -= gap
array[pre_index + gap] = current
import math
gap = math.floor(gap / 3)
return array
print(shell([213, 12, 31, 23, 1, 231, 2]))
def insert(array):
"""
插入排序
:param array:
:return:
"""
for i in range(len(array)):
pre_index = i - 1
current = array[i]
while pre_index >= 0 and array[pre_index] > current:
array[pre_index + 1] = array[pre_index]
pre_index -= 1
array[pre_index + 1] = current
return array
print(insert([213, 2, 123, 1, 3, 123, 3, 12]))
def select(array):
"""
选择排序
:param array:
:return:
"""
for i in range(len(array) - 1):
idx = i
for j in range(i, len(array)):
if array[idx] > array[j]:
idx = j
if idx != i:
array[i], array[idx] = array[idx], array[i]
return array
print(select([123, 23, 12, 3, 1, 1, 32, 32, 1]))
def bubble(array):
"""
冒泡排序
:param array:
:return:
"""
for i in range(1, len(array)):
for j in range(len(array) - i):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
return array
print(bubble([123, 23, 21, 3, 1, 2, 1]))
