1、冒泡排序：
def Paosort(A):#冒泡排序
# 时间复杂度为o(n)正序 ---o(n*n) 倒序 ,优点：简单、稳定 但时间复杂度差
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: #作用为判断后续数据是否已有序，若有则退出
break
return A
2、插入排序
def Insertsort(A):#插入排序
# 时间复杂度与冒泡相同
for i in range(1,len(A)):
temp=A[i] #摸一张牌,然后与现有的牌进行比较
while(i>0 and temp<A[i-1]):
A[i]=A[i-1] #交换次数较少
i-=1
A[i]=temp
return A
3、希尔排序
def ShellSort(A, k):
# 原始的希尔排序,改变k值（k=1时）可以转化为插入排序
# 可以通过增加增量序列，来改善希尔序列的复杂度
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] #设定哨兵
self.currentSize=0
def insert(self,item): #插入
self.items.append(item)
self.currentSize+=1
self.percut()
def percut(self): #堆的自我调整
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): # 时间复杂度 O(NlogN)
H=minHeap() # O(n) ,
H.listToHeap(A) #建立最小堆
for i in range(len(A)):
A[i]= H.delMin()
return A
### 采用最大堆进行排序 ###
def Heap_sort(A): #采用最大堆进行排序，使用较多
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):
''' 从最后一个带叶节点的节点进行堆化
i 代表为当前堆的顶点，N代表当前遍历堆的最大数
'''
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=[]): # 合并两个有序的子列
# 时间复杂度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为数组长度
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
排序算法比较
