当前位置：首页 > news >正文

【排序算法 python实现】

news 2024/11/24 17:06:43

排序算法 python实现 / 默写

# 汉诺塔
import copy
import randomdef hanuo(n, a, b, c):if n == 1:print(f'{a} --> {c}')returnhanuo(n - 1, a, c, b)print(f'{a} --> {c}')hanuo(n - 1, b, a, c)hanuo(3, 'A', 'B', 'C')# 冒泡排序
def bubble_sort(arr):n = len(arr)for i in range(n - 1):for j in range(n - 1 - i):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arrdef jiWeiJiu(arr):n = len(arr)for i in range(n // 2):flag = Falsefor m in range(i, n - 1 - i):if arr[m] > arr[m + 1]:arr[m], arr[m + 1] = arr[m + 1], arr[m]flag = Trueif not flag:breakflag = Falsefor q in range(n - i - 2, i, -1):if arr[q - 1] > arr[q]:arr[q - 1], arr[q] = arr[q], arr[q - 1]flag = Trueif not flag:breakreturn arrdef choose_sort(arr):n = len(arr)"""0 1 2 3 4 5n = 6"""for i in range(n - 1):min_index = ifor j in range(i + 1, n):if arr[min_index] > arr[j]:min_index = jif min_index != i:arr[min_index], arr[i] = arr[i], arr[min_index]return arr# 3. 插入
def insert_sort(arr):n = len(arr)for i in range(1, n):j = i - 1tmp = arr[i]while j >= 0 and tmp < arr[j]:arr[j + 1] = arr[j]j -= 1arr[j + 1] = tmpreturn arrdef merge(arr, left, mid, right):i = leftj = mid + 1tmp = []while i <= mid and j <= right:if arr[i] < arr[j]:tmp.append(arr[i])i += 1else:tmp.append(arr[j])j += 1while i <= mid:tmp.append(arr[i])i += 1while j <= right:tmp.append(arr[j])j += 1arr[left: right + 1] = tmpdef merge_sort(arr, left, right):if left < right:mid = (left + right) // 2# 假设左边右边都已经排好了merge_sort(arr, left, mid)merge_sort(arr, mid + 1, right)merge(arr, left, mid, right)return arr# 5. 快速
def partition(arr, left, right):tmp = arr[left]while left < right:while left < right and arr[right] >= tmp:right -= 1arr[left] = arr[right]while left < right and arr[left] <= tmp:left += 1arr[right] = arr[left]arr[left] = tmpreturn leftdef quick_sort(arr, left, right):if left < right:mid = partition(arr, left, right)quick_sort(arr, left, mid - 1)quick_sort(arr, mid + 1, right)return arr# 定顶调整，大顶堆
# 以后不用 i j 用 p q
def sift(arr, low, high):i = lowtmp = arr[low]j = 2 * i + 1# 最小三角while j <= high:if j + 1 <= high and arr[j] < arr[j + 1]:j = j + 1if tmp < arr[j]:arr[i] = arr[j]i = jj = 2 * i + 1else:breakarr[i] = tmpreturn arrdef heap_sort(arr):n = len(arr)# 农村包围城市# 依次处理每个顶for i in range((n - 2) // 2, -1, -1):sift(arr, i, n - 1)# 挨个出数for i in range(n - 1, -1, -1):arr[0], arr[i] = arr[i], arr[0]sift(arr, 0, i - 1)return arr# 3. 插入
def insert_sort_gap(arr, gap):n = len(arr)for i in range(gap, n):j = i - gaptmp = arr[i]while j >= 0 and tmp < arr[j]:arr[j + gap] = arr[j]j -= gaparr[j + gap] = tmpreturn arrdef shell_sort(arr):n = len(arr)gap = n // 2while gap >= 1:insert_sort_gap(arr, gap)gap //= 2return arr# 8. 计数
"""
0 1 2 3 4 8
max_v = 8
0 ~ 8; [0 , 9)
"""def count_sort(arr):max_v = max(arr)bucket = [0 for _ in range(max_v + 1)]for item in arr:bucket[item] += 1arr.clear()for i in range(len(bucket)):while bucket[i] > 0:arr.append(i)bucket[i] -= 1return arrdef radix_sort(arr):if not arr:return []digit = len(str(max(arr)))for i in range(digit):bucket = [[] for _ in range(10)]  # 0 ~ 9for v in arr:k = (v // (10 ** i)) % 10bucket[k].append(v)arr.clear()for bu in bucket:arr.extend(bu)return arrdef bucket_sort(arr, n=100, max_v=10000):bucket = [[] for _ in range(n)]for v in arr:i = min(v // (max_v // n), n - 1)bucket[i].append(v)for j in range(len(bucket[i]) - 1, 0, -1):if bucket[i][j] < bucket[i][j - 1]:bucket[i][j], bucket[i][j - 1] = bucket[i][j - 1], bucket[i][j]else:breakarr.clear()for bu in bucket:arr.extend(bu)return arrli = [random.randint(0, 100) for _ in range(10)]
li1 = copy.deepcopy(li)
li2 = copy.deepcopy(li)
li3 = copy.deepcopy(li)
li4 = copy.deepcopy(li)
li5 = copy.deepcopy(li)
li6 = copy.deepcopy(li)
li7 = copy.deepcopy(li)
li8 = copy.deepcopy(li)
li9 = copy.deepcopy(li)
li10 = copy.deepcopy(li)
li11 = copy.deepcopy(li)print('冒泡：', bubble_sort(li1))
print('鸡尾：', jiWeiJiu(li2))
print('选择：', choose_sort(li3))
print('插入：', insert_sort(li4))
print('归并：', merge_sort(li5, 0, len(li5) - 1))
print('快速：', quick_sort(li6, 0, len(li5) - 1))
print('堆排：', heap_sort(li7))
print('希尔：', shell_sort(li8))
print('计数：', count_sort(li9))
print('基数：', radix_sort(li10))
print('桶排：', bucket_sort(li11))