基于python常用排序與查找

"""
排序與查找
    -- 冒泡排序
    -- 選擇排序
    -- 快速排序 --****經典
    -- 希爾排序
"""
# 常用排序的實作

# 冒泡排序-每輪排出最大 時間復雜度O(n**2)
def bubble(list_):
    if list_: # 非空串列排序
        # 外層表示比較輪數
        for i in range(len(list_)-1):
            # 表示每輪兩兩比較的次數
            for j in range(len(list_)-1-i):
                if list_[j] > list_[j+1]:
                    list_[j],list_[j+1] = list_[j+1],list_[j]
    else: # 空串列報例外
        raise ValueError

# 選擇排序
def select_sort(list_):
    # 外側回圈n-1輪
    for i in range(len(list_)-1):
        # 假設list_[i]最小
        min = i
        for j in range(i+1,len(list_)):
            if list_[min] > list_[j]:
                # 擂主換人
                min = j
        #進行交換，將最小值換到應該在的位置
        if min != i:
            list_[i],list_[min] = list_[min],list_[i]

# 插入排序
def insert_sort(list_):
    # 外側回圈n-1輪,每次比較的數，從第二個數開始
    for i in range(1,len(list_)):
        # 空出list_[i]的位置
        x = list_[i]
        j = i-1
        while j >= 0 and list_[j] > x:
            list_[j+1] = list_[j]
            j -= 1
        list_[j +1] = x

# 完成一輪交換
def sub_sort(list_,low,high):
    # 選定基準
    x = list_[low]
    # low 向后，high向前
    while low < high:
        # 后面的數前放
        while list_[high] >= x and high > low:
            high -= 1
        list_[low] = list_[high]
        # 前面數后放
        while list_[low] < x and low < high:
            low += 1
        list_[high] = list_[low]
    list_[low] = x


# 快速排序(升序) # low,high = 0,len(list01)-1
# low表示串列的第一個元素索引，high表示最后一個元素索引
def quick_sort(list_,low,high):
    """
    1.取出0號元素，賦值，從串列尾部開始比較，
        只要比較出比該值小的，被比較的值放頭部，
            賦值值放那個移動額位置
    2.因第一次比較，分出大于原0號元素和小于0號
        元素的兩部分數，兩部分數分別重復1,2
    3.直到比較完，結束
    :return:
    """
    if low < high:
        sub_sort(list_,low,high)

#快排的主函式，傳入引數為一個串列，左右兩端的下標
def QuickSort(list,low,high):
    if high > low:
        #傳入引數，通過Partitions函式，獲取k下標值
        k = Partitions(list,low,high)
        #遞回排序串列k下標左側的串列
        QuickSort(list,low,k-1)
        # 遞回排序串列k下標右側的串列
        QuickSort(list,k+1,high)

def Partitions(list,low,high):
    left = low
    right = high
    #將最左側的值賦值給參考值k
    k = list[low]
    #當left下標，小于right下標的情況下，此時判斷二者移動是否相交，若未相交，則一直回圈
    while left < right :
        #當left對應的值小于k參考值，就一直向右移動
        while list[left] <= k:
            left += 1
        # 當right對應的值大于k參考值，就一直向左移動
        while list[right] > k:
            right = right - 1
        #若移動完，二者仍未相遇則交換下標對應的值
        if left < right:
            list[left],list[right] = list[right],list[left]
    #若移動完，已經相遇，則交換right對應的值和參考值
    list[low] = list[right]
    list[right] = k
    #回傳k值
    return right

# 二分查找(有序陣列)
def binary_search(list_,key):
    low, high = 0,len(list_)-1
    # 判斷條件
    while low < high:
        mid = (low+high) // 2
        if list_[mid] < key:
            low = mid + 1
        elif list_[mid] > key:
            high = mid -1
        else:
            return mid


list02 = [1,2,3,4,5,6,7,8,9,10]
print("key index:",binary_search(list02,8))

# list_demo = [6,1,2,7,9,3,4,5,10,8]
# print(list_demo)
# QuickSort(list_demo,0,9)
# print(list_demo)

#----------------------------
# if __name__ == "__main__":
#     print("-"*30)
#     list01 = [5,2,57,12,4,9,40,25,3]
#     # bubble(list01)
#     #print(list01)
#     print(sub_sort(list01,0,8))
#     print(list01)

標籤：Python

上一篇：10_多協程

下一篇：windows下搭建虛擬環境