sort algorithm 1

Sort(i)

三种复杂度为\(O(n^2)\)的排序算法:

• 冒泡排序
• 选择排序
• 插入排序

Bubble sort

“一趟一趟来”

def bubble_sort(ls):
    for i in range(len(ls)-1):
        for j in range(len(ls)-i-1):
            if ls[j] > ls[j+1]:
                ls[j+1],ls[j]=ls[j],ls[j+1]
    return(ls)

Select sort

"一个一个排"

def select_sort(ls):
    for i in range(len(ls)-1):
        min_loc = i
        for j in range(len(ls)-1-i):
            if ls[i+j]<ls[min_loc]:
                min_loc =i+j
        ls[min_loc],ls[i] = ls[i],ls[min_loc]
    print(ls)

Insert sort

def insert_select(ls):
    for i in range(1,len(ls)):
        j = i-1
        tmp = ls[i]
        while j>=0 and ls[j]>tmp:
            ls[j+1]=ls[j]
            j-=1
        ls[j+1] = tmp
    print(ls)

Sort(ii)

三种复杂度为\(O(nlogn)\)的排序算法:

• 快速排序
• 归并排序
• 堆排序