프로그래머가 마스터해야 할 상위 10가지 정렬 알고리즘(2부)

'''希尔排序''' def Shell_Sort(arr): # 设定步长,注意类型 step = int(len(arr) / 2) while step > 0: for i in range(step, len(arr)): # 类似插入排序, 当前值与指定步长之前的值比较, 符合条件则交换位置 while i >= step and arr[i - step] > arr[i]: arr[i], arr[i - step] = arr[i - step], arr[i] i -= step step = int(step / 2) return arr arr = [29, 63, 41, 5, 62, 66, 57, 34, 94, 22] result = Shell_Sort(arr) print('result list: ', result) # result list: [5, 22, 29, 34, 41, 57, 62, 63, 66, 94]

'''归并排序'''def Merge(left, right): arr = [] i = j = 0 while j < len(left) and i < len(right): if left[j] < right[i]: arr.append(left[j]) j += 1 else: arr.append(right[i]) i += 1 if j == len(left): # right遍历完 for k in right[i:]: arr.append(k) else: # left遍历完 for k in left[j:]: arr.append(k) return arr def Merge_Sort(arr): # 递归结束条件 if len(arr) <= 1: return arr # 二分 middle = len(arr) // 2 left = Merge_Sort(arr[:middle]) right = Merge_Sort(arr[middle:]) # 合并 return Merge(left, right) arr = [27, 70, 34, 65, 9, 22, 47, 68, 21, 18] result = Merge_Sort(arr) print('result list: ', result) # result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]

'''计数排序''' def Count_Sort(arr): max_num = max(arr) min_num = min(arr) count_num = max_num - min_num + 1 count_arr = [0 for i in range(count_num)] res = [0 for i in range(len(arr))] # 统计数字出现的次数 for i in arr: count_arr[i - min_num] += 1 # 统计前面有几个比自己小的数 for j in range(1, count_num): count_arr[j] = count_arr[j] + count_arr[j - 1] # 遍历重组 for k in range(len(arr)): res[count_arr[arr[k] - min_num] - 1] = arr[k] count_arr[arr[k] - min_num] -= 1 return res arr = [5, 10, 76, 55, 13, 79, 5, 49, 51, 65, 30, 5] result = Count_Sort(arr) print('result list: ', result) # result list: [5, 5, 5, 10, 13, 30, 49, 51, 55, 65, 76, 79]

'''基数排序''' def Radix_Sort(arr): max_num = max(arr) place = 0 while 10 ** place <= max_num: # 创建桶 buckets = [[] for _ in range(10)] # 分桶 for item in arr: pos = item // 10 ** place % 10 buckets[pos].append(item) j = 0 for k in range(10): for num in buckets[k]: arr[j] = num j += 1 place += 1 return arr arr = [31, 80, 42, 47, 35, 26, 10, 5, 51, 53] result = Radix_Sort(arr) print('result list: ', result) # result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]

'''桶排序''' def Bucket_Sort(arr): num = max(arr) # 列表置零 pre_lst = [0] * num result = [] for data in arr: pre_lst[data - 1] += 1 i = 0 while i < len(pre_lst): # 遍历生成的列表，从小到大 j = 0 while j < pre_lst[i]: result.append(i + 1) j += 1 i += 1 return result arr = [26, 53, 83, 86, 5, 46, 5, 72, 21, 4, 75] result = Bucket_Sort(arr) print('result list: ', result) # result list: [4, 5, 5, 21, 26, 46, 53, 72, 75, 83, 86]