算法简述

冒泡

原理：冒泡排序就是遍历数据，每次只与下一个数字比较，如果这两个数顺序不对，则与交换过来。

桶排序

原理：桶排序也叫计数排序，简单来说，就是将数据集里面所有元素按顺序列举出来，然后统计元素出现的次数。最后按顺序输出数据集里面的元素。但是桶排序非常浪费空间, 比如需要排序的范围在0~2000之间, 需要排序的数是[3,9,4,2000], 同样需要2001个空间。优点就是特别快。注意: 桶排序不能排序小数

快排

原理：快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。 步骤为：挑选基准值--从数列中挑出一个元素，称为"基准";
分割-重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成; 递归排序子序列--递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

选择排序

原理：选择排序的思路是固定位置，选择排序，即：先从序列中，找到最小的元素，放到第一个位置，然后找到第二小的元素，放到第二个位置，以此类推，直到排好所有的值。

插入排序

原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

排序比较

排序算法比较.png

实例：

s = [1,3,4,5,2,7,9,1]
冒泡的具体流程：

冒泡排序.png

桶排序的具体流程：

桶排序.png
快排的具体流程
快排.png
选择排序的具体流程
选择排序.png

插入排序的具体流程

插入排序.png

代码：

import time

def outer(func):
    def wrapper(*agrs,**kwargs):
        start_time = time.time()
        res = func(*agrs, **kwargs)
        end_time = time.time()
        print(end_time - start_time)
        return res
    return wrapper

# 冒泡排序
@outer
def bub_sort(s_list):
    if len(s_list)<=1:
        return s_list
    for i in range(len(s_list)-1):
        for j in range(len(s_list)-1-i):
            if s_list[j] > s_list[j+1]:
                s_list[j],s_list[j+1] = s_list[j+1],s_list[j]
    return s_list

# 桶排序
@outer
def bucket_sort(s_list):
    if len(s_list)<=1:
        return s_list
    # 选择一个最大的数
    max_num = max(s_list)
    # 创建一个元素全是0的列表, 当做桶
    bucket = [0]*(max_num+1)
    # 把所有元素放入桶中, 即把对应元素个数加一
    for i in s_list:
        bucket[i] +=1
    # 声明存储排序好的元素
    sort_nums = []
    # 取出桶中的元素
    for j in range(len(bucket)):
        if bucket[j]!=0:
            for y in range(bucket[j]):
                sort_nums.append(j)
    return sort_nums


# 快速排序
def quick_sort(s_list):
    if len(s_list)<=1:
        return s_list
    base = s_list[0]
    left = [x for x in s_list[1:] if x <= base]
    right = [x for x in s_list[1:] if x > base]
    return quick_sort(left)+[base]+quick_sort(right)

# 由于存在递归调用，所以需要单独一个函数来调用快速排序方法，否则装饰器会多次打印消耗时间
@outer
def call_quick_sort(s_list):
    return quick_sort(s_list)

# 选择排序
@outer
def select_sort(s_list):
    if len(s_list) <= 1:
        return s_list
    for i in range(len(s_list)-1):
        min_index = i
        for j in range(i+1,len(s_list)-1):
            if s_list[min_index]>s_list[j]:
                min_index =j
        s_list[i],s_list[min_index] = s_list[min_index],s_list[i]
    return s_list

@outer
def inert_sort(s_list):
    for i in range(1, len(s_list)):
        if s_list[i-1] > s_list[i]:
            tmp = s_list[i]
            seq = i
            while seq > 0 and s_list[seq-1] > tmp:
                s_list[seq] = s_list[seq-1]
                seq -= 1
            s_list[seq] = tmp
    return s_list

s = [1,3,4,5,2,7,9,1,8]
print(bub_sort(s))
print(bucket_sort(s))
print(call_quick_sort(s))
print(select_sort(s))
print(inert_sort(s))