目錄

基本排序算法按時間復雜度分類

冒泡排序

插入排序

選擇排序

?

?

基本排序算法按時間復雜度分類

?

O（n^2）

冒泡排序

插入排序

選擇排序

?

Q(n log n)

分而治之

快速排序

歸并排序

?

?

冒泡排序

相鄰的兩個元素對比，大的數后推，遍歷整個列表一次后，將最大項以冒泡的方式排列到列表末尾。

簡易版冒泡排序示例如下

            
              def bubble(sl):
    """
    冒泡排序，O(n^2)
    相鄰的兩個元素對比，大的后推，遍歷整個列表一次后，將最大項(i)以冒泡的方式排列到列表末尾
    :param sl: list
    :return:
    """
    items_len = len(sl)
    for i in range(1, items_len):
        for j in range(1, items_len):
            if sl[j-1] > sl[j]:
                sl[j-1], sl[j] = sl[j], sl[j-1]
    return sl
            
          

?

優化版冒泡排序示例如下

            
              def bubble_sort(items):
    """
    冒泡排序, 還是將while循環換為for循環比較習慣
    最好 O(n)
    最壞 O(n^2)
    """
    items_len = len(items)
    for i in range(1, items_len):
        has_swap = False
        for j in range(1, items_len):
            if items[j - 1] > items[j]:
                has_swap = True
                items[j - 1], items[j] = items[j], items[j - 1]
        if not has_swap:
            break
    return items
            
          

?

?

插入排序

從第二個數開始找前面對應順序的位置，像插入一張撲克牌順序一樣將其排好順序。

            
              def insert_sort_for(items):
    """
    插入排序，for循環, 中間還是使用while循環容易理解：
    比插入的值 大的數挪后，直到不需要挪動為止即為插入的位置。
    :param items:
    :return:
    """
    for i in range(1, len(items)):
        item_insert = items[i]
        j = i - 1
        while j >= 0:
            if item_insert < items[j]:
                items[j + 1] = items[j]     # 比插入值大的元素，向后移動一位
                j -= 1
            else:                           # 不需要挪動時，跳出循環
                break
        items[j + 1] = item_insert          # 找到了插入的位置

    return items
            
          

?

?

選擇排序

搜索整個列表，找到最小項位置，列表每一項都會判斷其位置是否為最小項。

            
              def select_sort(items):
    """
    選擇排序, 搜索整個列表，找到最小項位置
    """
    for i in range(len(items)-1):
        min_index = i
        for j in range(i+1, len(items)):
            if items[j] < items[min_index]:
                min_index = j

        if min_index != i:
            items[min_index], items[i] = items[i], items[min_index]

    return items
            
          

?