Bubble Sort（冒泡排序）:
exp1:
def bubble(a):
m=0
for i in range(len(a)):
is_sorted=True
for j in range(len(a)-1-i):
if a[j]>a[j+1]:
a[j],a[j+1]=a[j+1],a[j]
is_sorted=False
if(is_sorted):
break
return a
b=[4,2,5,1,7,3,8,9,0,6]
bubble(b)
输出结果：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
c=bubble(b)
c.reverse() //反向排序
c
输出结果：[9, 8, 6, 6, 5, 4, 3, 3, 2, 1, 0]
时间复杂度为O(n*n),适合大型的数组排序。
Insert Sort(插入排序):
exp1:
def insert_sort(a):
for i in range(1,len(a)):
j=i
while j>0 and a[j]<a[j-1]:
a[j-1],a[j]=a[j-1],a[j]
j=j-1
return a
时间复杂度O(n*n),适合于小型数组排序，速度更快，实际使用更多。
Select Sort(选择排序):
exp1(通过index来进行比较交换):
def select_sort1(a):
for i in range(0,len(a)-1):
min_inx=i
for j in range(i+1,len(a)):
if a[min_inx]>a[j]:
min_inx=j
a[i],a[min_inx]=a[min_inx],a[i]
return a
时间复杂度O(n*n)
exp2(通过直接比较数字来进行交换):
def select_sort(a):
for i in range(0,len(a)-1):
j=i
for j in range(i,len(a)-1):
if a[i]>a[j+1]:
a[i],a[j+1]=a[j+1],a[i]
return a
时间复杂度O(n*n)
Sorted和a.sort(系统自带的排序方法)：
由merge sort和insert sort合成的
速度最快的排序方法，无论是数组多大多小
时间复杂度O(n*log n)
Merge Sort(合并排序):
exp1:
def _merge(a: list,b: list)->list:
c=[]
while len(a)>0 and len(b)>0:
if a[0]<b[0]:
c.append(a[0])
a.remove(a[0])
else:
c.append(b[0])
b.remove(b[0])
if len(a)==0:
c+=b
else:
c+=a
return c
def _merge_sorted(nums: list)->list:
if len(nums)<=1:
return nums
m=len(nums)//2
a=_merge_sorted(nums[:m])
b=_merge_sorted(nums[m:])
return _merge(a,b)
a=[3,4,2,7,1,0,9,8,6,5,10]
_merge_sorted(a)
输出结果：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
时间复杂度O(n*log n)
Quick Sort(快速排序):
exp1：
def _quick_sorted(nums:list) -> list:
if len(nums)<=1:
return nums
pivot=nums[0]
left_nums=_quick_sorted([x for x in nums[1:]if x<pivot])
right_nums=_quick_sorted([x for x in nums[1:]if x>=pivot])
return left_nums+[pivot]+right_nums
def quick_sorted(nums:list,reverse=False)->list:
nums=_quick_sorted(nums)
if reverse:
nums=nums[::-1]
return nums
a=[1,3,5,11,4,6,8,9,10]
quick_sorted(a,reverse=False)
输出结果：
[1, 3, 4, 5, 6, 8, 9, 10, 11]