Python算法

一、二分查找
- 1.1 普通的二分查找
- 1.2 帶旋轉數組的二分查找
- 1.3 搜尋旋轉排序數組
二、順序查找
三、排序算法
- 3.1 冒泡排序
- 3.1 選擇排序
- 3.3 插入排序
- 3.4 快速排序
- 3.5 歸并排序
- 3.6 希爾排序
參考連結

一、二分查找

時間複雜度 O（logN)

Python算法一、二分查找二、順序查找三、排序算法參考連結

1.1 普通的二分查找

python算法圖解中的解釋

Python算法一、二分查找二、順序查找三、排序算法參考連結
通過不斷疊代mid的值，來查找參數

def binary_search(nums,target):
        # 确定lp和rp的索引值，從兩邊周遊查找
        lp,rp = 0,len(nums)-1
        while lp <= rp:
            # 疊代求中間的索引值
            mid = lp + (rp - lp) // 2
            # 如果target等于中間值，傳回中間值的索引
            if nums[mid] == target:
                return mid
            # 如果target大于中間值，說明target在中間值的右邊
            elif target > nums[mid]:
                lp = mid + 1
            # else最後一種情況，target小于中間值，在其左邊，更新rp的值
            else:
                rp = mid - 1
        return None
    
    nums = [1,3,4,56,67,78,980]
    print(binary_search(nums,980))

Python算法一、二分查找二、順序查找三、排序算法參考連結

1.2 帶旋轉數組的二分查找

例題連結：

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

首先判斷旋轉點在中間值的左邊還是右邊
然後進行二分查找

def xuanzhuan_search(nums,target):
    lp,rp = 0,len(nums)-1
    while lp <= rp:
        mid = lp + (rp-lp)//2
        if nums[mid] == target:
            return mid
        # 中間值大于lp的值，說明旋轉點在中間值的右邊
        elif nums[mid] >= nums[lp]:
            if nums[lp] <= target < nums[mid]:
                rp = mid - 1
            else:
                lp = mid + 1
        # 旋轉點在中間值的左邊
        else:
            if nums[mid] < target <= nums[rp]:
                lp = mid + 1
            else:
                rp = mid - 1
    return False

nums = [56,67,78,980,1,3,4]
print(xuanzhuan_search(nums,100))

Python算法一、二分查找二、順序查找三、排序算法參考連結

1.3 搜尋旋轉排序數組

https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/

由于傳回True or False

在重複值上可進行去重操作

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        nums = list(set(nums))
        lp,rp = 0,len(nums)-1
        while lp <= rp:
            mid = lp + (rp-lp)//2
            if nums[mid] == target:
                return True
            # 中間值大于lp的值，說明旋轉點在中間值的右邊
            elif nums[mid] >= nums[lp]:
                if nums[lp] <= target < nums[mid]:
                    rp = mid - 1
                else:
                    lp = mid + 1
            # 旋轉點在中間值的左邊
            else:
                if nums[mid] < target <= nums[rp]:
                    lp = mid + 1
                else:
                    rp = mid - 1
        return False

Python算法一、二分查找二、順序查找三、排序算法參考連結

本題難點就是有重複值，如果 nums[mid]==nums[lp]==nums[rp] 該怎麼處理

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        lp,rp = 0,len(nums)-1
        while lp <= rp:
            mid = lp + (rp-lp)//2
            if nums[mid] == target:
                return True
            # 中間值大于lp的值，說明旋轉點在中間值的右邊
            elif nums[mid] == nums[lp] == nums[rp]:
                lp += 1
                rp -= 1
            elif nums[mid] >= nums[lp]:
                if nums[lp] <= target < nums[mid]:
                    rp = mid - 1
                else:
                    lp = mid + 1
            # 旋轉點在中間值的左邊
            else:
                if nums[mid] < target <= nums[rp]:
                    lp = mid + 1
                else:
                    rp = mid - 1
        return False

在我們繼續分析之前，我們應該注意到，這個算法是分而治之政策的一個很好的例子。分和治意味着我們将問題分成更小的部分，以某種方式解決更小的部分，然後重新組合整個問題以獲得結果。當我們執行清單的二分查找時，我們首先檢查中間項。如果我們正在搜尋的項小于中間項，我們可以簡單地對原始清單的左半部分執行二分查找。同樣，如果項大，我們可以執行右半部分的二分查找。無論哪種方式，都是遞歸調用二分查找函數。
不過這種遞歸調用的方法隻能查找target值是否存在于數組中，而不能傳回其索引或者下标值

def binarySearch(alist, item):
        if len(alist) == 0:
            return False
        else:
            midpoint = len(alist)//2
            if alist[midpoint]==item:
              return True
            else:
              if item<alist[midpoint]:
                return binarySearch(alist[:midpoint],item)
              else:
                return binarySearch(alist[midpoint+1:],item)

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))

二、順序查找

其實在講二分查找之前應該講順序查找的，但是順序查找太簡單了

def sequentialSearch(alist, item):
    pos = 0
    found = False

    while pos < len(alist) and not found:
        if alist[pos] == item:
            found = True
        else:
            pos = pos + 1

    return found

def sequentialsearch(nums,target):
    for num in nums:
        if num == target:
            return True
    return False
nums = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialsearch(nums,8))
print(sequentialsearch(nums,100))

testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))

時間複雜度O（n)

三、排序算法

3.1 冒泡排序

Python算法一、二分查找二、順序查找三、排序算法參考連結

def bubble_sort(nums):
    for i in range(len(nums)):
        for j in range(len(nums)-i-1):
            if nums[j] > nums[j+1]:
                nums[j],nums[j+1] = nums[j+1],nums[j]
    return nums
nums = [123,34,231,456,678,343,1,3,56,768]
print(bubble_sort(nums))

Python算法一、二分查找二、順序查找三、排序算法參考連結

确定邊界，num從最後一個開始到1

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

nums = [123,34,231,456,678,343,1,3,56,768]
print(bubble_sort(nums))

3.1 選擇排序

選擇排序改進了冒泡排序，每次周遊清單隻做一次交換。為了做到這一點，一個選擇排序在他周遊時尋找最大的值，并在完成周遊後，将其放置在正确的位置。與冒泡排序一樣，在第一次周遊後，最大的項在正确的地方。第二遍後，下一個最大的就位。周遊 n-1 次排序 n 個項，因為最終項必須在第（n-1）次周遊之後。

Python算法一、二分查找二、順序查找三、排序算法參考連結

def select_sort(nums):
    """
    選擇排序：每次選擇最小值
    :param nums: list
    :return: list
    """
    for i in range(len(nums)-1):
        # 确定目前要排序的位置下标
        index = i
        # 選擇剩下數組裡最小的數值，和目前下标值進行交換
        for j in range(i+1,len(nums)):
            if nums[j] < nums[index]:
                index = j
        nums[index],nums[i] = nums[i],nums[index]
    return nums
nums = [123,34,231,456,678,343,1,3,56,768]
print(select_sort(nums))

Python算法一、二分查找二、順序查找三、排序算法參考連結

你可能會看到選擇排序與冒泡排序有相同數量的比較，是以也是 O(n^2）。然而，由于交換數量的減少，選擇排序通常在基準研究中執行得更快。事實上，對于我們的清單，冒泡排序有 20 次交換，而選擇排序隻有 8 次。

3.3 插入排序

插入排序，盡管仍然是 O(n^2)，工作方式略有不同。它始終在清單的較低位置維護一個排序的子清單。然後将每個新項 “插入” 回先前的子清單，使得排序的子清單稱為較大的一個項。展示了插入排序過程。陰影項表示算法進行每次周遊時的有序子清單。
每次插入剩下數組的最小值，并在前面數組找位置

Python算法一、二分查找二、順序查找三、排序算法參考連結

def insert_sort(nums):
    """
    将每次插入的值排序
    :param nums:
    :return:
    """
    for i in range(1,len(nums)):
        value = nums[i]
        pre_index = i-1
        while pre_index >= 0 and nums[pre_index] > value:
            nums[pre_index+1] = nums[pre_index]
            pre_index -= 1
        nums[pre_index+1] = value
    return nums
nums = [3,6,19,15,4,100,368,34,56,78,89]
print(insert_sort(nums))

Python算法一、二分查找二、順序查找三、排序算法參考連結

3.4 快速排序

def quick_sort(nums):
    return qsort(nums,0,len(nums)-1)

def qsort(nums,left,right):
    if left > right:
        return nums
    lp,rp = left,right
    key = nums[left]
    while lp < rp:
        while lp < rp and nums[rp] >= key:
            rp -= 1
        nums[lp] = nums[rp]
        while lp < rp and nums[lp] <= key:
            lp += 1
        nums[rp] = nums[lp]
    nums[lp] = key

    qsort(nums,left,lp-1)
    qsort(nums,lp+1,right)
    return nums

nums = [123,34,231,456,678,343,1,3,56,768]
print(quick_sort(nums))

Python算法一、二分查找二、順序查找三、排序算法參考連結

要分析 quickSort 函數，請注意，對于長度為 n 的清單，如果分區總是出現在清單中間，則會再次出現 log⁡n 分區。為了找到分割點，需要針對樞軸值檢查 n 個項中的每一個。結果是 nlog⁡n。此外，在歸并排序過程中不需要額外的存儲器。
不幸的是，在最壞的情況下，分裂點可能不在中間，并且可能非常偏向左邊或右邊，留下非常不均勻的分割。在這種情況下，對 n 個項的清單進行排序劃分為對0 個項的清單和 n-1 個項目的清單進行排序。然後将 n-1 個劃分的清單排序為大小為0的清單和大小為 n-2 的清單，以此類推。結果是具有遞歸所需的所有開銷的 O(n^2)

) 排序。
之前提到過，有不同的方法來選擇樞紐值。特别地，我們可以嘗試通過使用稱為中值三的技術來減輕一些不均勻分割的可能性。要選擇樞軸值，我們将考慮清單中的第一個，中間和最後一個元素。在我們的示例中，這些是54,77和20.現在選擇中值，在我們的示例中為54，并将其用于樞軸值（當然，這是我們最初使用的樞軸值）。想法是，在清單中的第一項不屬于清單的中間的情況下，中值三将選擇更好的“中間”值。當原始清單部分有序時，這将特别有用。我們将此樞軸值選擇的實作作為練習。

3.5 歸并排序

Python算法一、二分查找二、順序查找三、排序算法參考連結

def merge_sort(nums):
    if len(nums) == 1:
        return nums
    mid = len(nums) // 2
    return merge(merge_sort(nums[:mid]),merge_sort(nums[mid:]))

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

nums = [3,6,19,15,4,100,368,34,56,78,89]
print(merge_sort(nums))

Python算法一、二分查找二、順序查找三、排序算法參考連結

3.6 希爾排序

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

nums = [3,6,19,15,4,100,368,34,56,78,89]
print(xiersort(nums))

參考連結

1、Python算法圖解

2、https://facert.gitbooks.io/python-data-structure-cn/5.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%90%9C%E7%B4%A2/5.4.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/

Python算法一、二分查找二、順序查找三、排序算法參考連結

Python算法

一、二分查找

1.1 普通的二分查找

1.2 帶旋轉數組的二分查找

1.3 搜尋旋轉排序數組

二、順序查找

三、排序算法

3.1 冒泡排序

3.1 選擇排序

3.3 插入排序

3.4 快速排序

3.5 歸并排序

3.6 希爾排序

參考連結

繼續閱讀

模組化：數學模組化

開源軟體：NoSql資料庫 - 圖資料庫 Neo4j轉載自原文位址：http://www.cnblogs.com/loveis715/p/5277051.html

資料在網絡7層中的傳輸過程

當今世界十大經典算法

字元串功能實作

【算法提高班】貪婪政策

《貪婪的動态規劃》

分治法實作求解最大子數組

【python】：布爾運算

UVA 10154:Weights and Measures Weights and Measures

Linux Kernel Development　學習

動态規劃、最小費用流例題 — nyoj_712 探尋寶藏

計算機開路人阿蘭·圖靈

基礎算法之二分查找

poj3249

PAT 1089 Insert or Merge[難]