# 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 random
list = [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:
break
def 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//=2
def 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 = son
def 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 math
def 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)
