from base import gen_random_list

#選擇排序
'''
核心思想:
    假設(shè)無序數(shù)組長度為N,總共要遍歷N-1趟
    第一趟:遍歷第一個數(shù)據(jù)以及其往后的每個元素，找出最小的數(shù),遍歷完后，將第一個位置與這趟遍歷找到的最小的那個數(shù)交換位置
    第二趟:遍歷第二個數(shù)據(jù)以及其往后的每個元素敏簿，找出最小的數(shù),遍歷完后，將第二個位置與這趟遍歷找到的最小的那個數(shù)交換位置
    第三趟:遍歷第三個數(shù)據(jù)以及其往后的每個元素乘寒，找出最小的數(shù),遍歷完后，將第三個位置與這趟遍歷找到的最小的那個數(shù)交換位置
    ....
    第N-2趟:遍歷第N-2個數(shù)據(jù)以及其往后的每個元素，找出最小的數(shù),遍歷完后驹马，將第N-2個位置與這趟遍歷找到的最小的那個數(shù)交換位置
    第N-1趟:遍歷第N-1個數(shù)據(jù)以及其往后的每個元素牲蜀，找出最小的數(shù),遍歷完后笆制，將第N-1個位置與這趟遍歷找到的最小的那個數(shù)交換位置
'''

#選擇排序的雛形
#我們在這里建立一個對于5個元素構(gòu)成的隨機數(shù)組的排序
def select_sort_list_5():
    li=gen_random_list(5)
    print('original li:{}'.format(li))

    len_li=len(li)

    min_index=0
    for i in range(0,len_li):  # i in [0,1,2,3,4]
        if li[min_index]>li[i]:
            min_index=i
    li[min_index],li[0]=li[0],li[min_index]
    #完成這輪循環(huán)我們將第一個數(shù)據(jù)以及其往后的每個元素中的最小的那個數(shù)與第一個位置的元素交換位置

    min_index=1
    for i in range(1,len_li): # i in [1,2,3,4]
        if li[min_index]>li[i]:
            min_index=i
    li[min_index],li[1]=li[1],li[min_index]
    #完成這輪循環(huán)我們將第二個數(shù)據(jù)以及其往后的每個元素中的最小的那個數(shù)與第二個位置的元素交換位置

    min_index=2
    for i in range(2,len_li): # i in [2,3,4]
        if li[min_index]>li[i]:
            min_index=i
    li[min_index],li[2]=li[2],li[min_index]
    #完成這輪循環(huán)我們將第三個數(shù)據(jù)以及其往后的每個元素中的最小的那個數(shù)與第三個位置的元素交換位置

    min_index=3
    for i in range(3,len_li): # i in [3,4]
        if li[min_index]>li[i]:
            min_index=i
    li[min_index],li[3]=li[3],li[min_index]
    #完成這輪循環(huán)我們將第四個數(shù)據(jù)以及其往后的每個元素中的最小的那個數(shù)與第四個位置的元素交換位置

    print('sorted li:{}'.format(li))
'''
例如:
    select_sort_list_5()
輸出為:
    original li:[95, 89, 29, 50, 28]
    sorted li:[28, 29, 50, 89, 95] 
'''


'''
我們來推廣一下
下面我們來看選擇范圍的變化
'''
def select_sort_list_range(li):
    len_li=len(li)
    #當(dāng)傳入列表的長度為0或者1的時候，直接返回
    if len_li in (0,1):
        return li
    for i in range(0,len_li-1):
        print([_ for _ in range(i,len_li)],'再此過程中,獲取出這個范圍中的最小值涣达，并將它與位置為',i+1,'索引為',i,'元素交換位置,完成這次后',[_ for _ in range(0,i+1)],'是有序的')
'''
例如:
    select_sort_list_range(gen_random_list(10))
輸出為:
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 再此過程中,獲取出這個范圍中的最小值在辆，并將它與位置為 1 索引為 0 元素交換位置,完成這次后 [0] 是有序的
    [1, 2, 3, 4, 5, 6, 7, 8, 9] 再此過程中,獲取出這個范圍中的最小值，并將它與位置為 2 索引為 1 元素交換位置,完成這次后 [0, 1] 是有序的
    [2, 3, 4, 5, 6, 7, 8, 9] 再此過程中,獲取出這個范圍中的最小值度苔，并將它與位置為 3 索引為 2 元素交換位置,完成這次后 [0, 1, 2] 是有序的
    [3, 4, 5, 6, 7, 8, 9] 再此過程中,獲取出這個范圍中的最小值匆篓，并將它與位置為 4 索引為 3 元素交換位置,完成這次后 [0, 1, 2, 3] 是有序的
    [4, 5, 6, 7, 8, 9] 再此過程中,獲取出這個范圍中的最小值，并將它與位置為 5 索引為 4 元素交換位置,完成這次后 [0, 1, 2, 3, 4] 是有序的
    [5, 6, 7, 8, 9] 再此過程中,獲取出這個范圍中的最小值寇窑，并將它與位置為 6 索引為 5 元素交換位置,完成這次后 [0, 1, 2, 3, 4, 5] 是有序的
    [6, 7, 8, 9] 再此過程中,獲取出這個范圍中的最小值鸦概，并將它與位置為 7 索引為 6 元素交換位置,完成這次后 [0, 1, 2, 3, 4, 5, 6] 是有序的
    [7, 8, 9] 再此過程中,獲取出這個范圍中的最小值，并將它與位置為 8 索引為 7 元素交換位置,完成這次后 [0, 1, 2, 3, 4, 5, 6, 7] 是有序的
    [8, 9] 再此過程中,獲取出這個范圍中的最小值疗认，并將它與位置為 9 索引為 8 元素交換位置,完成這次后 [0, 1, 2, 3, 4, 5, 6, 7, 8] 是有序的
        
'''

'''
到這一步我們結(jié)合上面的分析完残，來寫個選擇吧
'''
def select_sort_list(li):
    len_li=len(li)
    #當(dāng)傳入列表的長度為0或者1的時候伏钠，直接返回
    if len_li in (0,1):
        return li
    for i in range(0,len_li-1):
        min_index=i
        for j in range(i,len_li):
            if li[min_index]>li[j]:
                min_index=j
        li[min_index],li[i]=li[i],li[min_index]
    return li
'''
例如:
    original_list=gen_random_list(20)
    print('Original List:{}'.format(original_list))
    result_list=select_sort_list(original_list)
    print('Sorted List:{}'.format(result_list))

輸出:
    Original List:[100, 86, 58, 94, 79, 28, 45, 22, 31, 86, 64, 97, 97, 16, 64, 56, 72, 38, 61, 22]
    Sorted List:[16, 22, 22, 28, 31, 38, 45, 56, 58, 61, 64, 64, 72, 79, 86, 86, 94, 97, 97, 100]
'''

'''
還是和上次一樣，寫一個尾遞歸的版本看看
'''
def select_sort_list_recursive(li,i=0):
    len_li=len(li)
    if len_li in (0,1):
        return li

    if i==len_li:
        return li
    min_index=i
    for j in range(i,len_li):
        if li[min_index]>li[j]:
            min_index=j
    li[min_index],li[i]=li[i],li[min_index]
    return select_sort_list_recursive(li,i+1)
'''
例如:
    original_list=gen_random_list(20)
    print('Original List:{}'.format(original_list))
    result_list=select_sort_list_recursive(original_list)
    print('Sorted List:{}'.format(result_list))
輸出:
    Original List:[27, 41, 47, 89, 100, 19, 77, 77, 100, 17, 68, 15, 38, 98, 19, 45, 42, 70, 31, 75]
    Sorted List:[15, 17, 19, 19, 27, 31, 38, 41, 42, 45, 47, 68, 70, 75, 77, 77, 89, 98, 100, 100]
'''