誰教你這么剪的 | 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)

記得多看視頻多理解理解，反復觀看