# 无序列表的顺序搜索 defsequential_search(alist, item): pos = 0 found = False while pos < len(alist) andnot found: if alist[pos] == item: found = True else: pos = pos + 1 return found
假设列表中的元素按升序排列,搜索的效率会比无序列表高一些:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
# 有序列表的顺序搜索 defordered_sequential_search(alist, item): pos = 0 found = False stop = False while pos < len(alist) andnot found andnot stop: if alist[pos] == item: found = True else: if alist[pos] > item: stop = True else: pos = pos + 1 return found
顺序搜索的时间复杂度:O(n)
二分搜索
对于有序列表可以从中间的水元素着手,将其和目标元素比较,这样可以很快地排除一半的元素:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
# 有序列表的二分搜索 defbinary_search(alist, item): first = 0 last = len(alist) - 1 found = Fasle while first <= last andnot found: mid_point = (first + last) // 2 if alist[mid_point] == item: found = True else: if item < alist[mid_point]: last = mid_point - 1 else: first = mid_point + 1 return found
defbubble_sort(alist): 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]
definsertion_sort(alist): for index in range(1, len(alist)): current_value = alist[index] position = index while position > 0and alist[position-1] > current_value: alist[position] = alist[position-1] position = position-1 alist[position] = current_value
defshell_sort(alist): sublistcount = len(alist) // 2 while sublistcount > 0: for startposition in range(sublistcount): gap_inserttion_sort(alist, startposition, sublistcount) print("After increments of size", sublistcount, "The list is", alist) sublistcount = sublistcount // 2 defgap_inserttion_sort(alist, start, gap): for i in range(start+gap, len(alist), gap): current_value = alist[i] position = i while position >= gap and \ alist[position-gap] > current_value: alist[position] = alist[position-gap] position = position-gap alist[position] = current_value >>> alist = [54, 26, 93, 17, 77, 31, 44, 55, 20] >>> shell_sort(alist) After increments of size 4 The list is [20, 26, 44, 17, 54, 31, 93, 55, 77] After increments of size 2 The list is [20, 17, 44, 26, 54, 31, 77, 55, 93] After increments of size 1 The list is [17, 20, 26, 31, 44, 54, 55, 77, 93]