jupyter notebook 导出的
包括：插入排序/希尔排序；冒泡排序/快速排序；简单选择排序/堆排序；归并排序
xixi=[1,3,5,7,9,2,4,6,8,10]
#插入排序;空间O(1);时间O(n^2)
def insert_sort(lst):
lst=lst[:]#避免替换
for i in range(1,len(lst)):
temp=lst[i]
j=i
while j>0 and lst[j-1]>temp:#寻找插入点
lst[j]=lst[j-1]
j-=1
lst[j]=temp
return lst
print(insert_sort(xixi))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
#希尔排序：O(1);O(nlogn)~O(n^2)
def shell_sort(lst):
lst=lst[:]#避免覆盖
num=step=len(lst)
while True:
step=step//3+1
for i in range(step,num):#除跳跃外，与插入一致
temp=lst[i]
j=i
while j>0 and lst[j-step]>temp:#跳跃寻找插入点
lst[j]=lst[j-step]
j-=step
lst[j]=temp
if step<=1:
break
return lst
shell_sort(xixi)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
#冒泡排序/交换排序；空间O(1),时间O(n^2)
def bubble_sort(lst):
lst=lst[:]#避免替换
for i in range(len(lst)-1):#n-1次循环
for j in range(1,len(lst)-i):#每一轮后最大的在最后面
if lst[j-1]>lst[j]:
lst[j-1],lst[j]=lst[j],lst[j-1]
return lst
print(insert_sort(xixi))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
#快速排序；O(nlogn)~O(n);O(nlogn)
def quick_sort(lst):
lst=lst[:]#避免替换
qsort_rec(lst,0,len(lst)-1)
return lst
def qsort_rec(lst,left,right):
# print(lst,left,right)
if left>=right:
return
i=left
j=right
pivot=lst[i]
while i<j:
while i<j and lst[j]>=pivot:#j向左扫描，找小于pivot的记录
j-=1
lst[i]=lst[j]
while i<j and lst[i]<=pivot:#i向右扫描，找大于pivot的记录
i+=1
lst[j]=lst[i]
lst[i]=pivot
qsort_rec(lst,left,i-1)#排序左侧
qsort_rec(lst,i+1,right)#排序右侧
print(quick_sort(xixi))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
#简单选择排序;空间O(1);时间O(n^2)
def select_srot(lst):
lst=lst[:]#避免替换
for i in range(len(lst)-1):
k=i
for j in range(i,len(lst)):#查找最小位置
if lst[j]<lst[k]:
k=j
if i!=k:
lst[i],lst[k]=lst[k],lst[i]
return lst
print(insert_sort(xixi))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
#堆排序；O(1),O(nlogn)
def heap_sort(lst):
lst=lst[:]#避免覆盖
num=len(lst)
#搭建大顶堆
for i in range(0,num//2)[::-1]:
heap_adjust(lst,i,num)
#堆顶记录与最后一个记录交换
for i in range(0,num)[::-1]:
lst[0],lst[i]=lst[i],lst[0]
heap_adjust(lst,0,i)
return lst
def heap_adjust(lst,i,size):
left=2*i+1
right=2*i+2
max=i
if i<size//2:
if left<size and lst[left]>lst[max]:
max=left
if right<size and lst[right]>lst[max]:
max=right
if max!=i:
lst[max],lst[i]=lst[i],lst[max]#实现本级交换
heap_adjust(lst,max,size)#调整交换后的子结点
heap_sort(xixi)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
#归并排序；O(n);O(nlogn)
def merge_sort(lst):
if len(lst)<=1:
return lst
num=len(lst)//2
left=merge_sort(lst[:num])
right=merge_sort(lst[num:])
return merge(left,right)
def merge(left,right):
i,j=0,0
result=[]
while i<len(left) and j<len(right):
if left[i] <= right[j]:
result.append(left[i])
i+=1
else:
result.append(right[j])
j+=1
result+=left[i:]
result+=right[j:]
return result
merge_sort(xixi)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
xixi
[1, 3, 5, 7, 9, 2, 4, 6, 8, 10]
随手补个煎饼排序，挺有趣的
xixi=[2,4,6,8,10,1,3,5,7,9]
def pancake_sort(lst):
lst=lst[:]
for i in range(len(lst))[::-1]:
#找到最大的那个
# maxIndex=0
# for j in range(1,i+1):
# if lst[j]>lst[maxIndex]:
# maxIndex=j
#求最大的位置
maxIndex=lst[:i+1].index(max(lst[:i+1]))
#翻面一次
lst=lst[:maxIndex+1][::-1]+lst[maxIndex+1:]
#翻面二次
lst=lst[:i+1][::-1]+lst[i+1:]
return lst
print(pancake_sort(xixi))
快速排序优化——尾递归，每一次循环，左侧的交给递归处理，右侧再拆分左右给递归处理，知道最右只剩1个不需要处理
#快速排序；O(nlogn)~O(n);O(nlogn)
def quick_sort(lst):
lst=lst[:]#避免替换
qsort_rec(lst,0,len(lst)-1)
return lst
def qsort_rec(lst,left,right):
# print(lst,left,right)
while right>left:
# if left>=right:
# return
i=left
j=right
pivot=lst[i]
while i<j:
while i<j and lst[j]>=pivot:#j向左扫描，找小于pivot的记录
j-=1
lst[i]=lst[j]
while i<j and lst[i]<=pivot:#i向右扫描，找大于pivot的记录
i+=1
lst[j]=lst[i]
lst[i]=pivot
qsort_rec(lst,left,i-1)#排序左侧
# qsort_rec(lst,i+1,right)#排序右侧
left+=1
