二分查找
- def bin_search(data_set, val):
- low = 0
- high = len(data_set) - 1
- while low <= high:
- mid = (low + high)//2
- if data_set[mid]==val:
- return mid
- elif data_set[mid] <val:
- low = mid + 1
- else:
- high = mid - 1
- data = [1,4,2,5,63,4]
- res = bin_search(data,63)
- print(res)
冒泡排序
思路: 首先列表中每两个相邻的数, 如果前边的比后面的大, 那么交换这两个数.
- import random
- def bubble_sort(list1):
- for i in range(len(list1)-1):
- for j in range(len(list1)-i-1):
- if list1[j]>list1[j+1]:
- list1[j],list1[j+1] = list1[j+1],list1[j]
- data = list(range(15))
- random.shuffle(data) #[2, 3, 13, 0, 14, 12, 6, 1, 4, 8, 10, 7, 11, 9, 5]
- print(data)
- res = bubble_sort(data) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
- print(data)
优化后
- import random
- def bubble_sort(list1):
- for i in range(len(list1)-1):
- exchange = False
- for j in range(len(list1)-i-1):
- if (list1[j])>(list1[j+1]):
- list1[j],list1[j+1] = list1[j+1],list1[j]
- exchange = True
- if not exchange:
- break
- data = list(range(20))
- random.shuffle(data)
- print(data) # [5, 1, 14, 13, 6, 15, 7, 12, 2, 16, 11, 9, 18, 8, 17, 3, 4, 10, 0, 19]
- bubble_sort(data)
- print(data) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
选择排序
思路: 一趟遍历记录最小的数, 放到第一个位置, 再一趟遍历记录剩余列表中的最小的值, 依次放置
- import random
- def select_sort(li):
- for i in range(len(li) - 1):
- min_loc = i
- for j in range(i+1,len(li)):
- if li[j]<li[min_loc]:
- min_loc = j
- li[i],li[min_loc] = li[min_loc],li[i]
- data = list(range(20))
- random.shuffle(data)
- print(data)
- select_sort(data)
- print(data)
插入排序
- import random
- def insert_sort(li):
- for i in range(1,len(li)):
- temp = li[i]
- j = i - 1
- while j>=0 and li[j]>temp:
- li[j+1] = li[j]
- j = j-1
- li[j+1] = temp
- data = list(range(20))
- random.shuffle(data)
- print(data)
- insert_sort(data)
- print(data)
快排
思路: 1, 取一个元素 p(第一个元素), 使元素 p 归位
2, 列表被 p 分成两部分, 左边都比 p 小, 右边都比 p 大
3, 递归完成排序
总结: 跟着我, 右手左手一个慢动作, 右手左手慢动作重播
- def quick_sort(data,left,right):
- if left <right:
- mid = partition(data,left,right)
- quick_sort(data,left,mid - 1)
- quick_sort(data,mid+1,right)
- def partition(data,left,right):
- tmp = data[left]
- while left < right:
- while left<right and data[right]>=tmp: # 右手
- right -= 1
- data[left] = data[right]
- while left<right and data[left]<=tmp: # 左手
- left += 1
- data[right] = data[left]
- data[left] = tmp
- return left
- import random
- data = list(range(20))
- random.shuffle(data)
- print(data) # [19, 4, 0, 7, 14, 8, 2, 12, 11, 17, 13, 3, 18, 10, 6, 1, 15, 5, 16, 9]
- quick_sort(data,0,len(data)-1)
- print(data) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
来源: http://www.bubuko.com/infodetail-2703363.html