（一）排序算法

排序算法性能比較

1.插入排序算法

把n個待排序的元素看成為一個有序表和一個無序表。開始時有序表中只包含1個元素滥朱，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素力试，將它插入到有序表中的適當位置徙邻，使之成為新的有序表，重復n-1次可完成排序過程懂版。

原理：

• 從第二個元素開始和前面的元素進行比較鹃栽，如果前面的元素比當前元素大，則將前面元素 后移，當前元素依次往前民鼓，直到找到比它小或等于它的元素插入在其后面
• 然后選擇第三個元素薇芝，重復上述操作，進行插入
• 依次選擇到最后一個元素丰嘉，插入后即完成所有排序

舉例

數(shù)列[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]需要使用插入排序夯到，我們來看看使用插入排序的詳細步驟：

• 首先第二個元素99和前面的元素11比較，99>11饮亏，第一輪完了耍贾，列表是 1 [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
• 然后，33作為比較元素路幸，和前面的元素99比較荐开，11<33<99交換位置，33插入到11和99之間简肴，列表為 1 [11, 33, 99, 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
• 接著晃听，33<69<99交換位置，列表變?yōu)? 1 [11, 33, 69, 99, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
• 以此類推砰识，69<77<99,77插入到69和99之間能扒，列表變?yōu)? 1 [11, 33, 69, 77, 99, 88, 55, 11, 33, 36,39, 66, 44, 22]
• 77<88<99, 88插入到77和99之間，列表變?yōu)? 1 [11, 33, 69, 77, 88, 99, 55, 11, 33, 36,39, 66, 44, 22]
• 33<55<69<77<88<99,55插入到33和69之間辫狼，列表變?yōu)? 1 [11, 33, 69, 77, 88, 99, 55, 11, 33, 36,39, 66, 44, 22]
• .......
• 最終得到列表 1 [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

python實現(xiàn)

def insert_sort(arr):
    # 第一層for表示循環(huán)插入的遍數(shù)
    for i in range(1,len(arr)):
        # 設置當前需要插入的元素
        current = arr[i]
        # 與當前元素比較的比較元素
        pre_index = i - 1
        while pre_index >= 0 and arr[pre_index] > current:
            # 當比較元素大于當前元素則把比較元素后移
            arr[pre_index+1] = arr[pre_index]
            # 往前選擇下一個比較元素
            pre_index -= 1
        # 當比較元素小于當前元素初斑，則將當前元素插入在 其后面
        arr[pre_index+1] = current
    return arr

2.選擇排序

每一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個元素膨处，存放在序列的起始位置见秤，所以稱為：選擇排序。

原理

• 設第一個元素為比較元素灵迫，依次和后面的元素比較秦叛，比較完所有元素找到最小的元素晦溪，將它和第一個元素互換
• 重復上述操作瀑粥，我們找出第二小的元素和第二個位置的元素互換，以此類推找出剩余最小元素將它換到前面三圆，即完成排序

舉例

數(shù)列[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]需要使用插入排序狞换，我們來看看使用選擇排序的詳細步驟：

1、首先11作為比較元素和列表后面的所有元素比較舟肉，找到最小的11修噪，并放在第一位，第一輪完了路媚，列表是 [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
2黄琼、然后，99作為比較元素整慎，和后面的元素[33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]作比較脏款，找到最小的11围苫，和第二位元素99交換位置，即第二輪比較完后撤师，列表為 [11, 11, 33 , 69, 77, 88, 55, 99, 33, 36,39, 66, 44, 22]
3剂府、第三輪比較完，22最小剃盾，和第三個元素33交換位置腺占，列表變?yōu)? [11, 11, 22, 69, 77, 88, 55, 99, 33, 36,39, 66, 44, 33]
4、最終得到列表 [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

python實現(xiàn)

def selection_sort(arr):
    # 第一層for表示循環(huán)選擇的遍數(shù)
    for i in range(len(arr)-1):
        # 將起始元素設為最小元素
        min_index = i
        # 第二層for表示最小元素和后面的元素逐個比較
        for j in range(i+1,len(arr)):
            if arr[j] < arr[min_index]:
                # 如果當前元素比最小元素小痒谴，則把當前元素角標記為最小元素角標
                min_index = j
        # 查找一遍后將最小元素與起始元素互換
        temp = arr[min_index]
        arr[min_index]=arr[i]
        arr[i] = temp
    return arr

3.冒泡排序

重復地走訪過要排序的元素列衰伯，依次比較兩個相鄰的元素，一層一層的將較大的元素往后移動积蔚，其現(xiàn)象和氣泡在上升過程中慢慢變大類似嚎研，故成為冒泡排序。

原理

• 從第一個和第二個開始比較库倘，如果第一個比第二個大临扮，則交換位置，然后比較第二個和第三個教翩，逐漸往后
• 經(jīng)過第一輪后最大的元素已經(jīng)排在最后杆勇，所以重復上述操作的話第二大的則會排在倒數(shù)第二的位置。
• 那重復上述操作n-1次即可完成排序饱亿，因為最后一次只有一個元素所以不需要比較

舉例

舉個例子蚜退，假設我現(xiàn)在有一個數(shù)列需要使用冒泡來排序 [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]，我們來看看使用冒泡的詳細步驟：

• 首先11和99比較大小彪笼，99大钻注，99繼續(xù)和后面的作比較，直到最后一個元素配猫，第一輪完了幅恋，列表是 [11, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22, 99]
• 然后，重復第一輪操作泵肄，即第二輪比較列表是 [11, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22, 99]捆交，
• 比較完后，列表為 [11, 33 , 69, 77, 55, 11, 33, 36,39, 66, 44, 22, , 88腐巢，99]
• 以此類推品追，最終得到列表 [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

python實現(xiàn)

def bubble_sort(arr):
    # 第一層for表示循環(huán)的遍數(shù)
    for i in range(len(arr)-1):
        # 第二層for表示具體比較哪兩個元素
        for j in range(len(arr)-1-i):
            if a[j] > a[j+1]:
                # 如果前面的大于后面的，則交換這兩個元素的位置
                temp = a[j]
                a[j] = a[j+1]
                a[j+1] = temp
    return arr

4.快速排序（重點）

通過一趟排序將要排序的數(shù)據(jù)分割成獨立的兩部分冯丙，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小肉瓦，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列泞莉。

原理

• 在數(shù)列之中洁墙，選擇一個元素作為”基準”（pivot），或者叫比較值戒财。
• 數(shù)列中所有元素都和這個基準值進行比較热监，如果比基準值小就移到基準值的左邊，如果比基準值大就移到基準值的右邊
• 以基準值左右兩邊的子列作為新數(shù)列饮寞，不斷重復第一步和第二步孝扛，直到所有子集只剩下一個元素為止。

舉例

舉個例子幽崩，假設我現(xiàn)在有一個數(shù)列需要使用快排來排序：[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]苦始，我們來看看使用快排的詳細步驟：

• 選取中間的66作為基準值（基準值可以隨便選）
• 數(shù)列從第一個元素11開始和基準值66進行比較，小于基準值慌申，那么將它放入左邊的分區(qū)中陌选，第二個元素99比基準值66大，把它放入右邊的分區(qū)中蹄溉。
• 然后依次對左右兩個分區(qū)進行再分區(qū)咨油，直到最后只有一個元素
• 分解完成再一層一層返回，返回規(guī)則是：左邊分區(qū)+基準值+右邊分區(qū)

python實現(xiàn)

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    mid = arr[len(arr)//2]
    left = []
    right = []
    arr.remove(mid)
    for item in arr:
        if item >= mid:
            right.append(item)
        else:
            left.append(item)
    return quick_sort(left) + [mid] + quick_sort(right)

5.希爾排序

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序柒爵，待整個序列中的記錄“基本有序”時役电，再對全體記錄進行依次直接插入排序。

原理

希爾排序

• 計算一個增量（間隔）值
• 對元素進行增量元素進行比較棉胀，比如增量值為7法瑟，那么就對0,7,14,21…個元素進行插入排序
• 然后對1,8,15…進行排序，依次遞增進行排序
• 所有元素排序完后唁奢，縮小增量比如為3霎挟，然后又重復上述第2，3步
• 最后縮小增量至1時麻掸，數(shù)列已經(jīng)基本有序酥夭，最后一遍普通插入即可

舉例

舉個例子，假設我現(xiàn)在有一個數(shù)列需要使用快排來排序：[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]论笔，我們來看看使用希爾排序的詳細步驟：

• 首先采郎，gap = length / 2=7，數(shù)組分為7組
  [11, 11],[ 99 , 33], [33, 36], [69, 39],[ 77, 66],[88, 44], [55, 22]
• 然后狂魔，對7組分別插入排序，像33,39,66,44,22這些元素被調(diào)到前面淫痰，
  [11, 11],[ 33 , 99], [33, 36], [39, 69],[ 66, 77],[44, 88], [22, 55]
• 接著最楷，數(shù)組變?yōu)?br> [11, 11,33 , 99, 33, 36, 39, 69, 66, 77,44, 88, 22, 55]
  gap = length / 2=3，數(shù)組分為3組，
  [11,99,39,77,22],[11,33,69,44,55],[33,36,66,88]
• 以此類推籽孙，gap = length / 2=1列表變?yōu)?br> [11,22,39,77,99,11,33,44,55,69,33,36,66,88]
• 最終對數(shù)組微調(diào)烈评，得到列表
  [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

python實現(xiàn)

def sheel_sort(arr):
    gap = len(arr) // 2
    while gap > 0:
        for i in range(gap,len(arr)):
            j = i
            current = a[i]
            while j - gap >=0 and current < arr[j - gap]:
                arr[j] = arr[j - gap]
                j -= gap
            a[j] = current
        gap = gap //2
    return arr

6.歸并排序

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。歸并排序適用于子序列有序的數(shù)據(jù)排序犯建。

原理

• 將一個序列從中間位置分成兩個序列糠爬；
• 在將這兩個子序列按照第一步繼續(xù)二分下去最疆；

• 直到所有子序列的長度都為1，也就是不可以再二分截止。這時候再兩兩合并成一個有序序列即可烁设。

  
  
  歸并排序

舉例

舉個例子，假設我現(xiàn)在有一個數(shù)列需要使用快排來排序：[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]叉庐，我們來看看使用歸并排序的詳細步驟：

1.對以下數(shù)組進行歸并排序：　
[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]

2. 首先宏多，進行數(shù)組分組，即
   [11, 99, 33 , 69, 77, 88, 55], [ 11, 33, 36,39, 66, 44, 22]
   [11, 99, 33] , [69, 77, 88, 55], [ 11, 33, 36], [39, 66, 44, 22]
   [11], [99, 33] , [69, 77], [88, 55],[ 11], [33, 36],[39, 66], [44, 22]
   直到所有子序列的長度都為1嗦随，也就是不可以再二分截止列荔。
   [11], [99], [33] , [69], [77], [88], [55],[ 11], [33], [36],[39], [66], [44], [22]
3. 這時候再兩兩合并成一個有序序列即可。
   [11],[33,99],[69,77],[55,88],[11],[33,36],[39,66],[22,44]
   [11,33,99],[55,69,77,88],[11,33,36],[22,39,44,66]
   [11,33,55,69,77,88,99],[11,22,33,36,39,44,66]
   4枚尼、最終排序
   [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

python實現(xiàn)

def merge_sor(arr):
    if len(arr) == 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    return merge(merge_sort(left),merge_sort(right))

def merge(left,right):
    result = []
    while len(left)>0 and len(right) > 0:
        if left[0] >= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result += left
    result += right
    return result