01排序算法之冒泡

#gen_random_list(num) 其中num为生成随机数的个数
#check_li_sorted(li,desc=False) 判断元素是否有序(默认从小到大,desc决定时候按照反序来检测)
from base import check_li_sorted,gen_random_list

#冒泡排序的雏形:
#我们在这里建立一个对于5个元素构成的随机数组的排序
def buble_sort_list_5():
    li=gen_random_list(5)
    print("original li:{}".format(li))

    len_li=len(li)

    for i in range(0,len_li-1): # i in [0,1,2,3]
        if li[i]>li[i+1]:
            li[i],li[i+1]=li[i+1],li[i]
    #完成这轮循环后这5个随机数中最大值的位置肯定位于第5个位置(索引为4的位置)

    for i in range(0,len_li-2): # i in [0,1,2]
        if li[i]>li[i+1]:
            li[i],li[i+1]=li[i+1],li[i]
    #完成这轮循环前4个随机数中最大值的位置肯定位于第4个位置(索引为3的位置)

    for i in range(0,len_li-2): # i in [0,1]
        if li[i]>li[i+1]:
            li[i],li[i+1]=li[i+1],li[i]
    #完成这轮循环前3个随机数中最大值的位置肯定位于第4个位置(索引为2的位置)

    for i in range(0,len_li-1): # i in [0]
        if li[i]>li[i+1]:
            li[i],li[i+1]=li[i+1],li[i]
    #完成这轮循环前2个随机数中最大值的位置肯定位于第4个位置(索引为1的位置)
    #剩下来的那个元素肯定是最小的元素，位于第1个位置(索引为0)


    print("sorted li:{}".format(li))
'''
例如:
    buble_sort_list_5()
输出为:
    original li:[99, 12, 21, 80, 90]
    sorted li:[12, 21, 80, 90, 99]
'''


'''
接下来我们推广一下
下面我们来看下冒泡过程
'''
def bubble_sort_list_range(li):
    len_li=len(li)
    #当传入列表的长度为0或者1的时候，直接返回
    if len_li in (0,1):
        return li
    for i in range(len_li,1,-1):
        print([_ for _ in range(i-1)]," 在此过程中，我们通过比较交换相邻元素将最大值移到位置",i,"索引为",i-1,"其中",[_ for _ in range(i-1,len_li)],'为有序的')
'''
例如:
    bubble_sort_list_range(gen_random_list(10))   
输出为:
    [0, 1, 2, 3, 4, 5, 6, 7, 8]  在此过程中，我们通过比较交换相邻元素将最大值移到位置 10 索引为 9 其中 [9] 为有序的
    [0, 1, 2, 3, 4, 5, 6, 7]  在此过程中，我们通过比较交换相邻元素将最大值移到位置 9 索引为 8 其中 [8, 9] 为有序的
    [0, 1, 2, 3, 4, 5, 6]  在此过程中，我们通过比较交换相邻元素将最大值移到位置 8 索引为 7 其中 [7, 8, 9] 为有序的
    [0, 1, 2, 3, 4, 5]  在此过程中，我们通过比较交换相邻元素将最大值移到位置 7 索引为 6 其中 [6, 7, 8, 9] 为有序的
    [0, 1, 2, 3, 4]  在此过程中，我们通过比较交换相邻元素将最大值移到位置 6 索引为 5 其中 [5, 6, 7, 8, 9] 为有序的
    [0, 1, 2, 3]  在此过程中，我们通过比较交换相邻元素将最大值移到位置 5 索引为 4 其中 [4, 5, 6, 7, 8, 9] 为有序的
    [0, 1, 2]  在此过程中，我们通过比较交换相邻元素将最大值移到位置 4 索引为 3 其中 [3, 4, 5, 6, 7, 8, 9] 为有序的
    [0, 1]  在此过程中，我们通过比较交换相邻元素将最大值移到位置 3 索引为 2 其中 [2, 3, 4, 5, 6, 7, 8, 9] 为有序的
    [0]  在此过程中，我们通过比较交换相邻元素将最大值移到位置 2 索引为 1 其中 [1, 2, 3, 4, 5, 6, 7, 8, 9] 为有序的
'''

'''
到这一步我们结合上面的分析，来写个冒泡吧
'''
def bubble_sort_list(li):
    len_li=len(li)
    #当传入列表的长度为0或者1的时候，直接返回
    if len_li in (0,1):
        return li
    for i in range(len_li,1,-1):
        #为了将当前无序范围中的最大值放到指定的位置
        for j in range(i-1):
            if li[j]>li[j+1]:
                li[j],li[j+1]=li[j+1],li[j]
    return li
'''
例如:
    original_list=gen_random_list(20)
    print('Original List:{}'.format(original_list))
    result_list=bubble_sort_list(original_list)
    print("Sorted List:{}".format(result_list))
    
输出:
    Original List:[72, 59, 37, 81, 81, 47, 74, 65, 40, 63, 43, 60, 99, 43, 67, 38, 86, 42, 51, 92]
    Sorted List:[37, 38, 40, 42, 43, 43, 47, 51, 59, 60, 63, 65, 67, 72, 74, 81, 81, 86, 92, 99] 
'''

'''
接下来我们皮一把，改成尾递归的形式
'''
def bubble_sort_list_recursive(list,i):
    #当传入列表的长度为0或者1的时候，直接返回
    if len(list) in (0,1):
        return list

    if i==0:
        return list
    for j in range(i-1):
        if list[j]>list[j+1]:
            list[j],list[j+1]=list[j+1],list[j]

    return bubble_sort_list_recursive(list,i-1)
'''
例如:
    original_list=gen_random_list(20)
    print('Original List:{}'.format(original_list))
    result_list=bubble_sort_list_recursive(original_list,len(original_list))
    print("Sorted List:{}".format(result_list))

    print('-'*100) 
输出:
    Original List:[45, 91, 72, 20, 95, 19, 75, 85, 44, 79, 16, 86, 80, 90, 38, 54, 40, 92, 75, 81]
    Sorted List:[16, 19, 20, 38, 40, 44, 45, 54, 72, 75, 75, 79, 80, 81, 85, 86, 90, 91, 92, 95]
    ----------------------------------------------------------------------------------------------------
'''

'''
为了避免每次使用的时候都用傻逼的len(list),我们这里用个装饰器
'''
import functools
def wrap(func):
    @functools.wraps(func)
    def inner(*args):
        return func(args[0],len(args[0]))
    return inner
#升级版，利用装饰器
@wrap
def bubble_sort_list_recursive_upper(list,i):
    if i==0:
        return list
    for j in range(i-1):
        if list[j]>list[j+1]:
            list[j],list[j+1]=list[j+1],list[j]

    return bubble_sort_list_recursive(list,i-1)
'''
例如:
    original_list=gen_random_list(20)
    print('Original List:{}'.format(original_list))
    result_list=bubble_sort_list_recursive_upper(original_list,len(original_list))
    print("Sorted List:{}".format(result_list))

    print('-'*100)
输出:
    Original List:[29, 47, 81, 34, 94, 92, 28, 32, 45, 91, 61, 24, 68, 65, 83, 62, 82, 79, 86, 27]
    Sorted List:[24, 27, 28, 29, 32, 34, 45, 47, 61, 62, 65, 68, 79, 81, 82, 83, 86, 91, 92, 94]
    ----------------------------------------------------------------------------------------------------  
'''