文章目录
- 前言
- 一、排序算法的稳定性
- 1.冒泡排序
- 2.选择排序
- 3.插入排序
- 4.快速排序
- 5.希尔排序
- 6.归并排序
- 二、搜索
- 二分查找
以下是花圃在学习Python的数据结构与算法的一些要点内容笔记。
一、排序算法的稳定性
排序算法（Sorting aigorithm），之前我们再说数据结构时候，说到顺序表、链表，那么这之中存储的数据是可以按照特定顺序进行排序的，所以我们将这种能够将一串数据进行排序的算法称之为排序算法。
排序算法稳定性是指让原本相等键值的记录维持相对的次序。
1.冒泡排序冒泡排序（Bubble Sort），是一种最基础的交换排序。之所以叫做冒泡排序，因为每一个元素都可以像小气泡一样，根据自身大小一点一点向数组的一侧移动。
每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟 *** 作。
而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。
稳定性：稳定
import time
def bubble_sort(lista):
if len(lista)<=1:
return lista
elif len(lista)==2:
if lista[0]>lista[1]:
lista[0],lista[1] = lista[1],lista[0]
return lista
else:
for j in range(len(lista)-2):
for i in range(len(lista)-2-j):
if lista[i]>lista[i+1]:
lista[i],lista[i+1]=lista[i+1],lista[i]
pass
pass
pass
return lista
pass
def bubble_sort_u(lista):
if len(lista)<=1:
return lista
elif len(lista)==2:
if lista[0]>lista[1]:
lista[0],lista[1] = lista[1],lista[0]
return lista
else:
for j in range(len(lista)-2):
count=0
for i in range(len(lista)-2-j):
if lista[i]>lista[i+1]:
lista[i],lista[i+1]=lista[i+1],lista[i]
count+=1
pass
pass
if count==0:
return lista
pass
return lista
pass
list1=[]
list2=[13,1]
list3=[55,20,12,88,66,33,44,99,100,40,60,23]
print(bubble_sort(list1))
print(bubble_sort(list2))
print(bubble_sort(list3))
list4=list(range(10000))
start_time1=time.time()
bubble_sort(list4)
end_time1=time.time()
print(end_time1-start_time1)
start_time2=time.time()
bubble_sort_u(list4)
end_time2=time.time()
print(end_time2-start_time2)
[]
[1, 13]
[12, 20, 33, 40, 44, 55, 60, 66, 88, 99, 100, 23]
4.7323689460754395
0.0010275840759277344
在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；以此类推，直到所有元素均排序完毕。
稳定性：不稳定
import time
list1=[]
list2=[13,1]
list3=[55,20,12,88,66,33,44,99,100,40,60,23]
list4=list(range(10000))
def choose_sort(lista):
if len(lista)<=1:
return lista
elif len(lista)==2:
if lista[0]>lista[1]:
lista[0],lista[1] = lista[1],lista[0]
return lista
else:
for j in range(len(lista)):
count=0
for i in range(j+1,len(lista)):
if lista[j]>lista[i]:
lista[j],lista[i]=lista[i],lista[j]
count+=1
pass
pass
if count==0:
return lista
pass
return lista
pass
start_time1=time.time()
print(["choose_sort"],choose_sort(list3))
end_time1=time.time()
print(end_time1-start_time1)
start_time3=time.time()
choose_sort(list4)
end_time3=time.time()
print(end_time3-start_time3)
print("===========================================================")
def choose_sort_u(lista):
if len(lista)<=1:
return lista
elif len(lista)==2:
if lista[0]>lista[1]:
lista[0],lista[1] = lista[1],lista[0]
return lista
else:
for j in range(len(lista)-1):
min=j
for i in range(j+1,len(lista)):
if lista[j]>lista[i]:
min=i
pass
pass
lista[j],lista[min]=lista[min],lista[j]
return lista
pass
start_time2=time.time()
print(["choose_sort_u"],choose_sort_u(list3))
end_time2=time.time()
print(end_time2-start_time2)
start_time4=time.time()
choose_sort(list4)
end_time4=time.time()
print(end_time4-start_time4)
['choose_sort'] [12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
0.0
0.000997304916381836
===========================================================
['choose_sort_u'] [12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
0.0
0.0029985904693603516
（1.从第一个元素开始，该元素可以认为已经被排序
（2.取下一个元素tem，从已排序的元素序列从后往前扫描
（3.如果该元素大于tem，则将该元素移到下一位
（4.重复步骤（3，直到找到已排序元素中小于等于tem的元素
（5.tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置
（6.重复步骤（2~（5
稳定性：稳定
import time
list1=[]
list2=[13,1]
list3=[55,20,12,88,66,33,44,99,100,40,60,23]
list4=list(range(10000))
def insert_sort(lista):
if len(lista)<=1:
return lista
elif len(lista)==2:
if lista[0]>lista[1]:
lista[0],lista[1] = lista[1],lista[0]
return lista
else:
for i in range(1,len(lista)):
for j in range(i):
if lista[i]<lista[j]:
lista[i],lista[j]=lista[j],lista[i]
pass
else:
continue
pass
pass
return lista
pass
def insert_sort_u(lista):
if len(lista)<=1:
return lista
elif len(lista)==2:
if lista[0]>lista[1]:
lista[0],lista[1] = lista[1],lista[0]
return lista
else:
for i in range(1,len(lista)):
while i>0:
if lista[i]<lista[i-1]:
lista[i],lista[i-1]=lista[i-1],lista[i]
i-=1
pass
else:
break
pass
pass
pass
return lista
print(insert_sort(list3))
print(insert_sort_u(list3))
start_time5=time.time()
insert_sort(list4)
end_time5=time.time()
print(end_time5-start_time5)
start_time6=time.time()
insert_sort_u(list4)
end_time6=time.time()
print(end_time6-start_time6)
[12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
[12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
4.825546503067017
0.0009644031524658203
def quick_sort(lista,first,last):
if first>=last:
return
mid_value=lista[first]
low=first
high=last
while low<high:
while low<high and lista[high]>=mid_value:
high-=1
pass
lista[low]=lista[high]
while low<high and lista[low]<mid_value:
low+=1
pass
lista[high]=lista[low]
pass
lista[low]=mid_value
quick_sort(lista,first,low-1)
quick_sort(lista,low+1,last)
pass
list3=[55,20,12,88,66,33,44,99,100,40,60,23]
quick_sort(list3,0,len(list3)-1)
print(list3)
[12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
希尔排序（Shell Sort）实际上是对插入排序的改进。
1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述 *** 作…
2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
稳定性：不稳定
import time
def Shell_sort_u(lista):
if len(lista) <= 1:
return lista
elif len(lista) == 2:
if lista[0] > lista[1]:
lista[0], lista[1] = lista[1], lista[0]
return lista
else:
gap=len(lista)//2
while gap>=1:
for i in range(gap, len(lista)):
while i>0:
if lista[i]<lista[i-gap]:
lista[i],lista[i-gap]=lista[i-gap],lista[i]
i-=gap
pass
else:
break
pass
pass
gap//=2
pass
return lista
pass
list3_4=[55,20,12,88,66,33,44,99,100,40,60,23]
print(Shell_sort_u(list3_4))
start_time8=time.time()
Shell_sort_u(list(range(10000)))
end_time8=time.time()
print(end_time8-start_time8)
print("***************************")
list6_1=[20,1,11,10,19,55,66,47,49,32,81,73,100,70,121,586,41,2,78,9,1,3]
print(Shell_sort_u(list6_1))
[12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
0.01695561408996582
***************************
[1, 1, 2, 3, 9, 10, 11, 19, 20, 32, 41, 47, 49, 55, 66, 70, 73, 78, 81, 100, 121, 586]
def merge_sort(lista):
mid_value=len(lista)//2
if len(lista)<=1:
return lista
left_li=merge_sort(lista[:mid_value])
right_li=merge_sort(lista[mid_value:])
left_pointer,right_pointer=0,0
result=[]
while left_pointer<len(left_li) and right_pointer<len(right_li):
if left_li[left_pointer]<=right_li[right_pointer] :
result.append(left_li[left_pointer])
left_pointer+=1
pass
else:
result.append(right_li[right_pointer])
right_pointer+=1
pass
pass
result+=left_li[left_pointer:]
result+=right_li[right_pointer:]
return result
pass
if __name__=="__main__":
list3_1=[55,20,12,88,66,33,44,99,100,40,60,23]
print(merge_sort(list3_1))
[12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
稳定性：稳定
二、搜索 二分查找首先对于一个普通的序列去查找某个元素或者搜索某个元素是否存在，我们不用所谓的二分查找也可以做到，无非是从头到尾去查找，但我们联想日常翻书的情景，我们发现，我们在一开始都是先翻一半，判断目的章节在该部分的哪一个位置，前或者后，然后依次再去把该部分进行折半。
二分查找就类似这样的过程，那么显然要求我的序列要是有序的，在之前学的顺序表是可以 *** 作的，而且要支持索引。
递归版本：
def binary_search(lista,item):
if len(lista)>0:
mid_value=len(lista)//2
if lista[mid_value]==item:
return True
elif lista[mid_value]>item:
return binary_search(lista[:mid_value],item)
pass
else:
return binary_search(lista[mid_value+1:],item)
pass
return False
if __name__=="__main__":
list3_1=[55,20,12,88,66,33,44,99,100,40,60,23]
print(merge_sort(list3_1))
print(binary_search(merge_sort(list3_1),100))
[12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
True
非递归版本：
def binary_search_u(lista,item):
first=0
last=len(lista)-1
while first<=last:
mid_value=(first+last)//2
if lista[mid_value]==item:
return True
elif lista[mid_value]>item:
last=mid_value-1
pass
else:
first=mid_value+1
pass
pass
return False
if __name__=="__main__":
list3_1=[55,20,12,88,66,33,44,99,100,40,60,23]
print(merge_sort(list3_1))
print(binary_search(merge_sort(list3_1),100))
print(binary_search_u(merge_sort(list3_1),100))
[12, 20, 23, 33, 40, 44, 55, 60, 66, 88, 99, 100]
True
True
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）