Use python to implement 8 sorting algorithms-insertion sort

The basic idea of ​​insertion sort:

At each step, a record to be sorted is inserted into the appropriate position of the previously sorted file according to the size of its key value, until all are inserted.

Example:

arr = [49,38,04,97,76,13,27,49,55,65], starting from the second number as the key value, comparing forward, if the previous number is larger, proceed Exchange,

arr = [38,49,04,97,76,13,27,49,55,65], and then use the third number as the key value, compare it forward, if the previous one is larger, exchange it,

arr = [38,04,49,97,76,13,27,49,55,65], continue, arr = [04,38,49,97,76,13,27,49,55,65]

Note: When comparing forward in sequence, because the previous array is ordered, when the previous number is less than or equal to the key value, you can jump out of this forward comparison loop, and the speed of the algorithm is significantly improved.

Code:

Python code

def insert_sort(lists):  
    #插入排序  
    count = len(lists)  
    for i in range(1,count):#从第2个数起遍历  
        key = lists[i]  
        j = i - 1  
        while j >= 0:  
            if lists[j] > key:  
                lists[j+1], lists[j] = lists[j], key  
            else: break  #当前一个数小于或等于key时，跳出循环  
            j -= 1  
    return lists