二分法查找
def binary_search(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
l, r = 0, len(nums)-1
while l <= r:
mid = (l + r) // 2
if nums[mid] > target:
r = mid - 1
elif nums[mid] < target:
l = mid + 1
else:
return mid
return -1
快速排序
def q_sorted(lst):
if len(lst) < 2:
return lst
pivot = lst[0]
small, medium, large = [], [], []
for item in lst:
if item < pivot:
small.append(item)
elif item > pivot:
large.append(item)
else:
medium.append(item)
return q_sort(small) + medium + q_sort(large)
冒泡排序
def bubble_sorted(lst):
l = list(lst)
for i in range(len(l)-1):
flag = True
for j in range(len(l)-1-i):
if l[j] > l[j+1]:
l[j], l[j+1] = l[j+1], l[j]
flag = False
if flag:
return l
return l
选择排序
def select_sorted(lst):
l = lst[:]
for i in range(len(l)-1):
min = i
for j in range(i+1, len(l)):
if l[j] < l[min]:
min = j
l[i], l[min] = l[min], l[i]
return l
插入排序
def insert_sorted(lst):
l = lst[:]
for i in range(1, len(l)):
value = l[i]
index = i
for j in range(i-1, -1, -1):
if l[j] > value:
l[j+1] = l[j]
index = j
else:
break
l[index] = value
return l
