Python的排序算法
https://i-blog.csdnimg.cn/direct/89a2e728798a4624b517ac5165e1c0f2.png一、算法
1.1 算法概念
算法就是计算机解决问题的方法或者步骤
程序 = 数据结构 + 算法
1.2 算法的特性
1】确定性: 算法的每条语句具有明白的意思,不能模棱两可
2】有穷性:在执行一定的时间后,能自动竣事算法
3】输入:至少有0个或者多个的输入
4】输出:至少要有一个输出
5】可行性:经济可行,社会可行
1.3 算法的设计要求
1】正确性:对于正确的输入,会给出正确的效果。
2】健壮性:对于错误的输入,要给出合理的处置处罚
3】可读性:要代码有适当的注释,命名规范
4】高效率:要求时间复杂度尽大概低
5】低存储:空间复杂度尽大概低
1.4 算法时间复杂度(T(n))
1> 算法时间复杂度计算公式:T(n) = O(f(n));
T(n):时间复杂度
n:表示问题的规模
f(n) :是问题规模与执行次数之间的函数
O(f(n)):使用O阶记法,记录算法时间复杂度
2> 时间复杂度推导
https://i-blog.csdnimg.cn/direct/32b7987de224410784c44a0389c50f22.png
3> 常见的时间复杂度
https://i-blog.csdnimg.cn/direct/35424af1fe404f52bf8791079fe99ab0.png
二、排序算法
2.1 概念
1】定义:将给定的序列,按照特定的次序进行排列的一种算法
2】种类:
1.交换类排序:冒泡排序、快速排序
2.选择类排序:简单选择排序、堆排序
3.插入类排序:直接插入排序、折半插入排序、希尔排序
4.归并排序:二路归并、三路归并。。。
5.基数排序
2.2 冒泡排序
概念和原理:
冒泡排序:是一种简单的排序算法,它重复的遍历要排序的序列,一次比力两个元素,如果他们的次序错误,就把他们交换过来。
冒泡排序算法的运作如下:
[*]比力相邻的元素。如果第一个比第二个大(升序),就交换他们两个。
[*]对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
[*]针对全部的元素重复以上的步骤,除了最后一个。
[*]持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比力。
时间复杂度:O(n^2)
算法实现:
#定义冒泡函数
def bubble_sort(alist):
j=0
while j<len(alist): #确定序列中数据
i=0
while i<len(alist)-1-j: #一个序列中两两比较的次数
if alist > alist:#前一个元素比后一个元素大 交互
alist,alist = alist,alist
i+=1
j+=1 https://i-blog.csdnimg.cn/direct/0748c76d27fd447db1c46cf43570ffac.png
2.3 选择排序
概念和原理:
选择排序:选择出当前序列中最小或者最大元素的所在的下标,再将最小元素和第一个位置交换(再将最大元素和最后一个位置交换),再找出剩下元素中最小或者最大元素的所在的下标,再将最小元素和第二个位置交换(再将最大元素和最后二个位置交换),以此类推
时间复杂度:O(n^2)
算法实现:
#定义选择排序算法
def select_sort(alist):
i = 0 #当前序列中的第一个元素
while i<len(alist)-1:
min_idex = i #min_idex最小元素所在的下标 一开始就把第一个元素当成最小的
j = i+1#使用j遍历当前序列中后面所有的元素
while j<len(alist):
if alist > alist: #alist < alist
min_idex = j
j+=1
if min_idex != i:
#将min_idex下标的元素放到第i位置上交互
alist,alist = alist,alist
i+=1 2.4 直接插入排序 (抓牌)
概念和原理:
1】定义:每次将待排序中的第一个元素,放入已排序列表中对应的位置
2】原理:每一步从待排序列中选取第一个元素,将其插入到之前已排序序列中,直到待排序列全部元素排完,则竣事排序
时间复杂度:O(n^2)
算法实现:
#定义直接插入排序算法
def insert_sort(alist):
i = 1 #记录待排序列中的第一个位置从第二个元素开始
while i < len(alist):
temp = alist
j = i
while temp < alist and j>0: #如果当前这个元素比前面的元素小
#前面的元素后移
alist = alist
j-=1
alist = temp #将当前要插入的位置 将值赋值进来
i+=1
li =
insert_sort(li)
print(li) 2.5 快速排序
概念和原理:
1】定义:快速排序是在序列元素与选定基准比力分割为大小两个部分的排序
基准(piovt)
2】原理:
1.从待排序列中,选定一个基准
2.以此为基准,将待排序列分为大小两个部分
3.对每个部分,再次选择一个基准,进行上述操作
4.直到每一个部分只有一个元素时,则排序乐成
时间复杂度:O(n^2)
算法实现:
#定义第一趟快排函数
def part(alist,L,R):
#定义基准
p = alist
while L<R:
while alist>=p and L<R:
R-=1
alist = alist #将比基准小的数据放在左边
while alist <= p and L<R:
L+=1
alist = alist #将比基准大的数据放在右边
#当L==R 说明只剩最后一个元素-->基准,L或者R就是基准所在的位置
alist = p
return L#基准所在的下标
#定义快排函数
def quick_sort(alist,L,R):
if L<R:
#进行第一次快排,
p_idex = part(alist,L,R)
#将基准左侧的序列再次进行快排
quick_sort(alist,L,p_idex-1)
#将基准右侧的序列再次进行快排
quick_sort(alist,p_idex+1,R)
li =
quick_sort(li,0,len(li)-1)
print(li) 2.6 希尔排序(相识)
概念和原理:
希尔排序是插入排序的一种,也称为缩小量排序。
原理:将序列在一个表中并对序列分别进行插入排序,重复过程,不外每次用更长的序列(步长更长了,列数更少了)
时间复杂度:O(n^2)
算法实现
https://i-blog.csdnimg.cn/direct/6c1a7ac225754da9be120e028bb8db47.png
#定义希尔排序算法
def shell_sort(alist):
#获取元素总个数
n=len(alist)
#设置初始步长
gap = n//2
while gap > 0:
#按步长进行插入
for i in range(gap,n):
j = i
while j>=gap and alist > alist:
alist,alist = alist,alist
j-=gap
#更新步长
gap = gap // 2
alist =
shell_sort(alist)
print(alist) 2.7 归并排序
概念和原理:
1】归并排序是采用分治法的一种典型的应用
2】归并排序的思想就是先递归分解序列,再归并序列
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
页:
[1]