排序
- 双调排序
def bitonic_sort(arr, reverse):
def compare(arr, reverse):
n = len(arr) // 2
for i in range(n):
if reverse != (arr[i] > arr[i+n]):
arr[i], arr[i+n] = arr[i+n], arr[i]
return arr
def bitonic_merge(arr, reverse):
n = len(arr)
if n <= 1:
return arr
arr = compare(arr, reverse)
left = bitonic_merge(arr[:n // 2], reverse)
right = bitonic_merge(arr[n // 2:], reverse)
return left + right
n = len(arr)
if n <= 1:
return arr
assert n & n-1 == 0
left = bitonic_sort(arr[:n // 2], True)
right = bitonic_sort(arr[n // 2:], False)
arr = bitonic_merge(left + right, reverse)
return arr
if __name__ == "__main__":
arr = [10, 20, 5, 9, 3, 8, 12, 14, 90, 0, 60, 40, 23, 35, 95, 18]
assert bitonic_sort(arr, False) == [
0, 3, 5, 8, 9, 10, 12, 14, 18, 20, 23, 35, 40, 60, 90, 95]
- 冒泡排序
时间复杂度：O(n^2) 思路：找出最大的放在最后
def bubble_sort(arr):
def swap(i, j):
arr[i], arr[j] = arr[j], arr[i]
n = len(arr)
last = n
while last > 1:
for index in range(last-1):
if arr[index] > arr[index+1]:
swap(index, index+1)
last -= 1
return arr
if __name__ == "__main__":
arr = [10, 20, 5, 9, 3, 8, 12, 14, 90, 0, 60, 40, 23, 35, 95, 18]
assert bubble_sort(arr) == [0, 3, 5, 8, 9, 10,
12, 14, 18, 20, 23, 35, 40, 60, 90, 95]
- 桶排序
时间复杂度：O(n) 思路：按索引放成员
def bucket_sort(arr):
max_num = max(arr)
min_num = min(arr)
bucket = [None]*(max_num+1-min_num)
for v in arr:
bucket[v - min_num] = v
list = []
for v in bucket:
if v is not None:
list.append(v)
return list
if __name__ == "__main__":
arr = [10, 20, 5, 9, 3, 8, 12, 14, 90, 0, 60, 40, 23, 35, 95, 18]
assert bucket_sort(arr) == [0, 3, 5, 8, 9, 10,
12, 14, 18, 20, 23, 35, 40, 60, 90, 95]
- 圈排序
时间复杂度：O(n^2) 思路：首先按索引找出目标成员，然后按大小顺讯排列，完成替换后，在将被替换的成员放置正确的位置
def cycle_sort(arr):
len_arr = len(arr)
for cur in range(len_arr-1):
item = arr[cur]
index = cur
for i in range(cur+1, len_arr):
if item > arr[i]:
index += 1
arr[index], item = item, arr[index]
while index != cur:
index = cur
for i in range(cur+1, len_arr):
if item > arr[i]:
index += 1
arr[index], item = item, arr[index]
return arr
if __name__ == "__main__":
arr = [10, 20, 5, 9, 3, 8, 12, 14, 90, 0, 60, 40, 23, 35, 95, 18]
assert cycle_sort(arr) == [0, 3, 5, 8, 9, 10, 12,
14, 18, 20, 23, 35, 40, 60, 90, 95]
- 地精排序
思路：从大到小遍历所有成员，如果index-1成员小于index，index加一，反之index减一
def gnome_sort(arr):
len_arr = len(arr)
index = 0
while index < len_arr:
if index == 0 or arr[index-1] < arr[index]:
index += 1
else:
arr[index-1], arr[index] = arr[index], arr[index-1]
index -= 1
return arr
if __name__ == "__main__":
arr = [10, 20, 5, 9, 3, 8, 12, 14, 90, 0, 60, 40, 23, 35, 95, 18]
assert gnome_sort(arr) == [0, 3, 5, 8, 9, 10, 12,
14, 18, 20, 23, 35, 40, 60, 90, 95]
- 堆排序
思路：首先建立小顶对，从长度//2开始从大到小遍历，找出叶节点的儿子，2 * index+ 1和2 * index + 2，将两个儿子的最小值和叶节点替换，如果叶节点更大的话，最后按顺序剔除堆顶点，然后排序
def heap_sort(arr):
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def heapfy(arr, index, end):
len_arr = len(arr[:end])
while index*2+1 < len_arr:
child = index*2 + 1
if child+1 < len_arr and arr[child] < arr[child+1]:
child += 1
if arr[index] > arr[child]:
break
swap(arr, index, child)
index = child
len_arr = len(arr)
for i in range(len_arr//2, -1, -1):
heapfy(arr, i, len_arr-1)
for i in range(len_arr-1, 0, -1):
swap(arr, 0, i)
heapfy(arr, 0, i)
return arr
if __name__ == "__main__":
arr = [10, 20, 5, 9, 3, 8, 12, 14, 90, 0, 60, 40, 23, 35, 95, 18]
assert heap_sort(arr) == [0, 3, 5, 8, 9, 10, 12,
14, 18, 20, 23, 35, 40, 60, 90, 95]
- 插入排序
思路：从小到大遍历数组，每次循环中将当前成员插入到前方所有成员中第一个大于他的前面
def insertion_sort(arr):
for index in range(1, len(arr)):
item = arr[index]
for i in range(index):
if item < arr[i]:
arr.pop(index)
arr.insert(i, item)
break
return arr
if __name__ == "__main__":
arr = [10, 20, 5, 9, 3, 8, 12, 14, 90, 0, 60, 40, 23, 35, 95, 18]
assert insertion_sort(arr) == [0, 3, 5, 8, 9,
10, 12, 14, 18, 20, 23, 35, 40, 60, 90, 95]
- 融合排序
思路：递归，将数组逐步分为左右两部分，然后将两部分逐一成员比较大小然后排序
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right, arr.copy())
def merge(left, right, arr):
l_index = r_index = 0
while l_index < len(left) and r_index < len(right):
if left[l_index] < right[r_index]:
arr[l_index+r_index] = left[l_index]
l_index += 1
else:
arr[l_index+r_index] = right[r_index]
r_index += 1
for i in range(l_index, len(left)):
arr[i+r_index] = left[i]
for i in range(r_index, len(right)):
arr[l_index+i] = right[i]
return arr
if __name__ == "__main__":
arr = [10, 20, 5, 9, 3, 8, 12, 14, 90, 0, 60, 40, 23, 35, 95, 18]
assert len(merge_sort(arr)) == len(arr)
assert merge_sort(arr) == [0, 3, 5, 8, 9, 10, 12,
14, 18, 20, 23, 35, 40, 60, 90, 95]
- 快排
思路：递归，随机找出其中一个成员，将大于它的放右变，小于的放左边，然后再将左右两边分别重复上述排列，直到长度小于等于1
def quick_sort(arr):
def partition(arr, left, right):
store_index = left
for i in range(left, right):
if arr[i] < arr[right]:
arr[i], arr[store_index] = arr[store_index], arr[i]
store_index += 1
arr[right], arr[store_index] = arr[store_index], arr[right]
return store_index
def quick_sort_recur(arr, left, right):
if left < right:
store_index = partition(arr, left, right)
quick_sort_recur(arr, left, store_index-1)
quick_sort_recur(arr, store_index+1, right)
quick_sort_recur(arr, 0, len(arr)-1)
return arr
if __name__ == "__main__":
arr = [10, 20, 5, 9, 3, 8, 12, 14, 90, 0, 60, 40, 23, 35, 95, 18]
assert len(quick_sort(arr)) == len(arr)
assert quick_sort(arr) == [0, 3, 5, 8, 9, 10, 12,
14, 18, 20, 23, 35, 40, 60, 90, 95]
- 选择排序
思路：从小打到遍历数组逐一将最小的排到前面
def selection_sort(arr):
for i in range(len(arr)):
cor_index = i
for j in range(i, len(arr)):
if arr[j] < arr[cor_index]:
cor_index = j
arr[i], arr[cor_index] = arr[cor_index], arr[i]
return arr
if __name__ == "__main__":
arr = [10, 20, 5, 9, 3, 8, 12, 14, 90, 0, 60, 40, 23, 35, 95, 18]
assert len(selection_sort(arr)) == len(arr)
assert selection_sort(arr) == [0, 3, 5, 8, 9, 10, 12,
14, 18, 20, 23, 35, 40, 60, 90, 95]
- 颜色排序
思路：遍历一次数组，找出等于2的成员，并且计算出非2的总和，即为1的个数
def sort_colors(arr):
n = len(arr)
index = n-1
res_arr, sums = [1]*n, 0
for v in arr:
if v == 2:
res_arr[index] = v
index -= 1
else:
sums += v
zero_nums = index+1-sums
zeros = [0]*(zero_nums)
zeros.extend(res_arr[zero_nums:])
return zeros
if __name__ == "__main__":
arr = [0, 1, 1, 1, 2, 2, 2, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 2, 2]
assert len(sort_colors(arr)) == len(arr)
assert sort_colors(arr) == [0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]
