常見算法：

一、排序引入

1.排序與搜索
排序算法（英語：Sorting algorithm）是一種能將一串數據依照特定順序進行排列的一種算法。
2.排序算法的穩定性
穩定性：穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。

1 8 3 8 5 6 7 2
(4,1) (3,1) (3,7) (5,6)
(3,7)(3,1)

            
              如果一個排序算法是穩定的，當有兩個相等鍵值的紀錄R和S，且在原本的列表中R出現在S之前，在排序過的列表中R也將會是在S之前。
不穩定排序算法可能會在相等的鍵值中改變紀錄的相對次序

            
          

二、冒泡排序

1.什么是冒泡排序
冒泡排序（Bubble Sort）是一種簡單的排序算法。
它重復地遍歷要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。
遍歷數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。
冒泡排序算法的工作原理如下：
比較相鄰的元素。如果第一個比第二個大（升序），就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。這步做完后，最后的元素會是最大的數。
除了最后一個，所有的元素重復以上的步驟。
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
2.冒泡排序的分析
交換過程：

3.冒泡排序的實現

            
              def bubble_sort(alist):
    # 外層循環控制比較幾輪
    n = len(alist)
    for j in range(n - 1):
        # 內存循環控制交換
        # -j是不再換已經排好的
        for i in range(n - 1 - j):
            # 若前一個比后一個大，則換
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]

if __name__ == '__main__':
    li = [33, 11, 26, 78, 3, 9, 40]
    print(li)
    bubble_sort(li)
    print(li)

            
          

優化有序的情況，最優時間復雜度O(n)

            
              def bubble_sort(alist):
    # 外層循環控制比較幾輪
    n = len(alist)
    for j in range(n - 1):
        # 定義計數器
        count = 0
        # 內存循環控制交換
        # -j是不再換已經排好的
        for i in range(n - 1 - j):
            # 若前一個比后一個大，則換
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
                # 計數器
                count += 1
        if count == 0:
            return

            
          

4.時間復雜度
最優時間復雜度：O(n)
最壞時間復雜度：O(n2)
穩定性：穩定
5.評價
優點：穩定，簡單
缺點：效率不很高，運行時間較長

三、選擇排序

1.什么是選擇排序
選擇排序（Selection sort）是一種簡單直觀的排序算法。
選擇排序算法的工作原理如下：
首先在序列中找到最小或最大元素，存放到排序序列的前或后。
然后，再從剩余元素中繼續尋找最小或最大元素。
然后放到已排序序列的末尾。
以此類推，直到所有元素均排序完畢。
2.選擇排序的分析
排序過程：

3.選擇排序的實現

            
              alist = [3, 11, 26, 26,7, 3, 9, 4]
 選擇排序把數據當成2部分
 alist = [3,        11, 26, 26,7, 9, 4]
 alist = [3, 4     11, 26, 26,7, 9]
 怎么找到最小值？ 索引min = 0
 最終min = 0
 min = 1開始
 min = 6
 alist[1] alist[6]

def select_sort(alist):
    n = len(alist)
    # 外層控制比較幾輪
    for j in range(n - 1):
        min_index = j
        # 內層控制元素比較和更新索引
        for i in range(j + 1, n):
            # 進行比較
            if alist[min_index] > alist[i]:
                # 更新索引
                min_index = i
        # 退出循環后，交換數據
        alist[j], alist[min_index] = alist[min_index], alist[j]
        if __name__ == '__main__':
   			 li = [3, 11, 26, 26, 7, 3, 9, 4]
    		print(li)
    		select_sort(li)
    		print(li)

            
          

4.時間復雜度
最優時間復雜度：O(n2)
最壞時間復雜度：O(n2)
穩定性：不穩定
5.評價
優點：移動次數少
缺點：比較次數多

四、插入排序

1.什么是插入排序
插入排序（Insertion Sort）是一種簡單直觀的排序算法。
插入排序算法的工作原理如下：
構建有序序列
在已排序序列中掃描未排序數據
找到相應位置并插入
2.插入排序的分析
排序過程：

3.插入排序的實現
插入排序

            
              def insert_sort(alist):
    n = len(alist)
    # 外層循環控制從右邊取多少元素
    for j in range(1, n):
        # i = [1，2，3...]
        i = j
        # 內存循環
        while i > 0:
            if alist[i] < alist[i - 1]:
                alist[i], alist[i - 1] = alist[i - 1], alist[i]
                # 控制循環結束
                i -= 1
            else:
                break


if __name__ == '__main__':
    li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(li)
    insert_sort(li)
    print(li)

            
          

4.時間復雜度
最優時間復雜度：O(n)
最壞時間復雜度：O(n2)
穩定性：穩定
5.評價
優點：穩定，比較快
缺點：比較次數不確定，數據量越大，該算法越渣

五、希爾排序

1.什么是希爾排序
希爾排序（Shell Sort）是插入排序的一種，也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。
希爾排序是非穩定排序算法，是DL．Shell于1959年提出的。
希爾排序算法的工作原理如下：
把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序。
隨著增量逐漸減少，每組包含的關鍵詞越來越多。
當增量減至1時，整個文件恰被分成一組，算法便終止。
2.希爾排序的分析
排序過程：
增量用gap代表，第一次增量3是將數據分3組

3.希爾排序的實現

            
              def shellSort(nums):
    # 設定步長
    step = len(nums)/2
    while step > 0:
        for i in range(step, len(nums)):
            # 類似插入排序, 當前值與指定步長之前的值比較, 符合條件則交換位置
            while i >= step and nums[i-step] > nums[i]:
                nums[i], nums[i-step] = nums[i-step], nums[i]
                i -= step
        step = step/2
    return nums


if __name__ == '__main__':
    nums = [9,3,5,8,2,7,1]
    print shellSort(nums)


"""
[1, 2, 3, 5, 7, 8, 9]
"""

            
          

4.時間復雜度
最優時間復雜度：根據步長序列的不同而不同，最優是1.3，根據數學運算算出的gap
最壞時間復雜度：O(n2)
穩定性：不穩定
5.評價
優點：平均時間短，數據移動少
缺點：不穩定

六、快速排序

1.什么是快速排序
快速排序（Quicksort），又稱劃分交換排序（partition-exchange sort）。
通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序。
整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
快速排序算法的工作原理如下：
從數列中挑出一個元素，稱為"基準"（pivot）。
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。
在這個分區結束之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。
遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
2.快速排序的分析
排序過程：

3.快速排序的實現
快排：first理解為第一個位置的索引，last是最后位置索引

            
              def quick_sort(alist, first, last):
    # 遞歸終止條件
    if first >= last:
        return

        # 設置第一個元素為中間值
    mid_value = alist[first]
    # low指向
    low = first
    # high
    high = last
    # 只要low小于high就一直走
    while low < high:
        # high大于中間值，則進入循環
        while low < high and alist[high] >= mid_value:
            # high往左走
            high -= 1
        # 出循環后，說明high小于中間值,low指向該值
        alist[low] = alist[high]
        # high走完了，讓low走
        # low小于中間值，則進入循環
        while low < high and alist[low] < mid_value:
            # low向右走
            low += 1
        # 出循環后，說明low大于中間值,high指向該值
        alist[high] = alist[low]
    # 退出整個循環后，low和high相等
    # 將中間值放到中間位置
    alist[low] = mid_value
    # 遞歸
    # 先對左側快排
    quick_sort(alist, first, low - 1)
    # 對右側快排
    quick_sort(alist, low + 1, last)


if __name__ == '__main__':
    li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(li)
    quick_sort(li, 0, len(li) - 1)
    print(li)

            
          

4.時間復雜度
最優時間復雜度：O(nlogn)
遍歷每個數是O(n)，訪問每個數是O(logn)，最終是O(nlogn)
可以轉換為求二叉樹深度的思想
最壞時間復雜度：O(n2)
穩定性：不穩定
5.評價
優點：效率高，數據移動比較少，數據量越大，優勢越明顯
缺點：不穩定

七、歸并排序

1.什么是歸并排序
歸并排序（MergeSort）是采用分治法的一個非常典型的應用。
歸并排序的思想就是先遞歸分解數組，再合并數組。
歸并排序算法的工作原理如下：
將數組分解最小之后，然后合并兩個有序數組。
比較兩個數組的最前面的數，誰小就先取誰，取了后相應的指針就往后移一位。
然后再比較，直至一個數組為空，最后把另一個數組的剩余部分復制過來即可。
2.歸并排序的分析
排序過程：

3.歸并排序的實現
歸并排序

            
              def merge_sort(alist):
    n = len(alist)

    # 遞歸結束條件
    if n <= 1:
        return alist

    # 中間位置
    mid = n // 2
    # 遞歸拆分左側
    left_li = merge_sort(alist[:mid])
    # 遞歸拆分右側
    right_li = merge_sort(alist[mid:])
    # 需要2個游標，分別指向左列表和右列表第一個元素
    left_point, right_point = 0, 0
    # 定義最終返回的結果集
    result = []
    # 循環合并數據
    while left_point < len(left_li) and right_point < len(right_li):
        # 誰小誰放前面
        if left_li[left_point] <= right_li[right_point]:
            # 放進結果集
            result.append(left_li[left_point])
            # 游標移動
            left_point += 1
        else:
            result.append(right_li[right_point])
            right_point += 1
    # 退出循環時，形成左右兩個序列
    result += left_li[left_point:]
    result += right_li[right_point:]
    return result


if __name__ == '__main__':
    li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(li)
    sort_li = merge_sort(li)
    print(li)
    print(sort_li)

            
          

4.時間復雜度
最優時間復雜度：O(nlogn)
最壞時間復雜度：O(nlogn)
穩定性：穩定
5.評價
優點：穩定，數據量越大越優秀
缺點：需要額外空間
6.常見算法的效率比較

            
              快速排序消耗空間因為每次遞歸時，要保持一些數據
最優情況：每一次平均分組的情況 O(logn)
最壞情況：退化為冒泡排序的情況 O(n)
堆排序是結合二叉樹去做的

            
          

八、搜索

1.搜索引入
搜索是在一個數據集合中找到一個特定數據的算法
搜索通常的答案是真的或假的
搜索的常見方法有二分查找、哈希查找等
2.二分法查找
二分查找又稱折半查找，優點是比較次數少，查找速度快，平均性能好。
缺點是要求待查表為有序表
因此，折半查找方法適用于不經常變動而查找頻繁的有序列表。
二分查找的工作原理如下：
首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功。
否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。
重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

3.二分查找的實現
遞歸實現
非遞歸實現
遞歸的實現

            
              def my_search(alist, item):
    n = len(alist)
    # 遞歸結束條件
    if n > 0:
        # 折半
        mid = n // 2
        # 判斷中間元素是否為要查的元素
        if alist[mid] == item:
            return True
        # 判斷中間元素與item的大小
        elif item < alist[mid]:
            # 繼續遞歸查找
            return my_search(alist[:mid], item)
        else:
            return my_search(alist[mid + 1:], item)
    return False

            
          

非遞歸實現

            
              def my_search2(alist, item):
    n = len(alist)
    # 起始，0
    first = 0
    # 結束位置
    last = n - 1
    while first <= last:
        # 折半
        mid = (first + last) // 2
        # 判斷中間元素
        if alist[mid] == item:
            return True
        elif item < alist[mid]:
            last = mid - 1
        else:
            first = mid + 1
    return False


if __name__ == '__main__':
    # 2個注意點：必須用有序的順序表
    li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
    print(my_search(li, 17))
    print(my_search2(li, 111))

            
          

4.時間復雜度
最優時間復雜度：O(1)
最壞時間復雜度：O(logn)

總結