排序算法之low B三人組

排序low B三人組

清單排序:将無序清單變成有充清單

應用場景:各種榜單,各種表格,給二分法排序使用,給其他算法使用

輸入無序清單,輸出有序清單(升序或降序)           

1. 冒泡排序

首先,清單每兩個相鄰的數做比較,如果前邊的數比後邊的數大,那麼交換這兩個數

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

冒泡排序的優化

如果冒泡排序中執行一趟而沒有交換,則清單已經是有序狀态,可以直接結束排序

def bubble_sort_1(l1):
    for i in range(len(l1)-1):
        flag=False
        
        for j in range(len(l1)-i-1):
            if l1[j] > l1[j+1]:
                l1[j],l1[j+1]=l1[j+1],l1[j]
                flag=True
        
        if not flag:
            return l1           

2. 選擇排序

一趟周遊記錄中最小的數,放到第一個位置

再一趟周遊記錄剩餘清單中最小的數,繼續放置

def select_sort(l1):
        for i in range(len(l1)-1):
            mid=i
    
            for j in range(i+1,len(l1)):
                if l1[j] <l1[mid]:
                    mid=j
    
            l1[mid],l1[i]=l1[i],l1[mid]
    
        return l1           

3. 插入排序

清單被分有有序區和無序區兩個部分.最初有序區隻有一個元素

每次從無序區選擇一個元素,插入到有序區的位置,直到無序區變空

例如，最初時有一個無序清單l1=[5,7,4,6,3,1,2,9,8],其使用插入排序時的步驟為:

1.取無序清單l1中的第一個元素5,放入另一個有序清單tmp中
2.取無序清單l1中的第二個元素7,因為7比5大,把7放入有序清單tmp的第二個位置
3.取無序清單l1中的第三個元素4,因為4比5小,是以把4放入到有序清單tmp的元素5的左邊中,此時有序清單tmp為[4,5,7]
4.取l1中第四個元素6,因為6比5大,又比7小,把6放入到元素5和7之間,此時tmp變成了[4,5,6,7]
...
每次從無序區中選擇一個元素,插入到有序區的某個位置,直到無序區變空           

def insert_sort(li):
    for i in range(1, len(li)):
        tmp = li[i]
        j = i - 1       #手裡最後一張
        while j>=0 and li[j]>tmp:
            li[j+1]=li[j]
            j = j-1
        li[j+1] = tmp
        
    return li