1谦絮、冒泡排序：
def Paosort(A):#冒泡排序
# 時(shí)間復(fù)雜度為o(n)正序 ---o(n*n) 倒序 ,優(yōu)點(diǎn)：簡單、穩(wěn)定 但時(shí)間復(fù)雜度差
for i in range(len(A)-1,-1,-1):
flag=0
for j in range(i):
if A[j]>A[j+1]:
A[j],A[j+1]=A[j+1],A[j]
flag=1
if flag==0: #作用為判斷后續(xù)數(shù)據(jù)是否已有序懂酱，若有則退出
break
return A
2撇他、插入排序
def Insertsort(A):#插入排序
# 時(shí)間復(fù)雜度與冒泡相同
for i in range(1,len(A)):
temp=A[i] #摸一張牌,然后與現(xiàn)有的牌進(jìn)行比較
while(i>0 and temp<A[i-1]):
A[i]=A[i-1] #交換次數(shù)較少
i-=1
A[i]=temp
return A
3茄猫、希爾排序
def ShellSort(A, k):
# 原始的希爾排序,改變k值（k=1時(shí)）可以轉(zhuǎn)化為插入排序
# 可以通過增加增量序列，來改善希爾序列的復(fù)雜度
D = int(len(A) / k)
while (D > 0):
for i in range(D, len(A)):
temp = A[i]
j = i
while (j >= D and temp < A[j - D]):
A[j] = A[j - D]
j -= D
A[j] = temp
D = int(D / 2)
return A
4困肩、堆排序
lass minHeap(object): #最小堆
def __init__(self):
self.items=[0] #設(shè)定哨兵
self.currentSize=0
def insert(self,item): #插入
self.items.append(item)
self.currentSize+=1
self.percut()
def percut(self): #堆的自我調(diào)整
i = self.currentSize
while i // 2 > 0:
if self.items[i] < self.items[i // 2]:
self.items[i], self.items[i // 2] = self.items[i // 2], self.items[i]
i = i // 2
def listToHeap(self,nums):
for num in nums:
self.insert(num)
def getMin(self):
return self.items[1]
def delMin(self):
if self.currentSize==0:
return False
temp = self.items[1]
if self.currentSize==1:
self.items.pop()
return temp
self.items[1]=self.items.pop()
self.currentSize = self.currentSize - 1
i=1
while(i*2<=self.currentSize):
minnum=self.permin(i)
if self.items[i]>self.items[minnum]:
self.items[i],self.items[minnum]=self.items[minnum],self.items[i]
i=i*2
return temp
def permin(self,i):
if i*2+1>self.currentSize:
return i*2
elif self.items[i*2]<self.items[i*2+1]:
return i*2
else:
return i*2+1
def pintHeap(self):
print(H.items[1:])
def HeapSort(A): # 時(shí)間復(fù)雜度 O(NlogN)
H=minHeap() # O(n) ,
H.listToHeap(A) #建立最小堆
for i in range(len(A)):
A[i]= H.delMin()
return A
### 采用最大堆進(jìn)行排序 ###
def Heap_sort(A): #采用最大堆進(jìn)行排序划纽，使用較多
for i in range(len(A)-1,-1,-1):
buildHeap(A, i)
A[i],A[0]=A[0],A[i]
def buildHeap(A,N):
for i in range(N//2,-1,-1):
perdown(A,i,N)
def perdown(A,i,k):
''' 從最后一個(gè)帶葉節(jié)點(diǎn)的節(jié)點(diǎn)進(jìn)行堆化
i 代表為當(dāng)前堆的頂點(diǎn)，N代表當(dāng)前遍歷堆的最大數(shù)
'''
def findmax(i):
if i*2+2>=k:
return i*2
elif A[i*2+1]>A[i*2+2]:
return i*2+1
else:
return i*2+2
while(i*2+1<k):
if A[i] < A[findmax(i)]:
A[i], A[findmax(i)] = A[findmax(i)], A[i]
i=i*2+1
5锌畸、歸并排序
def Merge(A, B, C=[]): # 合并兩個(gè)有序的子列
# 時(shí)間復(fù)雜度O（n）
i=j=0
while (i < len(A) and j < len(B)):
if A[i] > B[j]:
C.append(B[j])
j += 1
else:
C.append(A[i])
i += 1
while(i<len(A)):
C.append(A[i])
i+=1
while(j<len(B)):
C.append(B[j])
j+=1
return C
##遞歸排序##
def Mergesort(A): # N為數(shù)組長度
if len(A) <= 1:
return A
center = len(A) // 2
left = Mergesort(A[:center])
right = Mergesort(A[center:])
return Msort(left, right)
def Msort(left, right):
i, j = 0, 0
result = []
while i < len(left) and j < len(right):
if left[i] > right[j]:
result.append(right[j])
j+=1
else:
result.append(left[i])
i+=1
result+=left[i:]
result+=right[j:]
return result
排序算法比較
