网站商城开发免费网站推广网址
10大排序算法--python
- 一颗星--选择排序
- 一颗星--冒泡排序
- 一颗星--插入排序
- 两颗星--归并排序（递归-难）
- 三颗星--桶排序
- 三颗星--计数排序
- 四颗星--基数排序
- 四颗星--快速排序，寻找标志位（递归-难）
- 四颗星--又是比较难的希尔排序
- 五颗星--堆排序
谁教你这么剪的 | 11大排序的原理讲解和Python源码剖析_哔哩哔哩_bilibili
一颗星–选择排序
自己看代码都能看懂
def xuanze_paixu(bb):
n=len(bb)
for i in range(n-1):
# 优化代码
min=i for j in range(i+1,n):
if bb[i]> bb[j]:
# 优化代码
min=j
bb[i], bb[min] = bb[min], bb[i] # bb[i],bb[j]=bb[j],bb[i]
return bb a=[0,4,0,9,2,8,4,0,1,8]
c=xuanzhe_paixu(a)
print(c)
一颗星–冒泡排序
自己看代码都能看懂
def maopao_paixu(bb):
n=len(bb)
# 左闭右开且递减
for i in range(n-1,-1,-1):
for j in range(0,i):
if bb[j]>bb[j+1]:
bb[j],bb[j+1]= bb[j+1],bb[j]
return bb
a=[7,3,9,8,7,4,9,4,2,4,1,8,7,4,9,1,8,4,7,9]
result=maopao_paixu(a)
print(result)
一颗星–插入排序
def charu_paixu(bb):
n=len(bb)
for i in range(1,n):
x=bb[i]
j=i-1
# 用j的话比较清除
while j>=0:
if x< bb[j]:
bb[j+1]=bb[j]
else:
break
bb[j]=x
j = j - 1
return bb
a=[7,3,9,8,7,4,9,4,2,4,1]
b=charu_paixu (a)
print(b)
两颗星–归并排序（递归-难）
直接给我cpu干蒙了
视频解释
排序算法：归并排序【图解+代码】_哔哩哔哩_bilibili
代码如下，有两种，多参考参考
def merge(a, start, mind, end):
l = start
bb = []
right = mind + 1 while l <= mind and right <= end:
if a[l] <= a[right]:
bb.append(a[l])
l += 1
else:
bb.append(a[right])
right += 1 bb.extend(a[l:mind+1])
bb.extend(a[right:end+1]) for j in range(start, end+1):
a[j] = bb[j - start] print(start, end, bb) def divide(a, start, end):
if start == end:
return mind = (start + end) // 2
divide(a, start, mind)
divide(a, mind+1, end)
merge(a, start, mind, end) a = [7, 3, 9, 8, 7]
divide(a, 0, 4) # 第二种
# 因为在Python中，列表是可变的数据类型，也就是说，当你传递一个列表到一个函数中时，你实际上是传递了这个列表的引用，而不是它的副本。这意味着如果你在函数中修改了这个列表，那么这个改变将会影响到原始的列表。
def merge_sort(arr, start, end):
if start >= end:
return
mid = (start + end) // 2
merge_sort (arr, start, mid)
merge_sort (arr, mid + 1, end)
merge (arr, start, mid, end) def merge(arr, start, mid, end):
left = arr[start:mid + 1]
right = arr[mid + 1:end + 1] i = j = 0
k = start while i < len (left) and j < len (right):
if left[i] <= right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1 while i < len (left):
arr[k] = left[i]
i += 1
k += 1 while j < len (right):
arr[k] = right[j]
j += 1
k += 1 a = [6, 1, 4, 1, 7]
merge_sort (a, 0, len (a) - 1)
print (a)
值得好好研究和阅读，比较像递归和分治
三颗星–桶排序
这个还是比较好理解的
from xuanzhe_paixu import xuanzhe_paixu as slect
def tong_paixu(a):
Min=min(a)
Max=max(a)
bucket_len=(Max-Min)//3+1 #将计算长度的线段分出来算出每个桶的长度
bucket= [[] for _ in range(3)]
for sum in a:
bucket[(sum-Min)//bucket_len].append(sum) # 相减能够计算线段，相除能够计算几倍桶长度
bb=[]
for arry in bucket:
result=slect(arry)
print(result)
for i in result:
bb.append(i)
return bb
b=[6,4,7,1,8,6,4,8,7]
d=tong_paixu(b)
print(d)
三颗星–计数排序
def jisu_paixu(arry):
Max=max(arry)+1
b=[0]*Max
a=[]
for each in arry:
b[each]+=1
for index,i in enumerate(b):
if i!=0:
for j in range(i):
a.append(index)
print(a)
d=[7,6,4,7,4,5,1,8,5,7,4,3,9,5,7,2,9,8,5,7,9,2,8,5,77,43,9]
jisu_paixu(d) # 第二种
def jisu_paixu1(arry):
Max = max (arry) + 1
b = [0] * Max
for each in arry:
b[each]+=1
print(b)
c=[]
for index in range(Max):
while b[index] >0:
c.append(index)
b[index]-=1
return c
d=[7,6,4,7,4,5,1,8,5,7,4,3,9,5,7,2,9,8,5,7,9,2,8,5,77,43,9]
result=jisu_paixu1(d)
print(result)
四颗星–基数排序
就是将得到的列表通过迭代，实现每次少一个数，将最后一个数按数字放入对应的桶中，需要创建一个二维列表,和清空一个二维列表,这个很重要
a = [[] for _ in range (10)]
for i in range (10):
a.append ([])
def jisu_paixu(arry):
a=[]
Max=max(arry)
base=1
for i in range (10):
a.append ([])
while base<Max:
n=0
for each in arry:
a[each//base%10].append(each)
print(a)
for list1 in a:
for i in list1:
arry[n]=i
n+=1
print(arry)
base*=10
a = [[] for _ in range (10)]
b=[3,214,1,24,13]
jisu_paixu(b)
四颗星–快速排序，寻找标志位（递归-难）
def kuaisu_paixu(a,start,end): if start==end: return flag=start binaliang=start+1 for i in range(start+1,end): if a[flag]>a[i]: a[i],a[binaliang]=a[binaliang],a[i] binaliang+=1 a[flag],a[binaliang-1]=a[binaliang-1],a[flag] flag=binaliang-1 print(a[flag],a[start:flag],a[flag+1:end]) kuaisu_paixu(a,start,flag) kuaisu_paixu(a,flag+1,end) a=[4,6,5,3,6,5,3,6,7,7,3,2,4,9,8,4,8,9,2,4,8,9,3,1,3,9] kuaisu_paixu(a,0,len(a)) print(a) # 第二种办法 import random
def kuaisu_paixu(a,start,end):
# random_index=random.randint(start,end-1)
# a[start],a[random_index]=a[random_index],a[start]
# 这个是用来随机快速排序的
flag=start
binaliang=start+1
for i in range(start+1,end):
if a[flag]>a[i]:
a[i],a[binaliang]=a[binaliang],a[i]
binaliang+=1
a[flag],a[binaliang-1]=a[binaliang-1],a[flag]
flag=binaliang-1
print(a[flag],a[start:flag],a[flag+1:end])
return flag
def paixu(a,start,end): if start==end:
return flag=kuaisu_paixu(a,start,end)
paixu(a,start,flag)
paixu(a,flag+1,end)
a=[4,6,5,3,6,5,3,6,7,7,3,2,4,9,8,4,8,9,2,4,8,9,3,1,3,9]
paixu(a,0,len(a))
print(a)
四颗星–又是比较难的希尔排序
这里面有两种方式，一个是切片排序，一个是从头排序
还有希尔排序就是特殊的插入排序，一定要多了解了解，加理解
# 希尔排序就是特殊的插入排序，间隔不在是1，而是gap和cha
def xier_paixu(a):
n=len(a)
gap=n//2
while gap>0:
for i in range(gap,n):
j=i
while j>=gap:
if a[j]<a[j-gap]:
a[j],a[j-gap]=a[j-gap],a[j]
else:
break
j-=gap gap=gap//2
a = [4, 7, 1, 9, 8, 4, 7, 9, 8, 1, 2, 7, 4, 9, 8, 1, 2, 4, 7, 1, 9, 84]
xier_paixu(a)
print(a) # 第二种
def xier_paixu1(alist, start, end):
n = end - start
cha = n // 2
while cha > 0:
for i in range(cha + start, end):
j = i
while j >= start+cha:
if alist[j] < alist[j - cha]:
alist[j], alist[j - cha] = alist[j - cha], alist[j]
else:
break
j -= cha
cha //= 2 return alist a = [4, 7, 1, 9, 8, 4, 7, 9, 8, 1, 2, 7, 4, 9, 8, 1, 2, 4, 7, 1, 9, 84]
start = 2
end = len(a)
print(xier_paixu1(a, start, end))
五颗星–堆排序
## 创建一个列表去执行大顶堆操作，便于排序
def fangwen_paixu(arry):
arry=[None]+arry
# 将列表进行自顶向下的堆排序，不能超过索引
for i in range(len(arry)//2,0,-1):
dui_paixu(arry,i,len(arry)-1)
# 将最顶堆顶端的数与最低端的数交换放入列表中，不断缩小最低端的索引
for i in range(len(arry)-1,0,-1):
arry[i],arry[1]=arry[1],arry[i]
dui_paixu(arry,1,i-1)
return arry
# 创建堆排序函数
##
def dui_paixu(a, start, end):
head=start
jiedian=start*2
while(jiedian<=end):
# 寻找叶子节点最大的值，与头节点比较，将最大的值放入到头节点中
if jiedian+1<=end and a[jiedian]<a[jiedian+1]:
jiedian+=1
if a[head]<a[jiedian]:
a[head],a[jiedian]=a[jiedian],a[head]
# 进行迭代，最后遍历完整个数组，形成大顶堆
head,jiedian=jiedian,jiedian*2
else:
break
# 创建一个测试fangwen_paixu函数
b=[4,6,5,3,6,5,3,6,7,7,3,2,4,9,8,4,8,9,2,4,8,9,3,1,3,9]
c=fangwen_paixu(b)
#把c列表里面的NONE去掉
c.pop(0)
print(c)
记得多看视频多理解理解，反复观看