十大排序算法：
	非线性时间比较类：
		交换类：
			冒泡排序
			快速排序
		插入类：
			直接插入排序
			希尔排序
		选择类：
			简单选择排序
			堆排序
		归并类#：
			归并排序
	线性时间排序：
		计数排序
		桶排序
		基数排序

# 冒泡排序
def bubble_sort(nums):
    # 冒泡排序进行的次数n-1,每次遍历确定一个最大值
    for i in range(len(nums)-1):
        # j为进行比较的数据下标
        for j in range(len(nums)-1-i):
            # 若下标为j的数据大于其右相邻数据
            if nums[j] > nums[j+1]:
                # 二者交换数据
                nums[j],nums[j+1] = nums[j+1],nums[j]
    return nums

# 快速排序
def quick_sort(array):
    if len(array)<=1:			# 当子序列长度<=1
        return array			# 排序完成,停止递归
    else:
        small = []				# 由所有小于基准值的元素组成的子数组
        equal = []				# 包括基准值在内并且和基准相等的元素
        large = []				# 由所有大于基准值的元素组成的子数组
        reference = array[0]	 # 选择第一个数作为基准值
        # 遍历array中的每一个元素
        for s in array:
            # 当前元素小于基准值时
            if s < reference:
                # 当前元素插入small
                small.append(s)
            # 当前元素等于基准值
            elif s == reference:
                equal.append(s)
            # 当前元素大于基准值
        	else:
                large.append(s)
            print(small,equal,large)
    # 调用自身，即为递归
    return quick_sort(small) + equal + quick_sort(large)

def quick_sort(array):
    if len(array) <= 1:
        return array
    else:
        reference = array[0]
        small = [s for s in array[1:] if s < reference]
        equal = [e for e in array if e == reference]
        large = [l for l in array[1:] if l > reference]
    return quick_sort(small) + equal + quick_sort(large)

# 直接插入排序
def inset_sort(array):
    n = len(array)
    # 切记是从1到n-1，前闭后开
    for i in range(1,n):
    	# 如果待插入数据小于前一个数据
        if array[i] < array[i-1]:
            # index为待插入的下标
            index = i
            # 将待插入的数据放在temp中
            temp = array[i]
            # 从i-1循环到0,反向取值，间距为1
            # 前两个参数为区间范围，第三个参数为取值方向和大小
            for j in range(i-1,-1,-1):
                # 如果array[j]大于temp
                if array[j] > temp:
                    # 将array[j]后移一位
                    array[j+1] = array[j]
                    # 更新待插入的下标
                    index = j
                # 如果array[j]小于或等于temp
            	else:
                    # 跳出并结束
                    break
            # 将temp插入有序子数列
            array[index] = temp
       # 如果待插入数据大于前一个数据，则不需要移动
    return array

# 希尔排序
def shell_sort(array):
    # 设定初始增量d=n/2
    d = len(array)//2
    # 当增量大于0时执行,如果小于0,则退出循环
    while d>0:
        # i 的取值范围为d到n
        for i in range(d,len(array)):
            # 类似直接插入排序，比较当前值与指定增量的值
            while i>=d and array[i-d]>array[i]:
                # 符号条件则交换
                array[i],array[i-d] = array[i-d],array[i]
                # 取前一个指定增量的值，继续下一个判断
                i -= d
        # 将增量取半,回到while循环
        d = d//2
    return array

# 简单选择排序
def select_sort(array):
    # 从0遍历到待排序数组的长度len(array)-1
    for i in range(len(array)-1):
        # smallest为最小值的index，初始默认为当前的i
        smallest = i
        # j为比较index,从当前的index的下一位到数组结束
        for j in range(i+1,len(array)):
            # 如果当前最小值大于当前值
            if array[smallest]>array[j]:
                # 则二者交换位置
                array[smallest],array[j] = array[j],array[smallest]
    return array

# 堆排序
def heap_sort(array):
    """
    需要注意两点：
    （1）递归思想
    （2）切片思想
    """
    length = len(array)
    # 当数组array的长度为1时，说明只有一个元素
    if length <= 1:
        return array
    # 若存在两个及以上的节点
	else:
        # 调整为大顶堆，按照从下往上从左往右的顺序进行调整
        # 从最后一个非叶子节点开始想前遍历，直到根节点
        for i in range(len(array)//2-1,-1,-1):
            # 当左孩子大于父节点
            if array[2*i+1]>array[i]:
                # 交换位置
                array[2*i+1],array[i] = array[i],array[2*i+1]
            # 如果右孩子存在且大于父节点
            if 2*i+2 <= length-1:
                if array[2*i+2]>array[i]:
                    # 交换位置
                    array[2*i+2],array[i] = array[i],array[2*i+2]
        '''此处省略剩余数组重构过程,对结果无影响'''
        # 将堆顶元素与末尾元素进行交换
        array[0],array[length-1] = array[length-1],array[0]
        # 递归调用heap_sort函数堆前n-1个元素进行堆排序并返回堆排序后的结果
        return heap_sort(array[0:length-1]) + array[length-1:]

# 归并排序
def merge(left,right):
    """
    两个有序子序列的有序合并：
    依次对两个有序列表的最小数进行比较，较小的放入result中
    :param left: 左子序列
    :param right: 右子序列
    :return: 左右子序列所合成的有序序列
    """
    # result: 存好已经排序的数组
    result = []
    # 如果不符合左右子序列长度均大于0,则说明至少其中的一个数组已经无数据了
    while len(left)>0 and len(right)>0:
        # 相等的时候优先把左侧的数放进结果列表，以保证其稳定性
        if left[0] <= right[0]:
            # list.pop(0)为移除并返回数组的第一个值
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    # 跳出while循环后,我们便可以把另一个数组尽数加入result后面
    result += left
    result += right
    return result

def merge_sort(array):
	"""
	无序序列的不断拆分
	每次均由中间位置进行拆分,不断自我递归调用，直到子序列长度为1
	"""
    # 如果拆分后仅有单个元素，则返回该元素而不拆分
    if len(array) == 1:
        return array
    # 如果有两个以上元素，则从中间位置开始拆分
    middle = len(array)//2
    # 拆分后的左侧子串
    array_left = array[:middle]
    # 拆分后的右侧子串
    array_right = array[middle:]
    # 对拆分后的左右子串序列再进行拆分，直到len(arr)=1
    left = merge_sort(array_left)
    right = merge_soort(array_right)
    # 合并已拆分的左右子序列的同时进行排列并返回排列后的结果
    return merge(left,right)

# 计数排序
def count_sort(arr):
    # 计算序列的最大值和最小值
    maximum,minimum = max(arr),min(arr)
    # 申请额外的空间作为计数数组,大小为最大值减最小值+1
    countArr = [0 for i in range(maximum-minimum+1)]
    # 申请一个存放已排序序列的等长空间
    finalArr = [0 for i in range(len(arr))]
    # 统计各元素出现的次数,并将统计结果存入计数数组
    for i in arr:
        # 出现一次就加1
        countArr[i-minimum] += 1 	# 注意下标index = data - min
    # 对计数数组进行累加
    for i in range(1,len(countArr)):
        # 从第二个位置开始,每个每个位置的值等于其本身加上前者
        countArr[i] += countArr[i-1]
    # 开始将元素反向填充到最终的数组中
    for i in arr:
        finalArr[countArr[i-minimum]-1] = i
        # 填充了一个就减一
        countArr[i-minimum] -= 1
    return finalArr

# 桶排序
def bucket_sort(arr):
    maximum,minimum = max(arr),min(arr)
    # 确定桶的个数
    buckets = [[] for i in range(maximum-minimum)//10+1]
    for i in arr:
        # 计算各元素的所属的桶位
        index = (i - minimum)//10
        # list.append()---添加元素
        buckets[index].append(i)
    # 将原数组清空
    arr.clear()
    for i in buckets:
        # 桶内排序---堆排序(可以用别的替代)
        i = heap_sort(i)
        # 将已排序的桶重新放回已经清空的原数组中
        arr.extend(i)
    return arr

# 基数排序
def radix_sort(arr):
    maximum = max(arr)	 # 确定待排序数组中的最大位数
    d = 0				# 用d记录最大位数 
    while maximum!=0:
        maximum = maximum//10
        d += 1
    # d轮排序
    for i in range(d):					
        # 因为每一位数字都是0~9，所以建十个桶
        s = [[] for k in range(10)]		 
        for j in arr:
            # 从个位数开始注意进行分桶操作
            s[int(j/(10**i))%10].append(j)
        # 用10个桶回填原数组
        arr = [a for b in s for a in b]
    return arr