#gen_random_list(num) 其中num為生成隨機數(shù)的個數(shù)
#check_li_sorted(li,desc=False) 判斷元素是否有序(默認(rèn)從小到大,desc決定時候按照反序來檢測)
from base import check_li_sorted,gen_random_list

#冒泡排序的雛形:
#我們在這里建立一個對于5個元素構(gòu)成的隨機數(shù)組的排序
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]
    #完成這輪循環(huán)后這5個隨機數(shù)中最大值的位置肯定位于第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]
    #完成這輪循環(huán)前4個隨機數(shù)中最大值的位置肯定位于第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]
    #完成這輪循環(huán)前3個隨機數(shù)中最大值的位置肯定位于第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]
    #完成這輪循環(huán)前2個隨機數(shù)中最大值的位置肯定位于第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)
    #當(dāng)傳入列表的長度為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] 為有序的
'''

'''
到這一步我們結(jié)合上面的分析，來寫個冒泡吧
'''
def bubble_sort_list(li):
    len_li=len(li)
    #當(dāng)傳入列表的長度為0或者1的時候侦锯，直接返回
    if len_li in (0,1):
        return li
    for i in range(len_li,1,-1):
        #為了將當(dāng)前無序范圍中的最大值放到指定的位置
        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):
    #當(dāng)傳入列表的長度為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]
    ----------------------------------------------------------------------------------------------------  
'''