In [7]:
def binary_search(list_, item):
if len(list_) == 0:
return False
middle = len(list_) / 2
if item == list_[middle]:
return True
else:
if item > list_[middle]:
return binary_search(list_[middle+1:], item)
else:
return binary_search(list_[:middle-1], item)
print binary_search([0, 1, 2, 8, 13, 17, 19, 32, 42], 32)
In [21]:
def bubble_sort(list_):
for passnum in range(len(alist)-1,0,-1):
for i in range(passnum):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
alist = [54,26,93,17,77,31,44,55,20]
bubble_sort(alist)
print(alist)
In [1]:
def selection_sort(alist):
for fillslot in range(len(alist)-1,0,-1):
positionOfMax=0
for location in range(1,fillslot+1):
if alist[location]>alist[positionOfMax]:
positionOfMax = location
temp = alist[fillslot]
alist[fillslot] = alist[positionOfMax]
alist[positionOfMax] = temp
alist = [54,26,93,17,77,31,44,55,20]
selection_sort(alist)
print(alist)
In [20]:
def insertion_sort(alist):
for index in range(1,len(alist)):
currentvalue = alist[index]
position = index
while position>0 and alist[position-1]>currentvalue:
alist[position]=alist[position-1]
position = position-1
alist[position]=currentvalue
alist = [54,26,93,17,77,31,44,55,20]
insertion_sort(alist)
print(alist)
In [19]:
def merge_sort(alist):
if len(alist) <= 1:
return alist
print "Split", alist
mid = len(alist) / 2
# 递归调用
left = merge_sort(alist[:mid])
right = merge_sort(alist[mid:])
return merge(left, right)
def merge(left_half, right_half):
i = j = 0
result = []
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
result.append(left_half[i])
i += 1
else:
result.append(right_half[j])
j += 1
result += left_half[i:]
result += right_half[j:]
print "Merge", result
return result
alist = [54,26,93,17,77,31,44,55,20]
result = merge_sort(alist)
print(result)