文章概述

介紹各大常用經(jīng)典的排序算法和效率，以及python實現(xiàn)
常用算法（冒泡排序，選擇排序，快速排序，插入排序）

冒泡排序

介紹：冒泡排序算法思想比較簡單，對要排序的列表，從第一個元素起，依次比較相鄰兩個元素，如果順序不對，就交換，直到最小（大）元素“冒”出來。時間復(fù)雜度 O(n2)

算法描述：

1. 依次比較相鄰元素，如果第一個比第二個大，就交換位置，直到最后一個元素比較過后，最后一個元素就是最大值
2. 重復(fù)執(zhí)行步驟1，除了最后一個元素
3. 重復(fù)執(zhí)行上述步驟
   python實現(xiàn)：

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

選擇排序

介紹：從未排列表中找到最值，順序放到已排列表中。時間復(fù)雜度 O(n2)

算法描述：

1. 從未排列表中找到最大（?。┲担诺揭雅帕斜硎孜?/li>
2. 從剩余未排列表中找到最大（?。┲?，放到已排列表末尾
3. 重復(fù)步驟2，直到所有元素都排好
   python實現(xiàn)：

def selection_sort(arr):
    for i in range(len(arr) - 1):
        # 記錄最小數(shù)的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小數(shù)時，將 i 和最小數(shù)進行交換
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

快速排序

介紹：采用分而治之的思想，將要排序的數(shù)據(jù)分成兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序。
。時間復(fù)雜度 O(nlog2n)

算法描述：

1. 從列表中選擇一個基準元素，比之大的放到左邊，反之右邊。
2. 分別對左右兩部分執(zhí)行步驟1
3. 重復(fù)執(zhí)行上述步驟，直到不可再分
   python實現(xiàn)：

def quick_sort(data):    
    """快速排序"""    
    if len(data) >= 2:  # 遞歸入口及出口        
        mid = data[len(data)//2]  # 選取基準值，也可以選取第一個或最后一個元素        
        left, right = [], []  # 定義基準值左右兩側(cè)的列表        
        data.remove(mid)  # 從原始數(shù)組中移除基準值        
        for num in data:            
            if num >= mid:                
                right.append(num)            
            else:                
                left.append(num)        
        return quick_sort(left) + [mid] + quick_sort(right)    
    else:        
        return data

插入排序

介紹： 默認第一個元素為已排，剩余元素依次順序插入已排列表。時間復(fù)雜度 O(n2)

算法描述：

1. 默認第一個元素放在已排列表
2. 從剩余未排列表中找到第一個，按順序插入已排列表
3. 重復(fù)步驟2，直到所有元素都排好
   python實現(xiàn)：

def insert_sort(l):    
    """插入排序"""    
    length = len(l)
    for i in range(1,length):                   #默認第一個元素已經(jīng)在有序序列中，從后面元素開始插入    
        for j in range(i,0,-1):                 #逆向遍歷比較，交換位置實現(xiàn)插入        
            if l[j] < l[j-1]:            
                l[j],l[j-1] = l[j-1],l[j]
    return l