1、冒泡排序

• 冒泡排序只會操作相鄰的兩個數據。
• 每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關系要求。如果不滿足就讓它倆互換。
• 一次冒泡會讓至少一個元素移動到它應該在的位置，重復 n 次，就完成了 n 個數據的排序工作。

第一次冒泡操作的詳細過程

經過一次冒泡操作之后，6 這個元素已經存儲在正確的位置上。要想完成所有數據的排序，我們只要進行 6 次這樣的冒泡操作就行了。

實際上，冒泡過程還可以優化。當某次冒泡操作已經沒有數據交換時，說明已經達到完全有序，不用再繼續執行后續的冒泡操作。下圖中的另外一個例子，這里面給 6 個元素排序，只需要 4 次冒泡操作就可以了。

優化后的冒泡排序代碼如下：

            
              """
    優化的冒泡排序：
    當某次冒泡操作已經沒有數據交換時，說明已經達到完全有序，不用再繼續執行后續的冒泡操作
"""
def bubble_sort(a):
    '''   
    :param a: List[int]
    '''
    length = len(a)
    if length <= 1:
        return 

    for i in range(length):
        made_swap = False
        # 下標j + 1 最大為 length - 1
        for j in range(length-1-i):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                made_swap = True
        # 優化：無數據交換，結束排序操作
        if not made_swap:
                break
    return a

if __name__ == '__main__':
    a = [7,1,4,3,6,5]
    print(bubble_sort(a))
            
          

?

2、插入排序

首先，我們將數組中的數據分為兩個區間， 已排序區間 和 未排序區間 。初始已排序區間只有一個元素，就是數組的第一個元素。插入算法的核心思想是取未排序區間中的元素，在已排序區間中找到合適的插入位置將其插入，并保證已排序區間數據一直有序。重復這個過程，直到未排序區間中元素為空，算法結束。

如圖所示，要排序的數據是 4，5，6，1，3，2，其中左側為已排序區間，右側是未排序區間。

插入排序也包含兩種操作，一種是元素的 比較 ，一種是元素的 移動 。當我們需要將一個數據 a 插入到已排序區間時，需要拿 a 與已排序區間的元素依次比較大小 ，找到合適的插入位置。找到插入點之后，我們還需要 將插入點之后的元素順序往后移動一位 ，這樣才能騰出位置給元素 a 插入。

代碼如下：

            
              """
    插入排序包含兩種操作，一種是元素的比較，一種是元素的移動。
    當我們需要將一個數據 a 插入到已排序區間時，需要拿 a 與已排序區間的元素依次比較大小，找到合適的插入位置。
    找到插入點之后，我們還需要將插入點之后的元素順序往后移動一位，這樣才能騰出位置給元素 a 插入。
"""
def insertion_sort(a):
    '''
    :param a: List[int]
    '''
    length = len(a)
    if length <= 1:
        return

    for i in range(1, length):
        value = a[i]
        j = i - 1
        # 查找插入位置，在前面的已排序區間，拿value與已排序區間的元素依次比較大小
        while j >= 0 and a[j] > value:
            # 數據向后移動
            a[j+1] = a[j]
            j -= 1
        # 插入數據
        a[j+1] = value

    return a

if __name__ == '__main__':
    a = [7,1,4,3,6,5]
    print(insertion_sort(a))
            
          

?

3、選擇排序

選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。但是選擇排序每次會 從未排序區間中找到最小的元素，將其放到已排序區間的末尾 。

選擇排序是一種不穩定的排序算法。從圖中可以看出，選擇排序每次都要找剩余未排序元素中的最小值，并和前面的元素交換位置，這樣破壞了穩定性。 ?

比如 5，8，5，2，9 這樣一組數據，使用選擇排序算法來排序的話，第一次找到最小元素 2，與第一個 5 交換位置，那第一個 5 和中間的 5 順序就變了，所以就不穩定了。

正是因此，相對于冒泡排序和插入排序，選擇排序就稍微遜色了。

代碼如下：

            
              def selection_sort(a):
    length = len(a)
    if length <= 1:
        return

    for i in range(length):
        # i是每次已排序區間的末尾
        min_index = i
        min_val = a[i]
        # 查找未排序區間中最小的元素
        for j in range(i, length):
            if a[j] < min_val:
                # 未排序區間最小的元素
                min_val = a[j]
                min_index = j
        a[i], a[min_index] = a[min_index], a[i]

    return a

if __name__ == '__main__':
    a = [7,1,4,3,6,5]
    print(selection_sort(a))
            
          

?