Sorting problem: bubble sort, select sort, insert sort

What is list sorting

• Sort ： A set of “ disorder ” The recording sequence of is adjusted to “ Orderly ” The recording sequence of

• Sort the list ： Change an unordered list to a sequential list

  ​ Input ： list

  ​ Output ： Ordered list

• Ascending and descending

• Built in sort function sort()

  ​ sort Sort in the source list ,sortted Is to create a new sorted list , Source list unchanged .

Introduction to common sorting algorithms

Sorting algorithm analysis

Bubble sort (Bubble Sort)

• The number of neighbors in the list , If the front is bigger than the back , Then exchange these two numbers

• After a sequence , Then the disorder area is reduced by one number , Add a number to the ordered area

• Bubble sorting usually takes many times

• Code key ： Trip to , The range of disorder

def bubble_sort(li):
    for i in range(len(li)-1):   # The first i Trip to 
        exchange = False
        for j in range(len(li)-i-1):
            if li[j] < li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                exchange = True
        print(li)
    if not exchange:
        return

li = [9,8,7,1,2,3,4,5,6]
bubble_sort(li)
 

Selection sort (select_sort)

• The minimum number of records in a sequence , Put it in the first position
• The minimum number of disordered areas in the record list of one sort record , Put it in the second position
• Key points of the algorithm ： Ordered and disordered areas , The decimal position of the disorder area

def select_sort(li):
    for i in range(len(li)-1):    #i How many times is it 
        min_loc = i
        for j in range(i+1, len(li)):
            if li[j] < li[min_loc]:
                min_loc = j
        li[i], li[min_loc] = li[min_loc], li[i]
        print(li)

li = [3,4,2,1,5,6,8,7,9]
print(li)
select_sort(li)

Insertion sort （insert_sort）

• At the beginning ( Ordered region ) Only one card
• Every time ( From the disordered area ) Touch a card , Insert into the correct position of the existing card in your hand

def insert_sort(arry):   # Sort the previous list 
    for idx in range(1, len(arry)):
        j = idx
        while j > 0 and arry[j] < arry[j-1]:
            (arry[j-1], arry[j]) =(arry[j], arry[j-1])
            j -= 1
    return arry

arry = [1,2,5,7,6,9,8,4,3]
print(insert_sort(arry))