# coding=gbk# 注意1："//"才是整除: 6//5=1, 6/5=1.2# 注意2：range(5,-1,-1)为5、4、3、2、1、0# 注意3：其实你以前写的插排并不对# 注意4：把待排序的数想成高低不平的柱状图，更能够理清思路# 算法总结系列之五: 基数排序(Radix Sort) http://www.cnblogs.com/sun/archive/2008/06/26/1230095.html# 十大排序算法及其实现（C++ & Python） https://blog.csdn.net/Koala_Tree/article/details/79958965# 面试中的 10 大排序算法总结 http://www.codeceo.com/10-sort-algorithm-interview.html#0-tsina-1-10490-397232819ff9a47a7b7e80a40613cfe1# 冒泡排序: 两两冒泡交换，最大的放后面# 选择排序：选出最大数的位置，一次交换放后面。# 希尔排序：多次缩小增量的插入排序# 快速排序：一遍扫描，比基准小的交换到前面，递归# 归并排序：将排好序的列表合并起来# 堆排序：初始化堆，调整堆顶，选出最大的元素，一次交换放后面，和选择排序类似# 桶排序：造桶，放元素，排序，取元素# 计数排序：是造桶最多的桶排序# 基数排序：从最低位到最高位，对该位进行计数排序import randomlist = [1,234,32,4,4234,454325,534,345,353,53,2134,324,23,42,4,12,534,56,43,234,-8,23]sort_list = [-8, 1, 4, 4, 12, 23, 23, 32, 42, 43, 53, 56, 234, 234, 324, 345, 353, 534, 534, 2134, 4234, 454325]print("原数组：")print(list)print("正确的顺序：")print(sort_list)def bubble_sort(list): """ 冒泡排序:两两冒泡交换，最大的放后面 注意：一重循环为大的循环次数（固定为len-1） 二重循环为下标的取值范围（一直在变小） """ for i in range(0, len(list)-1): for j in range(0, len(list)-1-i): if list[j] > list[j+1]: list[j], list[j+1] = list[j+1], list[j]def select_sort(list): """ 选择排序：选出最大数的位置，一次交换放后面。 和冒泡排序比较： 冒泡排序是两两冒泡交换，选出最大的放后面 选择排序是选出最大数的位置，一次交换放后面。大大减少了交换的次数 """ for i in range(len(list)-1, 0, -1):# 用i表示最大数该放的位置 max_index = i# 表示暂定的最大数的下标 for j in range(i-1, -1, -1):# j用来遍历i前面所有的位置，找出最大数的位置 if list[j] > list[max_index]: max_index = j if max_index != i: list[max_index], list[i] = list[i], list[max_index]def insert_sort(list): """ 插入排序： 从前往后，依次取出元素，插入前面已经排好序的列表 """ for i in range(1, len(list), 1):# 用i表示待插入元素的下标 for j in range(i-1, -1, -1):# 用j遍历i前面所有的有序的数组，找到要插入的位置 if list[j] > list[j+1]: list[j],list[j+1] = list[j+1],list[j] else: breakdef shell_sort(list): """ 希尔排序：多次缩小增量的插入排序 """ increment = len(list)//2 while increment>0: for i in range(1, len(list)):# i表示待插入数字的下标 for j in range(i-1, -1, -1):# 用j遍历i前面的有序数组 if list[j] > list[j+1]: list[j],list[j+1] = list[j+1],list[j] else: break increment//=2def quick_sort(list, start, end): """ 快速排序：一遍扫描，比基准小的交换到前面，递归 """ if end <= start: return p = start for i in range(start, end): if list[i] < list[end]: list[i], list[p] = list[p], list[i]# 一遍扫描，比基准小的交换到前面 p+=1 list[p],list[end] = list[end],list[p] quick_sort(list, start, p-1) quick_sort(list, p+1, end)def merge_sort(list, start, end): """ 归并排序：将排好序的列表合并起来 注意1：合并时将最小的pop出来添加到新的列表 注意2：返回值才是排好序的列表 """ def merge(list, start, end): if end == start: return [list[end]] a = merge(list, start, (start+end)//2) b = merge(list, (start+end)//2+1, end) c = [] while a != [] and b != []: c.append(a.pop(0) if a[0] < b[0] else b.pop(0)) c.extend(a+b) return c a = merge(list, start, end) list.clear() list.extend(a)def head_adjust(list, father, end): """ 调整堆顶，把堆顶放到它应放的位置上 注意1：把数组映射成一颗完全二叉树后，编号为i的节点子节点编号为2i+1，2i+2，父节点编号为（i-1）//2 注意2：具体解释见：http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/ """ # 如果左孩子存在且左孩子大或者右孩子存在且右孩子大，则需要调整 if end-father <= 0: return while (father*2+1 <= end and list[father] < list[father*2+1]) or (father*2+2 <= end and list[father] < list[father*2+2]): if father*2+2 <= end and list[father*2+1] < list[father*2+2]:# 右孩子存在且右孩子大 son = father*2+2 else: son = father*2+1 list[father],list[son] = list[son], list[father] father = sondef heap_sort(list): """ 堆排序：初始化堆，调整堆顶，选出最大的元素，一次交换放后面，和选择排序类似 """ # 初始化堆，从最后一个父节点开始调整堆 for father in range(len(list)//2-1, -1, -1): head_adjust(list, father, len(list)-1) # i为堆顶最终的位置， for i in range(len(list)-1, 0, -1): list[i], list[0] = list[0],list[i] head_adjust(list, 0, i-1)def count_sort(list): """ 计数排序：时间为o（n）,也可以用桶排序实现计数排序 注意1：需要的空间和list里面的最大值相同 注意2：辅助的数组，下标表示值，内容为该值出现的次数 注意3：只能对一定范围内的整数进行排序 注意4：要对表进行处理，把表里面的正数转换为负数 """ min_value = min(list) for i in range(0, len(list)): # 把表里面的负数转换为正数 list[i] += abs(min_value) arr = [0]*(max(list)+1)#arr是辅助的数组，下标表示值，内容为该值出现的次数 for i in list: arr[i]+=1 k = 0 for i in range(0, len(arr)): while arr[i] > 0: list[k] = i arr[i] -= 1 k += 1 for i in range(0, len(list)):# 把表里面的数据还原 list[i] -= abs(min_value)def bucket_sort(list): ''' 桶排序：造桶，放元素，排序，取元素 计数排序：是造桶最多的桶排序 ''' min_value = min(list) for i in range(0, len(list)): # 把表里面的负数转换为正数 list[i] += abs(min_value) bucket_num = max(list)//10+1# 桶的数量 bucket = [[] for i in range(bucket_num)]# 造出bucket_num个桶 for i in list:# 扫描list所有元素放入桶里面 bucket[i//10].append(i) for i in range(bucket_num):# 对每个桶里面的元素进行快排 quick_sort(bucket[i], 0, len(bucket[i])-1) k = 0 for i in range(bucket_num):# 一次扫描，取出桶里面排好序的元素 while bucket[i] != []: list[k] = bucket[i].pop(0) k += 1 for i in range(0, len(list)):# 把表里面的数据还原 list[i] -= abs(min_value)import mathdef radix_sort(list): ''' 基数排序：从最低位到最高位，对该位进行计数排序 注意1：要对表进行处理，把表里面的正数转换为负数 ''' min_value = min(list) for i in range(0, len(list)): # 把表里面的负数转换为正数 list[i] += abs(min_value) max_length = len(str(max(list))) for i in range(0, max_length): bucket = [[] for i in range(10)]# 造10个桶 for j in list: bucket[j//(10**i) % 10].append(j)# 放元素 k = 0 for i in range(0, 10):# 取元素 while bucket[i] != []: list[k] = bucket[i].pop(0) k+=1 for i in range(0, len(list)):# 把表里面的数据还原 list[i] -= abs(min_value)radix_sort(list)print(list)print(list == sort_list)