python之算法LOB三人组
程序员文章站
2022-07-28 20:16:12
一、冒泡排序 a、冒泡排序 优化 如果冒泡排序中执行一趟而没有交换,则列表已经是有序状态,可以直接结算法 二、选择排序 a、一趟遍历记录最小的数,放到第一个位置; b、在一趟遍历记录剩余列表中最小的数,继续放置 三、插入排序 a、列表被分为有序区和无序区两个部分,最初有序区只有一个元素 b、每次从无 ......
一、冒泡排序
a、冒泡排序----优化
如果冒泡排序中执行一趟而没有交换,则列表已经是有序状态,可以直接结算法
import random from timewrap import * @cal_time def bubble_sort(li): for i in range(len(li) - 1): # i 表示趟数 # 第 i 趟时: 无序区:(0,len(li) - i) for j in range(0, len(li) - i - 1): if li[j] > li[j+1]: li[j], li[j+1] = li[j+1], li[j] @cal_time def bubble_sort_2(li): #冒泡排序优化 for i in range(len(li) - 1): # i 表示趟数 # 第 i 趟时: 无序区:(0,len(li) - i) change = False for j in range(0, len(li) - i - 1): if li[j] > li[j+1]: li[j], li[j+1] = li[j+1], li[j] change = True if not change: return li = list(range(10000)) # random.shuffle(li) # print(li) bubble_sort_2(li) print(li)
二、选择排序
a、一趟遍历记录最小的数,放到第一个位置;
b、在一趟遍历记录剩余列表中最小的数,继续放置
import random from timewrap import * @cal_time 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] li = list(range(10000)) random.shuffle(li) print(li) select_sort(li) print(li)
三、插入排序
a、列表被分为有序区和无序区两个部分,最初有序区只有一个元素
b、每次从无序区选择一个元素,插入到有序区的一个位置,直到无序区变空
import random from timewrap import * @cal_time def insert_sort(li): for i in range(1, len(li)): # i 表示无序区第一个数 tmp = li[i] # 摸到的牌 j = i - 1 # j 指向有序区最后位置 while li[j] > tmp and j >= 0: #循环终止条件: 1. li[j] <= tmp; 2. j == -1 li[j+1] = li[j] j -= 1 li[j+1] = tmp li = list(range(10000)) random.shuffle(li) print(li) insert_sort(li) print(li)