#coding=utf-8
from collections import deque
#冒泡排序
def bubblesort(l):#复杂度平均O(n*2) 最优O(n) 最坏O(n*2)
for i in range(len(l)-1):
for j in range(len(l)-1-i):
if l[j]>l[j+1]:
temp=l[j]
l[j]=l[j+1]
l[j+1]=temp
return l
#选择排序
def Selectionsort(l):#O(n*2)
for i in range(len(l)-1):
min_temp=i
for j in range(i+1,len(l)):
if l[j]<l[min_temp]:
min_temp=j
if min_temp!=i:
t=l[i]
l[i]=l[min_temp]
l[min_temp]=l[t]
return l
#插入排序
def Insertionsort(l):#复杂度平均O(n*2) 最优O(n) 最坏O(n*2)
for i in range(1,len(l)):
get=l[i]
j=i-1
while j>=0 and l[j]>get:
l[j+1]=l[j]
j-=1
l[j+1]=get
return l
#二分插入排序
def binaryInsertionsort(l):#复杂度平均O(n*2) 最优O(nlogn) 最坏O(n*2)
for i in range(1,len(l)):
get=l[i]
left=0
right=i-1
while left<=right:
mid=(right+left)//2
if l[mid]>get:
right=mid-1
else:
left=mid+1
for j in range(i-1,left-1,-1):
l[j+1]=l[j]
l[left]=get
return l
#希尔排序（插入）
def shellsort(l):#h不同而不同
h=0
while h<=len(l):
h=h*3+1
while h>=1:
for i in range(h,len(l)):
j=i-h
get=l[i]
while j>=0 and l[j]>get:
l[j+h]=l[j]
j=j-h
l[j+h]=get
h=(h-1)//3
return l
#归并排序
def merge(a, b):#O(nlogn)
c = []
h = j = 0
while j < len(a) and h < len(b):
if a[j] < b[h]:
c.append(a[j])
j += 1
else:
c.append(b[h])
h += 1
if j == len(a):
for i in b[h:]:
c.append(i)
else:
for i in a[j:]:
c.append(i)
return c
def merge_sort(lists):
if len(lists) <= 1:
return lists
middle = len(lists)//2
left = merge_sort(lists[:middle])
right = merge_sort(lists[middle:])
return merge(left, right)
#堆排序
def swap(l,i,j):#O(nlogn)
l[i],l[j]=l[j],l[i]
return l
def heap_adjust(l,start,end):
temp=l[start]
i=start
j=i*2
while j<=end:
if j<end and l[j]<l[j+1]:
j+=1
if temp<l[j]:
l[i]=l[j]
i=j
j=i*2
else:
break
l[i]=temp
def heap_sort(l):
l_length=len(l)-1
first_sort_count=l_length//2
for i in range(first_sort_count):
heap_adjust(l,first_sort_count-i,l_length)
for i in range(l_length-1):
l=swap(l,1,l_length-i)
heap_adjust(l,1,l_length-1-i)
l=list(l)[1:]
return l
#快速排序
def quicksort(l,start,end):#复杂度平均O(nlogn) 最优O(nlogn) 最坏O(n*2)
if start<end:
i,j=start,end
base=l[i]
while i<j:
while i<j and l[j]>=base:
j-=1
l[i]=l[j]
while i<j and l[i]<=base:
i+=1
l[j]=l[i]
l[i]=base
quicksort(l,start,i-1)
quicksort(l,j+1,end)
return l
#计数排序
def count_sort(l):#O(n+k)
n=len(l)
k=100
count=[0]*k
target=[0]*k
for i in range(n):
count[l[i]]+=1
for i in range(1,k):
count[i]=count[i]+count[i-1]
for i in range(n-1,-1,-1):
count[l[i]]-=1
target[count[l[i]]]=l[i]
for i in range(n):
l[i]=target[i]
return l