03插入排序

from base import gen_random_list

"""
将开始索引为start_index,结束索引为end_index的部分数组元素整体向右移动一位,注意end_index的最大取值为len(li)-2
"""
def translation_list(li,start_index,end_index):
    for i in range(end_index,start_index-1,-1):
        li[i+1]=li[i]

'''
测试平移函数
'''
def test_translation_list():
    li_01=[_ for _ in range(10)]
    translation_list(li_01,0,0)
    print(li_01)

    li_02=[_ for _ in range(10)]
    translation_list(li_02,0,1)
    print(li_02)

    li_03=[_ for _ in range(10)]
    translation_list(li_03,1,1)
    print(li_03)

    li_04=[_ for _ in range(10)]
    translation_list(li_04,1,7)
    print(li_04)

    li_05=[_ for _ in range(10)]
    translation_list(li_05,1,8)
    print(li_05)

    li_06=[_ for _ in range(10)]
    try:
        translation_list(li_06,1,9)
    except Exception as e:
        print(e)
    else:
        print(li_06)
'''
测试成功,
输出结果为:
    [0, 0, 2, 3, 4, 5, 6, 7, 8, 9]
    [0, 0, 1, 3, 4, 5, 6, 7, 8, 9]
    [0, 1, 1, 3, 4, 5, 6, 7, 8, 9]
    [0, 1, 1, 2, 3, 4, 5, 6, 7, 9]
    [0, 1, 1, 2, 3, 4, 5, 6, 7, 8]
    list assignment index out of range
'''


#选择排序
"""
核心思想:
    设无序数组的长度为N
    第一趟:从第二个元素(索引为1)开始,其中从左开始，长度为1的列表[index=0]是有序的(顺序为从小到大),我们从第一个元素的位置向右比较,直到第一个位置结束,如果第一个位置的元素大于第二个位置的元素,就将第一个位置元素右移一位，然后将位置为二的元素放到位置为一的地方
    第二趟:从第三个元素(索引为2)开始,其中从左开始，长度为2的[index=0,index=1]是有序的(顺序为从小到大),我们从第一个元素的位置向右开始比较,直到第二个位置结束，如果在比较的过程中遇到位于第i个(i在1到2之间)位置的元素大于第三个位置的元素,就将第i个位直到第二个位置的元素向右移动一位，然后将位置为三的元素放到位置为i的地方
    第三趟:从第四个元素(索引为3)开始,其中从左开始，长度为3的[index=0,index=1,index=2]是有序的(顺序为从小到大),我们从第一个元素的位置向右开始比较,直到第三个位置结束，如果在比较的过程中遇到位于第i个(i在1到3之间)位置的元素大于第四个位置的元素,就将第i个位直到第三个位置的元素向右移动一位，然后将位置为四的元素放到位置为i的地方
    第四趟:从第五个元素(索引为4)开始,其中从左开始，长度为4的[index=0,index=1,index=2,index=3]是有序的(顺序为从小到大),我们从第一个元素的位置向右开始比较,直到第四个位置结束，如果在比较的过程中遇到位于第i个(i在1到4之间)位置的元素大于第五个位置的元素,就将第i个位置到第四个位置的元素向右移动一位，然后将位置为五的元素放到位置为i的地方
    ....
    第N-2趟:从第N-1个元素(索引为N-2)开始,其中从左开始，长度为4的[index=0,index=1,index=2,index=3.....index=N-3]是有序的(顺序为从小到大),我们从第一个元素的位置向右开始比较,直到第N-2个位置结束，如果在比较的过程中遇到位于第i个(i在1到N-2之间)位置的元素大于第N-1个位置的元素,就将第i个位置到第N-2个位置的元素向右移动一位，然后将位置为N-1的元素放到位置为i的地方
    第N-1趟:从第N个元素(索引为N-2)开始,其中从左开始，长度为N-1的[index=0,index=1,index=2,index=3.....index=N-3,index=N-2]是有序的(顺序为从小到大),我们从第一个元素的位置向右开始比较,直到第N-1个位置结束，如果在比较的过程中遇到位于第i个(i在1到N-1之间)位置的元素大于第N个位置的元素,就将第i个位置到第N-1个位置的元素向右移动一位，然后将位置为N的元素放到位置为i的地方
"""
def insert_sort_list_5():
    li=gen_random_list(5)
    print('original li:{}'.format(li))

    len_li=len(li)

    cursor_index=1
    for i in range(0,cursor_index): # i in [0]
        if li[i]>li[cursor_index]:
            temp_val=li[cursor_index]
            translation_list(li,i,cursor_index-1) #start_index=i (i 在此处必为 0),end_index=cursor_index-1=0
            li[i]=temp_val #交换i与cursor_index位置的值
            break
    #完成这轮循环后，我们可以得到[index=0,index=1]的有序部分

    cursor_index=2
    for i in range(0,cursor_index): # i in [0,1]
        if li[i]>li[cursor_index]:
            temp_val=li[cursor_index]
            translation_list(li,i,cursor_index-1) #start_index=i (i 在此处可能为 0,1),end_index=cursor_index-1=1
            li[i]=temp_val #交换i与cursor_index位置的值
            break
    #完成这轮循环后，我们可以得到[index=0,index=1,index=2]的有序部分

    cursor_index=3
    for i in range(0,cursor_index): # i in [0,1,2]
        if li[i]>li[cursor_index]:
            temp_val=li[cursor_index]
            translation_list(li,i,cursor_index-1) #start_index=i (i 在此处可能为 0,1,2),end_index=cursor_index-1=2
            li[i]=temp_val #交换i与cursor_index位置的值
            break
    #完成这轮循环后，我们可以得到[index=0,index=1,index=2,index=3]的有序部分

    cursor_index=4
    for i in range(0,cursor_index): # i in [0,1,2,3]
        if li[i]>li[cursor_index]:
            temp_val=li[cursor_index]
            translation_list(li,i,cursor_index-1) #start_index=i (i 在此处可能为 0,1,2,3),end_index=cursor_index-1=3
            li[i]=temp_val #交换i与cursor_index位置的值
            break
    #完成这轮循环后，我们可以得到[index=0,index=1,index=2,index=3,index=4]的有序部分

    print('sorted li:{}'.format(li))
'''
例如:
    insert_sort_list_5()
输出:
    original li:[63, 60, 70, 62, 61]
    sorted li:[60, 61, 62, 63, 70]
'''

'''
下面我们来看下有序与无序列范围的变化
'''
def insert_sort_list_range(li):
    len_li=len(li)
    if len_li in (0,1):
        return li
    for i in range(1,len_li):
        print('在本轮循环中,只有',[_ for _ in range(i)],'是有序的，',[_ for _ in range(i,len_li)],'是无序列的,我们将',i,'位置的元素插入到有序部分',[_ for _ in range(i)],'中，最终我们得到新的有序部分:',[_ for _ in range(i+1)])
'''
例如:
    insert_sort_list_range(gen_random_list(10))
输出为:
    在本轮循环中,只有 [0] 是有序的， [1, 2, 3, 4, 5, 6, 7, 8, 9] 是无序列的,我们将 1 位置的元素插入到有序部分 [0] 中，最终我们得到新的有序部分: [0, 1]
    在本轮循环中,只有 [0, 1] 是有序的， [2, 3, 4, 5, 6, 7, 8, 9] 是无序列的,我们将 2 位置的元素插入到有序部分 [0, 1] 中，最终我们得到新的有序部分: [0, 1, 2]
    在本轮循环中,只有 [0, 1, 2] 是有序的， [3, 4, 5, 6, 7, 8, 9] 是无序列的,我们将 3 位置的元素插入到有序部分 [0, 1, 2] 中，最终我们得到新的有序部分: [0, 1, 2, 3]
    在本轮循环中,只有 [0, 1, 2, 3] 是有序的， [4, 5, 6, 7, 8, 9] 是无序列的,我们将 4 位置的元素插入到有序部分 [0, 1, 2, 3] 中，最终我们得到新的有序部分: [0, 1, 2, 3, 4]
    在本轮循环中,只有 [0, 1, 2, 3, 4] 是有序的， [5, 6, 7, 8, 9] 是无序列的,我们将 5 位置的元素插入到有序部分 [0, 1, 2, 3, 4] 中，最终我们得到新的有序部分: [0, 1, 2, 3, 4, 5]
    在本轮循环中,只有 [0, 1, 2, 3, 4, 5] 是有序的， [6, 7, 8, 9] 是无序列的,我们将 6 位置的元素插入到有序部分 [0, 1, 2, 3, 4, 5] 中，最终我们得到新的有序部分: [0, 1, 2, 3, 4, 5, 6]
    在本轮循环中,只有 [0, 1, 2, 3, 4, 5, 6] 是有序的， [7, 8, 9] 是无序列的,我们将 7 位置的元素插入到有序部分 [0, 1, 2, 3, 4, 5, 6] 中，最终我们得到新的有序部分: [0, 1, 2, 3, 4, 5, 6, 7]
    在本轮循环中,只有 [0, 1, 2, 3, 4, 5, 6, 7] 是有序的， [8, 9] 是无序列的,我们将 8 位置的元素插入到有序部分 [0, 1, 2, 3, 4, 5, 6, 7] 中，最终我们得到新的有序部分: [0, 1, 2, 3, 4, 5, 6, 7, 8]
    在本轮循环中,只有 [0, 1, 2, 3, 4, 5, 6, 7, 8] 是有序的， [9] 是无序列的,我们将 9 位置的元素插入到有序部分 [0, 1, 2, 3, 4, 5, 6, 7, 8] 中，最终我们得到新的有序部分: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
'''

'''
到这一步我们结合上面的分析，写个插入排序吧
'''
def insert_sort_list(li):
    len_li=len(li)
    if len_li in (0,1):
        return li
    for i in range(1,len_li):
        for j in range(i):
            if li[j]>li[i]:
                temp_val=li[i]
                translation_list(li,j,i-1)
                li[j]=temp_val
                break
    return li
'''
例如:
    original_list=gen_random_list(20)
    print("Original List:{}".format(original_list))
    result_list=insert_sort_list(original_list)
    print("Sorted List:{}".format(result_list))
输出为:
    Original List:[89, 64, 12, 36, 99, 32, 48, 90, 43, 63, 44, 85, 38, 66, 97, 48, 92, 91, 11, 53]
    Sorted List:[11, 12, 32, 36, 38, 43, 44, 48, 48, 53, 63, 64, 66, 85, 89, 90, 91, 92, 97, 99]
'''

'''
我们稍微改造一下，写个尾递归的版本
'''
def insert_sort_list_recursive(li,cursor_index=1):
    len_li=len(li)
    if len_li in (0,1):
        return li
    if cursor_index==len_li:
        return li
    for j in range(cursor_index):
        if li[j]>li[cursor_index]:
            temp_val=li[cursor_index]
            translation_list(li,j,cursor_index-1) #将索引为i到cursor_index-1之间元素右移一位
            li[j]=temp_val
            break
    return insert_sort_list_recursive(li,cursor_index+1)
"""
例如:
    original_list=gen_random_list(20)
    print("Original List:{}".format(original_list))
    result_list=insert_sort_list_recursive(original_list)
    print("Sorted List:{}".format(result_list))
输出为:
    Original List:[14, 85, 34, 33, 62, 68, 77, 72, 85, 89, 35, 52, 43, 73, 14, 22, 86, 70, 24, 99]
    Sorted List:[14, 14, 22, 24, 33, 34, 35, 43, 52, 62, 68, 70, 72, 73, 77, 85, 85, 86, 89, 99]
"""