目录冒泡排序选择排序快速排序1快速排序2归并排序插入排序希尔排序堆排序计数排序桶排序基数排序睡眠排序先简单了解一下常见的时间复杂度类别方便对排序算法时间花销有更好的理解O(1)常数复杂度算法的执行时间不随输入数据的大小变化而变化。O(log n)对数复杂度算法的执行时间是输入数据大小的对数函数通常见于二分查找。O(n)线性复杂度算法的执行时间与输入数据的大小成正比例如简单查找。O(n log n)线性对数复杂度常见于快速排序和归并排序。O(n^2)平方复杂度通常见于简单的双层循环算法如冒泡排序。O(n^3)立方复杂度通常见于三层嵌套循环算法。O(2^n)指数复杂度算法的执行时间随数据规模的增加而呈指数增长例如递归计算斐波那契数列。O(n!)阶乘复杂度随着n的增加执行时间的增加速度非常快通常见于解决旅行商问题的算法。冒泡排序- 思想通过多次比较和交换相邻的元素将最大或最小的元素逐渐移到列表的末尾。- 时间复杂度最坏情况下是O(n^2)平均情况下也是O(n^2)。- 空间复杂度O(1)原地排序不需要额外空间。def bubble_sort(input_list): 冒泡排序 length len(input_list) if length 2: return input_list for i in range(length): # 外层循环控制轮数 for j in range(length - 1 - i): # 内层循环控制遍历范围 if input_list[j 1] input_list[j]: input_list[j 1], input_list[j] input_list[j], input_list[j 1] return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(冒泡排序 , bubble_sort(input_list)) # 冒泡排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]选择排序- 思想在未排序的数据中选择最小或最大的元素将其放置在已排序部分的末尾。- 时间复杂度最坏情况下是O(n^2)平均情况下也是O(n^2)。- 空间复杂度O(1)原地排序。def select_sort(input_list): 选择排序 length len(input_list) if length 2: return input_list for i in range(length): minIndex i # 初始默认minIndex为未排序列中最小元素对应的索引 for j in range(i 1, length): if input_list[j] input_list[minIndex]: # 如果找到更小元素进行交换 input_list[j], input_list[minIndex] input_list[minIndex], input_list[j] return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(选择排序 , select_sort(input_list)) # 选择排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]A快速排序1- 思想选择一个基准元素将小于基准的元素放在左侧大于基准的元素放在右侧然后递归对左右子数组进行排序。- 时间复杂度最坏情况下是O(n^2)平均情况下是O(n log n)。- 空间复杂度平均情况下是O(log n)最坏情况下是O(n)。def quick_sort1(input_list, left, right): 快速排序 # 直接在原列表上进行操作 def partition(input_list, left, right): # 主要目的是将比基准数小的放到基准数左边比基准数大的放到基准数右边 key left # 划分参考数索引,默认为第一个数为基准数可优化 while left right: # 如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现 while left right and input_list[right] input_list[key]: right - 1 # 如果列表前边的数,比基准数小或相等,则后移一位直到有比基准数大的数出现 while left right and input_list[left] input_list[key]: left 1 # 此时已找到一个比基准大的数和一个比基准小的数将他们互换位置 (input_list[left], input_list[right]) (input_list[right], input_list[left]) # 当从两边分别逼近直到两个位置相等时结束将对应位置的数同基准数进行互换 (input_list[left], input_list[key]) (input_list[key], input_list[left]) # 返回目前基准数所在位置的索引 return left if left right: # 如果已经不能分区开始结束递归调用递归调用结束的判定 return # 从基准开始分区 mid partition(input_list, left, right) # 递归调用 quick_sort1(input_list, left, mid - 1) quick_sort1(input_list, mid 1, right) return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(快速排序1, quick_sort1(input_list, 0, len(input_list) - 1)) # 快速排序1 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]快速排序2def quick_sort2(input_list): 快速排序 # 这个递归的快排会更好理解一些缺点在于不是在原列表上进行操作 if len(input_list) 2: mid input_list[len(input_list) // 2] # 基准数可从待排序列任选 left, right [], [] input_list.remove(mid) for num in input_list: if num mid: right.append(num) else: left.append(num) return quick_sort2(left) [mid] quick_sort2(right) else: return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(快速排序2, quick_sort2(input_list)) # 快速排序2 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]归并排序- 思想将待排序数组分为两个子数组分别对子数组进行排序然后将它们合并成一个有序数组。- 时间复杂度最坏情况下和平均情况下都是O(n log n)。这块有个文章详细解释了快速排序的时间复杂度是怎么算出来的归并排序时间复杂度过程推导详解_java_脚本之家- 空间复杂度O(n)需要额外的空间来合并子数组。def merge_sort(input_list): # 分治法 归并排序 def merge(left, right): # left和right都是有序的 merge_result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: merge_result.append(left[i]) i 1 else: merge_result.append(right[j]) j 1 if i len(left): # 如果left已经追加完毕将right剩下的元素直接追加到末尾 merge_result.extend(right[j:]) else: # 如果right已经追加完毕将left剩下的元素直接追加到末尾 merge_result.extend(left[i:]) return merge_result if len(input_list) 2: return input_list middle len(input_list) // 2 left merge_sort(input_list[:middle]) # 递归调用归并排序 right merge_sort(input_list[middle:]) return merge(left, right) if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(归并排序 , merge_sort(input_list)) # 归并排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]插入排序- 思想将待排序的元素逐个插入到已排序部分的正确位置构建有序序列。- 时间复杂度最坏情况下是O(n^2)平均情况下也是O(n^2)。- 空间复杂度O(1)原地排序。def insert_sort(input_list): 插入排序 length len(input_list) if length 2: return input_list for i in range(1, length): j i target input_list[i] # target要进行插入的元素 while j 0 and target input_list[j - 1]: # 寻找插入位置 input_list[j] input_list[j - 1] j j - 1 input_list[j] target return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(插入排序 , insert_sort(input_list)) # 插入排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]希尔排序def shell_sort(input_list): 希尔排序 def shell_insert(input_list, gap): # gap为组内元素的索引间隔(步长)代码部分参考“插入排序”很像 for i in range(gap, length): # 当gap为1的时候就是等同于插入排序insert_sort j i target input_list[i] # 记录要插入的数,因为input_list[i]的值会被覆盖所以必须提前记录 while j 0 and target input_list[j - gap]: # 对步长为gap的同组数据进行插入排序 # 从后往前直到找到比target小的数的位置 input_list[j] input_list[j - gap] # 向后挪动 j - gap # 未找到之前继续往前一个 input_list[j] target # 将target插入目标位置 length len(input_list) if length 2: return input_list gap length // 2 while gap 1: shell_insert(input_list, gap) gap gap // 2 return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(希尔排序 , shell_sort(input_list)) # 希尔排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]堆排序堆的实现思路1将待排序的序列构造成一个大根堆或小根堆。2将堆顶元素与堆底元素交换并将堆的规模缩小1。3对新的堆顶元素进行向下调整操作使其重新成为大根堆或小根堆。4重复步骤2和3直到堆的规模为1。- 思想将待排序数组构建成最大堆或最小堆然后逐步将堆顶元素与堆尾元素交换调整堆结构重复这个过程直到整个数组有序。- 时间复杂度最坏情况下和平均情况下都是O(n log n)。- 空间复杂度O(1)原地排序。def heap_sort(input_list): 堆排序 def sift_down(input_list, father, end): # 让父节点始终比左右子节点(如果右节点存在的话)的值要大 # end 之后的数据是已经排好序的数据若计算的孩子超出 end 范围则不处理 while True: # 交换之后可能造成被交换的孩子节点作为父节点不再满足堆的性质因此需要重新对交换的孩子节点进行堆初始化 left_child 2 * father 1 # 父节点左孩子节点下标 if left_child end: # 孩子节点不一定还有孩子节点 break # 如果节点的右孩子存在且大于左孩子时此时右孩子为孩子节点中的最大交换时此右节点与父节点交换 # 否则父节点只有左孩子或者左孩子比右孩子要小此时左孩子是孩子节点中最大的交换时此左节点与父节点交换 if left_child 1 end and input_list[left_child 1] input_list[left_child]: left_child left_child 1 # 若上一个if语句执行则以下代码是右子节点与父节点交换否则为左子节点与父节点交换 if input_list[left_child] input_list[father]: input_list[left_child], input_list[father] input_list[father], input_list[left_child] father left_child # 调换后子节点可能不满足大顶堆被调换的子节点重新作为父节点继续进行调整操作 else: break length len(input_list) first length // 2 - 1 # 最后一个有孩子的节点的下标 for i in range(first, -1, -1): # 从最后一个有子节点的节点开始往上调整最大堆 sift_down(input_list, i, length - 1) for head_end in range(length - 1, 0, -1): input_list[head_end], input_list[0] input_list[0], input_list[head_end] # 头尾对调同时堆开始变小 sift_down(input_list, 0, head_end - 1) # father0 表示交换以后自顶向下重新调整大顶堆 return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(堆排序 , heap_sort(input_list)) # 堆排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]计数排序- 思想适用于非负整数的排序算法通过统计每个元素出现的次数来进行排序。- 时间复杂度最坏情况下和平均情况下都是O(n k)其中k是非负整数的范围。- 空间复杂度O(k)。def count_sort(input_list): 计数排序 length len(input_list) if length 2: return input_list max_num max(input_list) count [0] * (max_num 1) for element in input_list: count[element] 1 # 间接使用索引来存储数 input_list.clear() for i in range(max_num 1): # 元素[0, 1, 2, ..., max_num] # input_list.extend([i] * count[i]) # 下面两条语句可以用这条语句替代 for j in range(count[i]): # count[i]表示元素i出现的次数如果有多次重复追加 input_list.append(i) return input_list # 下面这种代码思想也可以达到相同的目的只不过中间涉及到元素间的比较与计数排序的思想稍有差异。 # count [0] * length # for i in range(length): # p 0 # q 0 # for j in range(length): # # 全表查找比input_list[i]小的元素个数pq是为了保证相同元素重复出现时仍然能够正常排序 # # 这块的元素比较使得它算不上真正意义上的计数排序不过思想倒是已经很不错。 # if input_list[j] input_list[i]: # p 1 # elif input_list[j] input_list[i]: # q 1 # # count[p] input_list[i] # for k in range(p, p q): # 如果没有重复元素最终可得q1这里其实就可以写成 count[p] input_list[i] 了 # count[k] input_list[i] # return count if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(计数排序 , count_sort(input_list)) # 计数排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]桶排序def bucket_sort(input_list): 桶排序 big max(input_list) num big // 10 1 # 以10为等差计算桶的数目 buckets [[] for i in range(0, num)] # 初始化桶 for i in input_list: buckets[i // 10].append(i) # 划分桶 for i in buckets: # 桶内排序桶内快速排序 quick_sort1(i, 0, len(i) - 1) # 对原列表进行修改所以无需返回新的排序后的列表 # bucket quick_sort2(i) # 返回新的列表不是在原列表上修改 # buckets[buckets.index(i)] bucket # 根据桶的划分每个桶是不一样的所以我这儿用index函数查找每个桶的索引位置 output_list [] for i in buckets: output_list.extend(i) # for j in i: # output_list.append(j) return output_list def quick_sort1(input_list, left, right): 快速排序 # 直接在原列表上进行操作 def partition(input_list, left, right): # 主要目的是将比基准数小的放到基准数左边比基准数大的放到基准数右边 key left # 划分参考数索引,默认为第一个数为基准数可优化 while left right: # 如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现 while left right and input_list[right] input_list[key]: right - 1 # 如果列表前边的数,比基准数小或相等,则后移一位直到有比基准数大的数出现 while left right and input_list[left] input_list[key]: left 1 # 此时已找到一个比基准大的数和一个比基准小的数将他们互换位置 (input_list[left], input_list[right]) (input_list[right], input_list[left]) # 当从两边分别逼近直到两个位置相等时结束将对应位置的数同基准数进行互换 (input_list[left], input_list[key]) (input_list[key], input_list[left]) # 返回目前基准数所在位置的索引 return left if left right: # 如果已经不能分区开始结束递归调用递归调用结束的判定 return # 从基准开始分区 mid partition(input_list, left, right) # 递归调用 quick_sort1(input_list, left, mid - 1) quick_sort1(input_list, mid 1, right) return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(桶排序 , bucket_sort(input_list)) # 桶排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]基数排序- 思想适用于整数或字符串的排序算法将数据按位数进行排序从最低位到最高位。- 时间复杂度最坏情况下和平均情况下都是O(nk)其中k是位数。- 空间复杂度O(n k)。def radix_sort(input_list, radix10): 基数排序 # import math # K math.ceil(math.log(max(input_list), radix)) # 用K位数可表示任意整数 K 1 # 也可不用 import math 模块 毕竟简单算法尽量不要用库函数 for element in input_list: while True: if element radix ** K: K 1 else: break # K表示最大数的位数比如最大数为897则K3 bucket [[] for i in range(radix)] # 不能用 [[]]*radix (看完下面几条语句你就会明白为什么) # bucket [[]] * radix # [[], [], [], [], [], [], [], [], [], []] # aa [[]] * 10 # 一改具改 # bb [[] for i in range(10)] # aa bb # 尽管有 # True # aa[0] is aa[1] # True # bb[0] is bb[1] # 但是 # False # [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] # [[50], [], [2], [3], [44, 4], [5, 15], [36, 26, 46], [47, 27], [38, 48], [19]] # [50, 2, 3, 44, 4, 5, 15, 36, 26, 46, 47, 27, 38, 48, 19] # [[2, 3, 4, 5], [15, 19], [26, 27], [36, 38], [44, 46, 47, 48], [50], [], [], [], []] # [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] for i in range(K): # K次循环 for val in input_list: bucket_index val % (radix ** (i 1)) // (radix ** i) # 把val放到bucket_index对应的这个桶 # example 4789 % 10**3 // 10**2 7 bucket[bucket_index].append(val) # 析取整数第K位数字 从低到高 个十百千... input_list.clear() for each in bucket: input_list.extend(each) # 桶合并 bucket [[] for i in range(radix)] return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(基数排序 , radix_sort(input_list)) # 基数排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]睡眠排序这个算法虽然是拿来搞笑的但他毕竟也是正儿八经的可以排序出来的。import time import threading def sleep_sort(input_list): # 哈哈调皮一下顺便学学join和守护线程的用法如果max(input_list)比较大的话建议放弃尝试 睡眠排序 output_list [] thread_list [] def do_sleep(i): # 统一乘了一个系数总不能让我真的等i秒 time.sleep(i / 100) # 只要sleep时间不会过于短在毫秒级别以上应该都是可以分出先后的再短就悬了 output_list.append(i) for i in input_list: t threading.Thread(targetdo_sleep, args(i,)) thread_list.append(t) for t in thread_list: # 对每个线程设置守护并开启主线程结束以后会杀死子线程 t.setDaemon(True) t.start() for t in thread_list: # join 所完成的工作就是线程同步避免主线程提前结束以后直接终止掉了子线程 t.join() # 即主线程任务结束之后进入阻塞状态一直等待其他的子线程执行结束之后才继续 # t.join(timeout0.02) # 主线程将会累计等待timeout*len(input_list)这么多秒时间一到强行终止返回当前已排序结果 return output_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(睡眠排序 , sleep_sort(input_list)) # 睡眠排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] Python 之简单排序算法实现
目录冒泡排序选择排序快速排序1快速排序2归并排序插入排序希尔排序堆排序计数排序桶排序基数排序睡眠排序先简单了解一下常见的时间复杂度类别方便对排序算法时间花销有更好的理解O(1)常数复杂度算法的执行时间不随输入数据的大小变化而变化。O(log n)对数复杂度算法的执行时间是输入数据大小的对数函数通常见于二分查找。O(n)线性复杂度算法的执行时间与输入数据的大小成正比例如简单查找。O(n log n)线性对数复杂度常见于快速排序和归并排序。O(n^2)平方复杂度通常见于简单的双层循环算法如冒泡排序。O(n^3)立方复杂度通常见于三层嵌套循环算法。O(2^n)指数复杂度算法的执行时间随数据规模的增加而呈指数增长例如递归计算斐波那契数列。O(n!)阶乘复杂度随着n的增加执行时间的增加速度非常快通常见于解决旅行商问题的算法。冒泡排序- 思想通过多次比较和交换相邻的元素将最大或最小的元素逐渐移到列表的末尾。- 时间复杂度最坏情况下是O(n^2)平均情况下也是O(n^2)。- 空间复杂度O(1)原地排序不需要额外空间。def bubble_sort(input_list): 冒泡排序 length len(input_list) if length 2: return input_list for i in range(length): # 外层循环控制轮数 for j in range(length - 1 - i): # 内层循环控制遍历范围 if input_list[j 1] input_list[j]: input_list[j 1], input_list[j] input_list[j], input_list[j 1] return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(冒泡排序 , bubble_sort(input_list)) # 冒泡排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]选择排序- 思想在未排序的数据中选择最小或最大的元素将其放置在已排序部分的末尾。- 时间复杂度最坏情况下是O(n^2)平均情况下也是O(n^2)。- 空间复杂度O(1)原地排序。def select_sort(input_list): 选择排序 length len(input_list) if length 2: return input_list for i in range(length): minIndex i # 初始默认minIndex为未排序列中最小元素对应的索引 for j in range(i 1, length): if input_list[j] input_list[minIndex]: # 如果找到更小元素进行交换 input_list[j], input_list[minIndex] input_list[minIndex], input_list[j] return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(选择排序 , select_sort(input_list)) # 选择排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]A快速排序1- 思想选择一个基准元素将小于基准的元素放在左侧大于基准的元素放在右侧然后递归对左右子数组进行排序。- 时间复杂度最坏情况下是O(n^2)平均情况下是O(n log n)。- 空间复杂度平均情况下是O(log n)最坏情况下是O(n)。def quick_sort1(input_list, left, right): 快速排序 # 直接在原列表上进行操作 def partition(input_list, left, right): # 主要目的是将比基准数小的放到基准数左边比基准数大的放到基准数右边 key left # 划分参考数索引,默认为第一个数为基准数可优化 while left right: # 如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现 while left right and input_list[right] input_list[key]: right - 1 # 如果列表前边的数,比基准数小或相等,则后移一位直到有比基准数大的数出现 while left right and input_list[left] input_list[key]: left 1 # 此时已找到一个比基准大的数和一个比基准小的数将他们互换位置 (input_list[left], input_list[right]) (input_list[right], input_list[left]) # 当从两边分别逼近直到两个位置相等时结束将对应位置的数同基准数进行互换 (input_list[left], input_list[key]) (input_list[key], input_list[left]) # 返回目前基准数所在位置的索引 return left if left right: # 如果已经不能分区开始结束递归调用递归调用结束的判定 return # 从基准开始分区 mid partition(input_list, left, right) # 递归调用 quick_sort1(input_list, left, mid - 1) quick_sort1(input_list, mid 1, right) return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(快速排序1, quick_sort1(input_list, 0, len(input_list) - 1)) # 快速排序1 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]快速排序2def quick_sort2(input_list): 快速排序 # 这个递归的快排会更好理解一些缺点在于不是在原列表上进行操作 if len(input_list) 2: mid input_list[len(input_list) // 2] # 基准数可从待排序列任选 left, right [], [] input_list.remove(mid) for num in input_list: if num mid: right.append(num) else: left.append(num) return quick_sort2(left) [mid] quick_sort2(right) else: return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(快速排序2, quick_sort2(input_list)) # 快速排序2 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]归并排序- 思想将待排序数组分为两个子数组分别对子数组进行排序然后将它们合并成一个有序数组。- 时间复杂度最坏情况下和平均情况下都是O(n log n)。这块有个文章详细解释了快速排序的时间复杂度是怎么算出来的归并排序时间复杂度过程推导详解_java_脚本之家- 空间复杂度O(n)需要额外的空间来合并子数组。def merge_sort(input_list): # 分治法 归并排序 def merge(left, right): # left和right都是有序的 merge_result [] i j 0 while i len(left) and j len(right): if left[i] right[j]: merge_result.append(left[i]) i 1 else: merge_result.append(right[j]) j 1 if i len(left): # 如果left已经追加完毕将right剩下的元素直接追加到末尾 merge_result.extend(right[j:]) else: # 如果right已经追加完毕将left剩下的元素直接追加到末尾 merge_result.extend(left[i:]) return merge_result if len(input_list) 2: return input_list middle len(input_list) // 2 left merge_sort(input_list[:middle]) # 递归调用归并排序 right merge_sort(input_list[middle:]) return merge(left, right) if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(归并排序 , merge_sort(input_list)) # 归并排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]插入排序- 思想将待排序的元素逐个插入到已排序部分的正确位置构建有序序列。- 时间复杂度最坏情况下是O(n^2)平均情况下也是O(n^2)。- 空间复杂度O(1)原地排序。def insert_sort(input_list): 插入排序 length len(input_list) if length 2: return input_list for i in range(1, length): j i target input_list[i] # target要进行插入的元素 while j 0 and target input_list[j - 1]: # 寻找插入位置 input_list[j] input_list[j - 1] j j - 1 input_list[j] target return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(插入排序 , insert_sort(input_list)) # 插入排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]希尔排序def shell_sort(input_list): 希尔排序 def shell_insert(input_list, gap): # gap为组内元素的索引间隔(步长)代码部分参考“插入排序”很像 for i in range(gap, length): # 当gap为1的时候就是等同于插入排序insert_sort j i target input_list[i] # 记录要插入的数,因为input_list[i]的值会被覆盖所以必须提前记录 while j 0 and target input_list[j - gap]: # 对步长为gap的同组数据进行插入排序 # 从后往前直到找到比target小的数的位置 input_list[j] input_list[j - gap] # 向后挪动 j - gap # 未找到之前继续往前一个 input_list[j] target # 将target插入目标位置 length len(input_list) if length 2: return input_list gap length // 2 while gap 1: shell_insert(input_list, gap) gap gap // 2 return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(希尔排序 , shell_sort(input_list)) # 希尔排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]堆排序堆的实现思路1将待排序的序列构造成一个大根堆或小根堆。2将堆顶元素与堆底元素交换并将堆的规模缩小1。3对新的堆顶元素进行向下调整操作使其重新成为大根堆或小根堆。4重复步骤2和3直到堆的规模为1。- 思想将待排序数组构建成最大堆或最小堆然后逐步将堆顶元素与堆尾元素交换调整堆结构重复这个过程直到整个数组有序。- 时间复杂度最坏情况下和平均情况下都是O(n log n)。- 空间复杂度O(1)原地排序。def heap_sort(input_list): 堆排序 def sift_down(input_list, father, end): # 让父节点始终比左右子节点(如果右节点存在的话)的值要大 # end 之后的数据是已经排好序的数据若计算的孩子超出 end 范围则不处理 while True: # 交换之后可能造成被交换的孩子节点作为父节点不再满足堆的性质因此需要重新对交换的孩子节点进行堆初始化 left_child 2 * father 1 # 父节点左孩子节点下标 if left_child end: # 孩子节点不一定还有孩子节点 break # 如果节点的右孩子存在且大于左孩子时此时右孩子为孩子节点中的最大交换时此右节点与父节点交换 # 否则父节点只有左孩子或者左孩子比右孩子要小此时左孩子是孩子节点中最大的交换时此左节点与父节点交换 if left_child 1 end and input_list[left_child 1] input_list[left_child]: left_child left_child 1 # 若上一个if语句执行则以下代码是右子节点与父节点交换否则为左子节点与父节点交换 if input_list[left_child] input_list[father]: input_list[left_child], input_list[father] input_list[father], input_list[left_child] father left_child # 调换后子节点可能不满足大顶堆被调换的子节点重新作为父节点继续进行调整操作 else: break length len(input_list) first length // 2 - 1 # 最后一个有孩子的节点的下标 for i in range(first, -1, -1): # 从最后一个有子节点的节点开始往上调整最大堆 sift_down(input_list, i, length - 1) for head_end in range(length - 1, 0, -1): input_list[head_end], input_list[0] input_list[0], input_list[head_end] # 头尾对调同时堆开始变小 sift_down(input_list, 0, head_end - 1) # father0 表示交换以后自顶向下重新调整大顶堆 return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(堆排序 , heap_sort(input_list)) # 堆排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]计数排序- 思想适用于非负整数的排序算法通过统计每个元素出现的次数来进行排序。- 时间复杂度最坏情况下和平均情况下都是O(n k)其中k是非负整数的范围。- 空间复杂度O(k)。def count_sort(input_list): 计数排序 length len(input_list) if length 2: return input_list max_num max(input_list) count [0] * (max_num 1) for element in input_list: count[element] 1 # 间接使用索引来存储数 input_list.clear() for i in range(max_num 1): # 元素[0, 1, 2, ..., max_num] # input_list.extend([i] * count[i]) # 下面两条语句可以用这条语句替代 for j in range(count[i]): # count[i]表示元素i出现的次数如果有多次重复追加 input_list.append(i) return input_list # 下面这种代码思想也可以达到相同的目的只不过中间涉及到元素间的比较与计数排序的思想稍有差异。 # count [0] * length # for i in range(length): # p 0 # q 0 # for j in range(length): # # 全表查找比input_list[i]小的元素个数pq是为了保证相同元素重复出现时仍然能够正常排序 # # 这块的元素比较使得它算不上真正意义上的计数排序不过思想倒是已经很不错。 # if input_list[j] input_list[i]: # p 1 # elif input_list[j] input_list[i]: # q 1 # # count[p] input_list[i] # for k in range(p, p q): # 如果没有重复元素最终可得q1这里其实就可以写成 count[p] input_list[i] 了 # count[k] input_list[i] # return count if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(计数排序 , count_sort(input_list)) # 计数排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]桶排序def bucket_sort(input_list): 桶排序 big max(input_list) num big // 10 1 # 以10为等差计算桶的数目 buckets [[] for i in range(0, num)] # 初始化桶 for i in input_list: buckets[i // 10].append(i) # 划分桶 for i in buckets: # 桶内排序桶内快速排序 quick_sort1(i, 0, len(i) - 1) # 对原列表进行修改所以无需返回新的排序后的列表 # bucket quick_sort2(i) # 返回新的列表不是在原列表上修改 # buckets[buckets.index(i)] bucket # 根据桶的划分每个桶是不一样的所以我这儿用index函数查找每个桶的索引位置 output_list [] for i in buckets: output_list.extend(i) # for j in i: # output_list.append(j) return output_list def quick_sort1(input_list, left, right): 快速排序 # 直接在原列表上进行操作 def partition(input_list, left, right): # 主要目的是将比基准数小的放到基准数左边比基准数大的放到基准数右边 key left # 划分参考数索引,默认为第一个数为基准数可优化 while left right: # 如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现 while left right and input_list[right] input_list[key]: right - 1 # 如果列表前边的数,比基准数小或相等,则后移一位直到有比基准数大的数出现 while left right and input_list[left] input_list[key]: left 1 # 此时已找到一个比基准大的数和一个比基准小的数将他们互换位置 (input_list[left], input_list[right]) (input_list[right], input_list[left]) # 当从两边分别逼近直到两个位置相等时结束将对应位置的数同基准数进行互换 (input_list[left], input_list[key]) (input_list[key], input_list[left]) # 返回目前基准数所在位置的索引 return left if left right: # 如果已经不能分区开始结束递归调用递归调用结束的判定 return # 从基准开始分区 mid partition(input_list, left, right) # 递归调用 quick_sort1(input_list, left, mid - 1) quick_sort1(input_list, mid 1, right) return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(桶排序 , bucket_sort(input_list)) # 桶排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]基数排序- 思想适用于整数或字符串的排序算法将数据按位数进行排序从最低位到最高位。- 时间复杂度最坏情况下和平均情况下都是O(nk)其中k是位数。- 空间复杂度O(n k)。def radix_sort(input_list, radix10): 基数排序 # import math # K math.ceil(math.log(max(input_list), radix)) # 用K位数可表示任意整数 K 1 # 也可不用 import math 模块 毕竟简单算法尽量不要用库函数 for element in input_list: while True: if element radix ** K: K 1 else: break # K表示最大数的位数比如最大数为897则K3 bucket [[] for i in range(radix)] # 不能用 [[]]*radix (看完下面几条语句你就会明白为什么) # bucket [[]] * radix # [[], [], [], [], [], [], [], [], [], []] # aa [[]] * 10 # 一改具改 # bb [[] for i in range(10)] # aa bb # 尽管有 # True # aa[0] is aa[1] # True # bb[0] is bb[1] # 但是 # False # [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] # [[50], [], [2], [3], [44, 4], [5, 15], [36, 26, 46], [47, 27], [38, 48], [19]] # [50, 2, 3, 44, 4, 5, 15, 36, 26, 46, 47, 27, 38, 48, 19] # [[2, 3, 4, 5], [15, 19], [26, 27], [36, 38], [44, 46, 47, 48], [50], [], [], [], []] # [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] for i in range(K): # K次循环 for val in input_list: bucket_index val % (radix ** (i 1)) // (radix ** i) # 把val放到bucket_index对应的这个桶 # example 4789 % 10**3 // 10**2 7 bucket[bucket_index].append(val) # 析取整数第K位数字 从低到高 个十百千... input_list.clear() for each in bucket: input_list.extend(each) # 桶合并 bucket [[] for i in range(radix)] return input_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(基数排序 , radix_sort(input_list)) # 基数排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]睡眠排序这个算法虽然是拿来搞笑的但他毕竟也是正儿八经的可以排序出来的。import time import threading def sleep_sort(input_list): # 哈哈调皮一下顺便学学join和守护线程的用法如果max(input_list)比较大的话建议放弃尝试 睡眠排序 output_list [] thread_list [] def do_sleep(i): # 统一乘了一个系数总不能让我真的等i秒 time.sleep(i / 100) # 只要sleep时间不会过于短在毫秒级别以上应该都是可以分出先后的再短就悬了 output_list.append(i) for i in input_list: t threading.Thread(targetdo_sleep, args(i,)) thread_list.append(t) for t in thread_list: # 对每个线程设置守护并开启主线程结束以后会杀死子线程 t.setDaemon(True) t.start() for t in thread_list: # join 所完成的工作就是线程同步避免主线程提前结束以后直接终止掉了子线程 t.join() # 即主线程任务结束之后进入阻塞状态一直等待其他的子线程执行结束之后才继续 # t.join(timeout0.02) # 主线程将会累计等待timeout*len(input_list)这么多秒时间一到强行终止返回当前已排序结果 return output_list if __name__ __main__: input_list [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] print(睡眠排序 , sleep_sort(input_list)) # 睡眠排序 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]