入门小菜鸟,希望像做笔记记录自己学的东西,也希望能帮助到同样入门的人,更希望大佬们帮忙纠错啦~侵权立删。
目录
一、冒泡排序
比较两个相邻元素的大小,然后根据大小交换位置,这样从列表左端开始冒泡,最后最大值会依次从右端冒出。
def bubbling(data):
for i in range(len(data)):
for j in range(len(data) - i - 1):
if data[j] > data[j+1]:
data[j],data[j+1] = data[j+1],data[j]
return data
时间复杂度为O(n²)
二、选择排序
把序列中的最小值或者最大值找出来放在起始位置,然后再从剩下的序列中找出极值放到起始位置之后,以此类推最后就完成排序。
def select(data):
l = len(data)
for i in range(l-1):
t = i
for j in range(i+1,l):
if data[j] > data[t]:
j,t = t,j
if t != i:
data[i],data[t] = data[t],data[i]
return data
时间复杂度为O(n²)
三、插入排序
首先构建一个初始的有序序列,然后从无序序列中抽取元素,插入到有序序列的相对排序位置。
简单来说就是从第二个位置开始遍历,与它前面的元素相比较,如果比前面元素小就交换位置。
很适合用在合并两个有序序列,并且合并后的序列依旧有序这样的情况下。
def insert(data):
l = len(data)
for i in range(1,l):
for j in range(i,0,-1):
if data[j] < data[j-1]:
data[j],data[j-1] = data[j-1],data[j]
return data
时间复杂度为O(n²)
四、快速排序
从序列中找出一个基准元素,大于该元素的放到一边,小于该元素的放到另一边形成分区;然后分别从大小分区中再找基准再分别分出相对大小分区,通过递归完成快速排序。
def quick(data):
if len(data) >= 2:
m = data[0] #基准值,随你取
#左右分区
l = []
r = []
data.remove(m)
for i in data:
if i >= m:
r.append(i)
else:
l.append(i)
return quick(l) + [m] + quick(r)
else:
return data
这种算法可以通过一些方式提高速度,比如说使用并行的元素分区,在超大数据中使用多机进行联合排序,将两个分区拆分为更多分区等。
五、归并排序
将数据分为两个数组,然后比较两个数组最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。
def merge(data):
#分治操作
length = len(data)
if length <= 1:
return data
n = length//2
left = merge(data[:n])
right = merge(data[n:])
#合并操作
l,r = 0,0
result = []
while l < len(left) and r < len(right):
if left[l] < right[r]:
result.append(left[l])
l = l + 1
else:
result.append(right[r])
r = r + 1
result = result + left[l:]
result = result + right[r:]
return result
六、希尔排序
希尔排序按照下标的增量对数据进行分组,对每组使用直接插入排序算法排序,然后随着下标增量的减少,每组包含的数据越来越多,当增量减至1时恰好分成一组,输出即为最终结果。
思想:随着进行相对比较的两个元素之间的距离的减小,相对元素的大小会逐步区分出来并向两端聚拢,当步长为1的时候,就完成最后一次比较,那么序列顺序就出来了。
def xier(data):
l = len(data)
s = l // 2
while s > 0:
for i in range(s,l):
t = i
while t >= s and data[t - s] > data[t]:
data[t - s],data[t] = data[t],data[t-s]
t = t - s
s = s // 2
return data
欢迎大家在评论区批评指正,谢谢~