搜索与排序
（一）二分搜素
Binary Search (iterative):
def bi_search_iter(alist, item):
left, right = 0, len(alist) - 1
while left <= right:
mid = (left + right) // 2
if alist[mid] < item:
left = mid + 1
elif alist[mid] > item:
right = mid - 1
else: # alist[mid] = item
return mid
return -1
Binary Search (recursive):
def bi_search_re(num_list, val):
def bi_search(l, h):
# Not found
if l > h:
return -1
# Check mid
mid = (l + h) // 2
if (num_list[mid] == val):
return mid;
elif (num_list[mid] < val):
return bi_search(mid + 1, h)
else:
return bi_search(l, mid - 1)
return bi_search(0, len(num_list))
（二）排序
1. 冒泡排序
稳定的排序
O(n^2)
def _bubble_sort(nums: list):
for i in range(len(nums)-1):
# Get (i+1) largest in the correct position
for j in range(len(nums) - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
优化：
def bubble_sort_mod(array):
for i in range(len(nums)-1):
is_sorted = True
for j in range(len(nums) - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
is_sort = False
if is_sorted:break
2. 选择排序
不稳定的排序
O(n^2)
def selection_sort(items):
for i in range(len(items)-1): # n
pos_min = i #idx
for j in range(i + 1, len(items)): # n
if (items[j] < items[pos_min]):
pos_min = j
items[i], items[pos_min] = items[pos_min], items[i]
