歸并排序
-
思想
簡單地将原始序列劃分成兩個子序列，分别對每個子序列遞歸排序，最後将排好序的子序列合并為一個有序序列
先拆成一個一個的，然後兩個合并一起，并排好序
兩個兩個的合并成四個的時候，需要左邊一個指針left指向左邊第一個元素，右邊一個指針right指向右邊第一個元素，兩個元素比較，誰小放到左邊，然後挪一下指針
-
性質
穩定
時間複雜度：
O（nlogn）
（最優、最壞一樣）
#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: Caramel
@file: 6.1_merge_sort.py
@time: 2020/02/12
@desc:歸并排序
"""
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:])
'''将兩個有序的子序列合并成一個整體'''
left_index = 0
right_index = 0
result = []
while left_index < len(left_li) and right_index < len(right_li):
if left_li[left_index] <= right_li[right_index]:
'''等号保證穩定性'''
result.append(left_li[left_index])
left_index += 1
else:
result.append(right_li[right_index])
right_index += 1
result += left_li[left_index:]
result += right_li[right_index:]
return result
if __name__ == '__main__':
il = [15, 15, 65, 16, 86, 10, 63]
print(il)
sorted = merge_sort(il)
print(sorted)
-
執行過程
先是對左邊的進行遞歸，分裂直到剩最後一個元素54，然後執行兩個元素[54, 26]的右邊遞歸，得到第一個兩個的右邊元素26
他們兩個執行合并操作，變成[26, 54]。以此類推。
- 執行結束後不是在原有的清單上進行改動，而是在重新生成一個等大的有序清單。雖然時間複雜度降低，但是代價是空間。
排序比較
搜尋
-
二分法查找
前提：
資料已是有序的
操作對象支援下标索引
即是有序順序表
先預處理資料，順序由小到大排列。取中值，關鍵碼與其比較，若果大于就在大的那一部分找，同理。
計算下标時，用第一個和最後一個的下标計算
#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: Caramel
@file: 6.2_binary_search.py
@time: 2020/02/12
@desc:二分查找
"""
def binary_search(alist, item):
'''遞歸'''
n = len(alist)
if n >= 2:
mid = n//2
if alist[mid] == item:
return True
elif item < alist[mid]:
return binary_search(alist[:mid], item)
else:
return binary_search(alist[mid:], item)
return False
def binary_search_2(alist, item):
'''非遞歸'''
n = len(alist)
fir = 0
last = n - 1
while fir <= last:
mid = (last + fir) // 2
if alist[mid] == item:
return True
elif item < alist[mid]:
last = mid - 1
else:
fir = mid + 1
return False
if __name__ == '__main__':
li = [10, 15, 15, 16, 63, 65, 86]
print(binary_search(li, 65))
print(binary_search(li, 98))
print(binary_search_2(li, 65))
print(binary_search_2(li, 98))
ASL：
log2（n+1）-1
成功檢索：
log2（n+1）向上取整
失敗檢索：
log2（n+1）向上或者向下取整
時間複雜度：
最壞：
O（logn）
最好：
O（1）