刷力扣发现很吃力，好多基础排序很模糊，趁着界面不忙碌总结一下基础排序
# -*- coding:utf-8 -*-
# auther="金木水火"
'''经典排序'''
import random
'''
#冒泡排序
1.比较相邻的数据，按照倒序/顺序，交换值
2.对所有相邻的数据都进行1的操作得到一个最大/最小的数据
3.针对所有数据重复2的步骤，排除最后一个数得到排序的数据
'''
def bubbleSort(L):
'''
时间复杂度:O(n2)，循环37次
空间复杂度:O(n)
变量交换，将最大放到第一位
'''
m = 1
if not isinstance(L,list) or len(L)<2:
print('不支持或者无需排序')
for i in range(len(L)-1):
for j in range(i+1,len(L)):
if L[i]<L[j]:
tmp= L[i]
L[i]=L[j]
L[j]=tmp
m += 1
print(L)
print(m)
def bubbleSort(L):
'''
时间复杂度:O(n2),循环37次
空间复杂度:O(1)
数组自身交换，将最小的放到最后一位
'''
m=1
if not isinstance(L,list) or len(L)<2:
print('不支持或者无需排序')
for i in range(len(L)-1):
for j in range(len(L)-i-1):
if L[j]<L[j+1]:
L[j],L[j+1] = L[j+1],L[j]
m+=1
print(L)
print(m)
def bubbleSort(L):
'''
优化交换逻辑：
第二层循环完毕，数据已经排序完了
这个时候如果第一层循环还没有走完，
后面的循环就是无用的操作了。
优化将第一层无效的循环过滤掉
优化后：
时间复杂度:O(n2),循环34次
空间复杂度:O(1)
'''
m=1
if not isinstance(L,list) or len(L)<2:
print('不支持或者无需排序')
for i in range(len(L)-1):#到不了队尾
tag=False
for j in range(len(L)-i-1):
if L[j]<L[j+1]:
L[j],L[j+1] = L[j+1],L[j]
tag=True
m += 1
if not tag:
break
print(L)
print(m)
'''
选择排期
1.将第一层循环中的当前元素看做最小/大元素
2.第二层循环从剩余未排序的元素中查找元素和1中的最小元素比较大/小，
将比较后的元素和1中的最小/最大元素交换
'''
def bubbleSort(L):
'''
时间复杂度:O(n2),循环37次
空间复杂度:O(1)
'''
m = 1
if not isinstance(L, list) or len(L) < 2:
print('不支持或者无需排序')
maxlen=len(L)
for i in range(maxlen):
minIndex=i
for j in range(i+1,maxlen):
m += 1
if L[j] <L[minIndex]:
minIndex=j #找出最小元素的坐标
if minIndex !=i:
L[i],L[minIndex] = L[minIndex],L[i] #和已经确定的最小元素交换
print(m)
print(L)
'''
插入排序
1.将左边当做有序的，右边是无序的
2.第一层循环无序的,得到当前的数据
3.第二层循环有序的，用2中数据做对比，
大/小做交换，让左边永远保持有序
'''
def bubbleSort(L):
'''
时间复杂度:*O(n2),循环37次
空间复杂度:O(1)
'''
m = 1
if not isinstance(L, list) or len(L) < 2:
print('不支持或者无需排序')
maxLen=len(L)
for i in range(1,maxLen):
for j in range(i):
m +=1
if L[j] < L[i]: #有序右边开始比较
L[j],L[i] =L[i],L[j]
print(m)
print(L)
def bubbleSort(L):
'''
时间复杂度: *O(n2),循环19次
空间复杂度:O(n)
'''
m = 1
if not isinstance(L, list) or len(L) < 2:
print('不支持或者无需排序')
maxLen=len(L)
for i in range(1,maxLen):
j = i
while j >0:
m +=1
# 如果当前元素和有序的最后一个元素比较不满足条件本次循环直接跳出，说明不需要调整当前数据
if L[j] < L[j-1]:#有序左边开始比较
L[j],L[j-1] =L[j-1],L[j]
j -= 1
else:
break
print(m)
print(L)
def bubbleSort(L):
'''
插入排序优化:希尔排序
时间复杂度: O(n2),循环26次
空间复杂度:O(n)
实现逻辑:
1.序列长度取模，总是默认第一个模是有序的，其他是无序的
2.对无序序列循环，得到当前的元素
3.对有序序列循环，将2中元素从左边开始对比，按照条件交换值
4.对序列循环取模，直到模为0
'''
m = 1
if not isinstance(L, list) or len(L) < 2:
print('不支持或者无需排序')
maxlen=len(L)
mod=maxlen//2 #取模运算
while mod >0:
for i in range(mod,maxlen):
j=i
while j >0:
m +=1
if L[j] <L[j-mod]:
L[j],L[j-mod] =L[j-mod],L[j]
j -=mod
else:
break
mod//=2
print(m)
print(L)
def quick_sort(alist, start, end):
"""快速排序
时间复杂度: O(nlogn), 循环26次
空间复杂度: O(n)
1.定义快速排序退出条件，左边位置大于等于右边位置就退出
2.右边开始查找元素，比较和mid的值，小于就交换位置到左边
3.左边开始查找元素，比较和mid的值，大于的就交换位置到右边
4.递归左边序列排序；递归右边序列排序
"""
if start >= end:
return
mid_value = alist[start]
low = start
high = end
while low < high:
while low < high and alist[high] >= mid_value:
high -= 1
mid_value=alist[low]
alist[low] = alist[high]
alist[high] = mid_value
while low < high and alist[low] <=mid_value:
low += 1
mid_value =alist[high]
alist[high] = alist[low]
alist[low] =mid_value
#alist[low] = mid_value
quick_sort(alist, start, low-1)
# 对基准元素右边的子序列进行快速排序
quick_sort(alist, low+1, end)
def merge(left,right):
'''
归并：1. left,right 需要归并的两个序列
2. 比较left,right两边序列的元素，
满足条件的就放到零时序列
3. 将临时序列返回
'''
tmp = list()
i,j=0,0
while i <len(left) and j < len(right):
if left[i] <= right[j]:
tmp.append(left[i])
i +=1
else:
tmp.append(right[j])
j += 1
tmp.extend(left[i:]) #左边剩余未归并进行整体插入
tmp.extend(right[j:]) #右边边剩余未归并进行整体插入
return tmp #返回归并结果
def mergeSort(L):
'''
时间复杂度: O(nlogn)
空间复杂度: O(n)
'''
maxlen=len(L)
if maxlen <=1:
return L
midIndex = maxlen // 2
left=mergeSort(L[:midIndex]) #左边序列归一
right=mergeSort(L[midIndex:]) #右边序列归一
return merge(left,right) #返回归并的结果
if __name__ == '__main__':
li=[random.randint(1,99999) for _ in range(100) ]
print(li)
print(mergeSort(li))
