1.二分查找
def binary_search(li,val):
left = 0
right = len(li) - 1
while left <= right: #候选区有值
mid = (left + right) // 2
if li[mid] == val:
return mid
elif li[mid] > val: #待查找值在mid左侧
right = mid - 1
else: #li[mid] < val 待查找值在mid右侧
left = mid + 1
else:
return None
the_list = [1,3,5,7,9]
print(binary_search(the_list,7))`
2.冒泡排序
import random
def bubble_sort(li):
for i in range(len(li)-1): #第i趟
exchange = False
for j in range(len(li)-i-1):
if li[j] > li[j+1]:
li[j],li[j+1] = li[j+1],li[j]
exchange = True
if not exchange:
return
def bubble_reverse_sort(li):
for i in range(len(li)-1): #第i趟
exchange = False
for j in range(len(li)-i-1):
if li[j] < li[j+1]:
li[j],li[j+1] = li[j+1],li[j]
exchange = True
if not exchange:
return
the_list = [random.randint(0,100) for i in range(10)]
print(the_list)
bubble_sort(the_list)
print(the_list)
bubble_reverse_sort(the_list)
print(the_list)
3.选择排序
def select_sort_simple(li):
li_new = []
for i in range(len(li)):
min_val = min(li)
li_new.append(min_val)
li.remove(min_val)
return li_new
def select_sort(li):
for i in range(len(li)-1): #i是第几趟
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]
return li
li = [3,2,4,1,5,6,8,7,9]
print(select_sort(li))
4.插入排序
def insert_sort(li):
for i in range(1,len(li)): #i表示摸到的牌的下标
tmp = li[i]
j = i - 1 #j指的是手里的牌的下标
while j >= 0 and li[j] > tmp:
li[j+1] = li[j]
j -= 1
li[j+1] = tmp
print(li)
li =[3,2,4,1,5,7,9,6,8]
insert_sort(li)
print(li)
5.快速排序
def partition(li,left,right):
tmp = li[left]
while left < right:
while left <right and li[right] >= tmp: #从右边找比tmp小的数
right -= 1 #往左走一步
li[left] = li[right] #把右边的值移到左边空位
while left < right and li[left] <= tmp:
left += 1
li[right] = li[left] #把左边的值移到右边空位上
li[left] = tmp #把tmp归位
return left
def quick_sort(li,left,right):
if left < right: #至少两个元素
mid = partition(li,left,right)
quick_sort(li,left,mid-1)
quick_sort(li,mid+1,right)
li = [5,7,4,6,3,1,2,9,8]
quick_sort(li,0,len(li)-1)
print(li)
6.堆排序
def sift(li,low,high):
"""
li:列表
low:堆的根节点位置
high:堆的最后一个元素的位置
"""
i = low #i开始指向根节点
j = 2*i+1 #j开始是左孩子
tmp = li[low] #把堆顶存起来
while j <= high: #只要j位置有数
if j + 1 <= high and li[j+1] > li[j]: #如果右孩子有并且比较大
j = j + 1 #j指向右孩子
if li[j] > tmp:
li[i] = li[j]
i = j #往下看一层
j = 2*i+1
else: #tmp更大，把tmp放到i的位置上
li[i] = tmp
break
else:
li[i] = tmp #把tmp放到叶子节点上
def heap_sort(li):
n = len(li)
for i in range((n-2)//2,-1,-1):
#i表示建堆的时候调整的部分的根的下标
sift(li,i,n-1)
#建堆完成了
for i in range(n-1,-1,-1):
#i指向当前堆的最后一个元素
li[0],li[i] = li[i],li[0]
sift(li,0,i-1) #i-1是新的high
li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)
heap_sort(li)
print(li)
Python堆排序内置模块
import heapq
import random
li = list(range(100))
random.shuffle(li)
print(li)
heapq.heapify(li) #建堆
n = len(li)
for i in range(n):
print(heapq.heappop(li),end=',')
