计数权 python 代码 python 设计算法
最编程
2024-03-21 16:25:32
...
感悟:重点不在于代码[通过各种方法最终都能搓出来],而在于思想[多看多了解]。
一、冒泡算法
[bubble_sort]
def bubble_sort(L):
len_for_L = len(L)
for i in range(len_for_L-1):
flag = 0
for j in range(len_for_L-1-i):
if L[j] > L[j+1]:
L[j+1],L[j] = L[j],L[j+1]
flag = 1
if flag == 0:
break
print(L)
L = [1,7,8,4,3,6,5,9,0]
bubble_soft(L)
二、二分查找
# 前提:L必须是提前排好序的
[binary_sort]
def binary_soft(L,x):
lower,higher = 0,len(L)-1
while lower<higher:
mid = (lower + higher) // 2
if x == L[mid]:
return mid
elif x > L[mid]:
lower += 1
elif x < L[mid]:
higher -= 1
L = [1,2,3,4,5,6,7,8,9]
print(binary_soft(L,6))
三、插入排序(很慢)
# 基本思想: 将一个数插入到已经排好序的数据列中,使得新的数据列也是排好序的。
[insert_soft]
def insert_soft(L):
# 依次插入数据
for i in range(1,len(L)):
# 在内部处理排好i之前的所有数据的排序
while i > 0:
if L[i] >= L[i-1]:
break # 核心1[如果已经比前面最后一个值大,就直接结束循环,避免浪费时间]
else:
L[i],L[i-1] = L[i-1],L[i]
i = i-1 # 核心2[不停更换i的值]
return L
四、直接选择排序
[direct_sort]
def direct_sort(L):
for i in range(len(L)-1):
# 找到i之后最小的那一个
min = i
for j in range(i+1,len(L)):
min = j if L[min] > L[j] else min
L[i],L[min] = L[min],L[i]
return L
L = [1,2,3,4,5,7,10,1.2]
print(direct_sort(L))
五、快速排序
# 原创版本[根据快速排序基本思想]
def quick_sort(L,left,right):
if left >= right:
return L
lower = left
higher = right
key = left
# 每一次大while就将L按照[key左边的值都比L[key]小,key右边的值都比L[key]大]
while left < right:
# 进行一次右边比较
while left < right: # 确保右边所有的都比L[key]值大
if L[key] > L[right]:
L[key],L[right] = L[right],L[key]
key = right
break
right -= 1
while left < right: # 确保左边所有的都比L[key]值小
if L[key] < L[left]:
L[key], L[left] = L[left], L[key]
key = left
break
left += 1
# 以上以完成[key左边的值都比L[key]小,key右边的值都比L[key]值大]
quick_sort(L, lower, key-1) # 递归[再次排序key左边所有值]
quick_sort(L, key+1, higher) # 递归[再次排序key右边所有值]
return L
[进一步优化版本]
# quick_sort
def quick_sort(L,left,right):
if left >= right:
return L
lower = left
higher = right
key = left
# 每一次大while就将L按照[key左边的值都比L[key]小,key右边的值都比L[key]大]
while left < right:
# 进行一次右边比较
while left < right and L[right] > L[key]:
right -= 1
# key = right [此句可以省略]
L[key],L[right] = L[right],L[key]
while left < right and L[left] < L[key]:
left += 1
L[key],L[left] = L[left],L[key]
key = left
quick_sort(L, lower, key-1)
quick_sort(L, key+1, higher)
return L
L = [6,2,7,3,8,9,5,10,-1]
print(quick_sort(L,0,len(L)-1))
[以下排序将于2018/8/28更新]
六、希尔排序
[xier_sort原创版本]
[代码中包含插入排序思想,但还是有所不同]
def xier_sort(L):
len_for_L = len(L)
group = len_for_L//2
while group > 0:
# 每循环一次,group值就地板除2
for i in range(0,group+1): # 这里需要加1,确保L[group]和L[group+group..]能正确访问
j = i+group
# 因为这里会存在j-=group和j+=group,
while j < len_for_L:
# 如果是符合后面数大于前面数,就往后走
if L[j] >= L[j-group]:
j+=group
# 如果后面数比前面数字还小,就需要回溯,放置L[j]的值
else:
L[j],L[j-group] = L[j-group],L[j]
j-=group
# 如果出现一个数,比grup还小,那么后续while的j-group就会出问题
if j < group:
j += group
group = group // 2
return L
L = [1,5,4,7,2,9,10,15,-2.5,0,6]
print(xier_sort(L))
[优化版本: 使用temp记录回溯前的j值,减少重复判断]
def xier_sort(L):
len_for_L = len(L)
group = len_for_L//2
while group > 0:
# 每循环一次,group就除以一半
for i in range(0,group+1):
j = i+group
# 因为这里会存在j-=group和j+=group,
while j < len_for_L:
# 如果是符合后面数大于前面数,就往后走
if L[j] >= L[j-group]:
j+=group
temp = j
# 如果后面数比前面数字还小,就需要回溯,放置L[j]的值
else:
L[j],L[j-group] = L[j-group],L[j]
j-=group
# 如果出现一个数,比grup还小,说明已完成对L[j]的排序,直接跳到回溯前的j值
if j < group:
j = temp
group = group // 2
return L
L = [1,5,4,7,2,9,10,15,-2.5,0,6]
print(xier_sort(L))
[c语言版本]
#include <stdio.h>
int data[] = {1,5,4,7,2,9,10,15,-2,0,6};
const int len_for_data = sizeof(data)/sizeof(int);
void go_on(int *a);
void main(){
go_on(data);
for(int i=0; i<len_for_data; i++){
printf("%d\n", data[i]);
}
}
void go_on(int *a){
int temp1, temp2;
int group = len_for_data/2; //地板除
while(group > 0){ //当group = 1的时候
//下面是插入排序逻辑
for(int i=0; i<group+1; i++){
int j = i+group; //模仿插入排序,表示这个一个后面来的数据[要插入]
while(j<len_for_data){
if(a[j] >= a[j-group]){
j+=group;
//记录最后一个排队的人
temp1 = j;
}
else{
temp2 = a[j];
a[j] = a[j-group];
a[j-group] = temp2;
/*printf("%d, %d", a[j], a[j-group]);*/
j -= group; //如果出现后面比前面还小,说明插入排序有问题,就
}
//按照插入排序,j必须大于group才行
//如果小于group,说明前面全排好了,直接跳到最后就行了
if(j<group){
j = temp1;
}
}
}
group = group/2;//修改group,直到group为1做完最后一次排序
}
}
七、归并排序
[基本思想: 先分(拆分成left,right) 后治(合并left,right)]
def dispatch(L):
if len(L)<=1:
return L
mid = len(L)//2
left = dispatch(L[:mid])
right = dispatch(L[mid:])
return merge(left,right)
def merge(left, right):
l,r = 0,0
result = []
# left和right在同等条件下逐个值相互比较
while l < len(left) and r < len(right):
if left[l] <= right[r]:
result.append(left[l])
l+=1 # 如果result得到了左边的数,那么左边计数+1,对左边后一位数进行判断,相反,右边计数不变(等待下一次判断)[这样所有的数都能参与判断]
else:
result.append(right[r])
r += 1 # 同理l+=1
result.extend(left[l:])
result.extend(right[r:])
return result
L = [1,2,9,6,5,4,0,2.1,7.9]
print(dispatch(L))
[将于2018/8/29 更新堆排序]
八、堆排序
def heap_sort(L):
count = len(L)
for root in range(count//2-1, -1, -1):
big_heap(L, root, count-1)
for end in range(count-1,0,-1):
L[end],L[0] = L[0],L[end]
big_heap(L, 0, end-1)
return L
def big_heap(L, root, end):
"""
遍历当前节点和当前节点下方所有节点,确保当前节点一下数据为最大堆
"""
while True:
child = 2*root +1
if child > end:
break
if child+1 <= end and L[child+1] > L[child]:
child += 1
if L[child] > L[root]:
L[child],L[root] = L[root],L[child]
root = child
else:
break
print(heap_sort([1,5,6,9,3,4,2,7,9.5,10.2]))
九、计数排序
[count_sort]
[基本思想]
条件:存在一个列表L
根据列表最大值max[假设列表最小元素为0,所有数都在0~max之间],创建一个max+1大小的列表k[len(k)-1 = max]
然后遍历原始数据,在k中统计L中值和K序号相等的个数
创建一个和列表L相同大小的列表M
逆向遍历列表L,在k中L值对应的序号,在M中根据此序号值放入到M中[每进行一次操作,k中对应序号-1]
个人总结:
计数排序是一种用空间换时间(效率)的排序,过程中需要额外构造新列表(尤其是k列表,对数据的规格要求比较高)
但想法简单,可能适合有些情景(局限性较大),说实话,个人觉得这个算法没什么意思,本不想写的...,但为了博客完整性,还是写在下面了。
def count_sort(L):
list_for_count = [0]*(max(L)+1)
result_list = [0]*len(L)
# 统计原始列表L中各值的元素个数,并将值填入list_for_count中
for content in L:
if list_for_count[content]==0:
list_for_count[content] = L.count(content)
for i in range(1, len(list_for_count)):
list_for_count[i] = list_for_count[i]+list_for_count[i-1]
# 逆向遍历L,在统计列表中查找指定元素的存放位置
for content in L[-1::-1]:
# 此处list_for_count[content]-1(是因为list_for_count统计的是个数,而序列号永远比个数少一)
result_list[list_for_count[content]-1] = content
list_for_count[content] -= 1
return result_list
L = [1,2,9,6,5,4,0,5,8]
print(count_sort(L))
十、基数排序
import math
def bucket_sort(L):
# 首先得到L中最大元素的位数[有几次表示要进行几次桶排序]
max_digit = int(math.ceil(math.log(max(L),10)))
# 根据max_digit创建桶(一共10个桶)
bucket = [[] for i in range(10)]
# eg:如果max_digit=4,当i=0表示判断个位
for i in range(max_digit+1):
# 将数据放入桶中
for content in L:
bucket[content//(10**i)%10].append(content)
# print(bucket)
L = []
# 从桶中取出数据,进行下一次桶排序
for each in bucket:
L.extend(each)
# print(L)
# 清空桶,方便下一次桶排序
bucket = [[] for i in range(10)]
return L
L = [1,2,9,6,5,4,0,10,100,45,67]
print(bucket_sort(L))
补充: content//(10**i)%10 基于
1234//1%10 = 4 # 得到个位
1234//10%10 = 3 # 得到十位
1234//100%10 = 2 # 得到百位
1234//1000%10 = 1 # 得到千位
下一篇: Zookeeper ZAB 协议原理详解
推荐阅读
-
联合国商品贸易统计数据库(UN Comtrade)数据抓取 Python 代码
-
python 冒泡排序算法代码_python 用冒泡方法对 10 个数字排序
-
粒子群算法和鲸鱼算法的比较(Matlab 代码实现 粒子群算法(带约束处理)--Python 和 Matlab 鲸鱼优化算法的实现(Matlab 实现)
-
SBD 算法详情和相关 python 代码
-
Canny 和 Hough 算法的 Python 实现 代码示例分析
-
[ISP 图像处理]流程概述和经典算法(附 python 代码)
-
协作过滤推荐算法的 Python 实现 完整代码示例
-
启发式搜索、A* 算法、均匀成本搜索 (UCS)(附 python 代码和示例)
-
机器人路径规划:基于 A* 算法的机器人路径规划(提供 Python 代码)
-
计数权 python 代码 python 设计算法