python排序算法及优化学习笔记1

简介: python实现的简单的排序算法,以及算法优化,学习笔记1

1.排序算法

1.1冒泡排序

1.1.1算法描述(摘自网络)

原始算法:

1.        比较相邻的元素。如果第一个比第二个大,就交换它们两个;

2.        对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;

3.        针对所有的元素重复以上的步骤,除了最后一个;

4.        重复步骤1~3,直到排序完成。

算法优化:

每一轮步骤1~3排序结束后,如果没有进行排序操作,则表示整个数组已经满足了升序或者降序的顺序,不需要继续排序了,此时退出循环排序,节省时间。

1.1.2算法实现

输入:

Src:一个数组

Order0是降序,1是升序

Opt:默认为True,使用优化算法,False为原始排序算法

@time_count

def bubble(src: list, order=1, opt=True):    

   # src: list

   # order: 0 descend, 1 ascend

   # opt: True optimize, False not optimize

   # print(src)    

   dst = src.copy()

   step = 0

   for i in range(len(dst)-1, 0, -1):

       sorted = not opt

       for j in range(i):

           step += 1

           if (order and dst[j] > dst[j+1]) or (not order and dst[j] < dst[j+1]):

               temp = dst[j]

               dst[j] = dst[j+1]

               dst[j+1] = temp

               sorted = True

       if not sorted:

           print('no need to sort')

           break

   print('step', step)

   return dst

1.2选择排序

1.2.1算法描述(摘自网络)

原始算法:

1.        在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。

2.        从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

3.        重复第二步,直到所有元素均排序完毕。

算法优化:

1.        步骤1同时找出最大和最小值,找出的最大和最小值分别存放在各自的序列中,排序完成后输出两个序列的组合。

2.        如果最大值和最小值是同一个值,说明剩下的所有数据都是相同的,可直接退出排序。

1.2.2算法实现

原始算法:

@time_count

def select_origin(src: list, order=1):

   # src: list

   # order: 0 descend, 1 ascend

   # print(src)

   dst_temp = src.copy()

   dst = []

   while len(dst_temp):

       max_id = 0

       for i in range(1, len(dst_temp)):

           if dst_temp[i] > dst_temp[max_id]:

               max_id = i

       if order == 0:

           dst.append(dst_temp[max_id])

       else:

           dst.insert(0, dst_temp[max_id])

       dst_temp.pop(max_id)

   return dst

优化算法:

@time_count

def select_opt(src: list, order=1):

   # src: list

   # order: 0 descend, 1 ascend

   # print(src)

   dst_temp = src.copy()

   dst_min = []

   dst_max = []

   while len(dst_temp):

       max_id = 0

       min_id = 0

       for i in range(1, len(dst_temp)):

           if dst_temp[i] > dst_temp[max_id]:

               max_id = i

           if dst_temp[i] < dst_temp[min_id]:

               min_id = i

       if max_id == min_id:

           if order == 0:

               dst_max += dst_temp

           else:

               dst_max = dst_temp + dst_max

           break

       if order == 0:

           dst_max.append(dst_temp[max_id])

           dst_min.insert(0,dst_temp[min_id])

       else:

           dst_max.insert(0, dst_temp[max_id])

           dst_min.append(dst_temp[min_id])

       if max_id > min_id:

           dst_temp.pop(max_id)

           dst_temp.pop(min_id)

       elif max_id < min_id:

           dst_temp.pop(min_id)

           dst_temp.pop(max_id)

       else:

           dst_temp.pop(min_id)

   if order == 0:

       return dst_max + dst_min

   else:

       return dst_min + dst_max

1.3插入排序

1.3.1算法描述(摘自网络)

原始算法:

1.        把待排序的数组分成已排序和未排序两部分,初始的时候把第一个元素认为是已排好序的。

2.        从第二个元素开始,在已排好序的子数组中寻找到该元素合适的位置并插入该位置。

3.        重复上述过程直到最后一个元素被插入有序子数组中。

算法优化1

在步骤2中,计算待插入的值靠近序列的开头还是末尾,靠近哪一侧,就从该侧寻找位置插入,减少循环查找的次数。

算法优化2

在步骤2中,计算待插入的值靠近序列的开头、中间还是末尾,,靠近哪一侧,就从该侧寻找位置插入,进一步减少循环查找的次数。

1.3.2算法实现

原始算法:

@time_count

def insert_origin(src: list, order=1):

   # src: list

   # order: 0 descend, 1 ascend

   # print(src)

   dst = src[0:1]

   for i in range(1, len(src)):

       inserted = False

       for j in range(len(dst)):

           if (order and src[i] < dst[j]) or (not order and src[i] > dst[j]):

               dst.insert(j, src[i])

               inserted = True

               break

       if not inserted:

           dst.append(src[i])

   return dst

优化算法1

@time_count

def insert_opt1(src: list, order=1):

   # src: list

   # order: 0 descend, 1 ascend

   # print(src)

   dst = src[0:1]

   for i in range(1, len(src)):

       inserted = False

       if abs(src[i]-dst[0]) <= abs(src[i]-dst[-1]):

           for j in range(len(dst)):

               if (order and src[i] < dst[j]) or (not order and src[i] > dst[j]):

                   dst.insert(j, src[i])

                   inserted = True

                   break

           if not inserted:

               dst.append(src[i])

       else:

           for j in range(len(dst)-1,-1,-1):

               if (order and src[i] > dst[j]) or (not order and src[i] < dst[j]):

                   dst.insert(j+1, src[i])

                   inserted = True

                   break

           if not inserted:

               dst.insert(0,src[i])

   return dst

优化算法2

@time_count

def insert_opt2(src: list, order=1):

   # src: list

   # order: 0 descend, 1 ascend

   # print(src)

   dst = src[0:1]

   def insert_left(src_vlaue, from_mid=False):

       inserted = False

       start = 0 if not from_mid else int(len(dst)/2)

       for j in range(start, len(dst)):

           if (order and src_vlaue < dst[j]) or (not order and src_vlaue > dst[j]):

               dst.insert(j, src_vlaue)

               inserted = True

               break

       if not inserted:

           dst.append(src_vlaue)

   def insert_right(src_vlaue, from_mid=False):

       inserted = False

       start = len(dst)-1 if not from_mid else int(len(dst)/2)

       for j in range(start,-1,-1):

           if (order and src_vlaue > dst[j]) or (not order and src_vlaue < dst[j]):

               dst.insert(j+1, src_vlaue)

               inserted = True

               break

       if not inserted:

           dst.insert(0, src_vlaue)

   for i in range(1, len(src)):            

       l = abs(src[i]-dst[0])

       r = abs(src[i]-dst[-1])      

       m = src[i]-dst[int(len(dst)/2)]            

       if l <= abs(m) and l <= r:

           insert_left(src[i])

       elif r <= abs(m) and r <= l:

           insert_right(src[i])

       else:

           if m >= 0:

               insert_left(src[i], True)

           else:

               insert_right(src[i], True)

   return dst

2.算法比较

2.1算法有效性

为证明算法能有效进行排序,使用的数组为:

data0 = [0, 7, 7, -2, 1, -7, 7, 7, 6, -2, 0, 10, 9, 9, 4, 2, 6, 5, 1, 8, 3, 1, 10, 7, -1]

分别使用各个算法进行升序和降序。

1)冒泡排序:

>>> bubble(data0)

no need to sort

step 297

cost 1

[-7, -2, -2, -1, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10]

>>> bubble(data0, 0)

no need to sort

step 297

cost 1

[10, 10, 9, 9, 8, 7, 7, 7, 7, 7, 6, 6, 5, 4, 3, 2, 1, 1, 1, 0, 0, -1, -2, -2, -7]

>>> bubble(data0,opt=False)

step 300

cost 2

[-7, -2, -2, -1, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10]

>>> bubble(data0, 0, opt=False)

step 300

cost 2

[10, 10, 9, 9, 8, 7, 7, 7, 7, 7, 6, 6, 5, 4, 3, 2, 1, 1, 1, 0, 0, -1, -2, -2, -7]

2)选择排序

>>> select_opt(data0)

cost 0

[-7, -2, -2, -1, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10]

>>> select_opt(data0,0)

cost 0

[10, 10, 9, 9, 8, 7, 7, 7, 7, 7, 6, 6, 5, 4, 3, 2, 1, 1, 1, 0, 0, -1, -2, -2, -7]

>>> select_origin(data0)

cost 0

[-7, -2, -2, -1, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10]

>>> select_origin(data0,0)

cost 0

[10, 10, 9, 9, 8, 7, 7, 7, 7, 7, 6, 6, 5, 4, 3, 2, 1, 1, 1, 0, 0, -1, -2, -2, -7]

>>>

3)插入排序

>>> insert_opt1(data0)

cost 0

[-7, -2, -2, -1, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10]

>>> insert_opt1(data0, 0)

cost 0

[10, 10, 9, 9, 8, 7, 7, 7, 7, 7, 6, 6, 5, 4, 3, 2, 1, 1, 1, 0, 0, -1, -2, -2, -7]

>>> insert_origin(data0)

cost 0

[-7, -2, -2, -1, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10]

>>> insert_origin(data0, 0)

cost 0

[10, 10, 9, 9, 8, 7, 7, 7, 7, 7, 6, 6, 5, 4, 3, 2, 1, 1, 1, 0, 0, -1, -2, -2, -7]

>>> insert_opt2(data0)

cost 0

[-7, -2, -2, -1, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 9, 9, 10, 10]

>>> insert_opt2(data0, 0)

cost 0

[10, 10, 9, 9, 8, 7, 7, 7, 7, 6, 6, 7, 5, 1, 3, 1, 2, 4, 1, 0, 0, -1, -2, -2, -7]

>>>

2.2算法比较

使用三组数据比较各个算法的计算时长。

数组1长度为1万,其数值为0~100的随机数。

数组2长度为10万,其数值为0~100的随机数。

数组3长度为1万,其数值前50000~100的随机数,后5000为升序的值。

import random

import datetime

 

data1 = [random.randint(-100,100) for i in range(10000)]

data2 = [random.randint(-100,100) for i in range(100000)]

data3 = [random.randint(-100,100) for i in range(5000)] + [i for i in range(5000)]

使用datetime计算算法执行的时长。

def time_count(func):

   def wrapper(*args, **kwargs):

       start = datetime.datetime.now()

       result = func(*args, **kwargs)

       print('cost', int((datetime.datetime.now() - start).total_seconds()*1000))

       return result

   return wrapper

每个算法,对同一组数据,计算5次升序,取平均值,单位是ms,结果如下:

算法

冒泡排序

选择排序

插入排序

原始

优化

提升

原始

优化

提升

原始

优化1

优化2

提升1

提升2

数据11w

降序

11998

11976

0.19%

3498

3146

10.08%

2323

1178

281

49.28%

87.89%

升序

11760

11765

-0.05%

3517

3143

10.63%

2278

1169

527

48.66%

76.84%

数据210w

降序

1263493

1263487

0.00%

351886

316437

10.07%

230149

119339

28089

48.15%

87.80%

升序

1251652

1251670

0.00%

354900

315789

11.02%

234406

118856

53412

49.29%

77.21%

数据31w

降序

15113

15112

0.01%

3671

3209

12.58%

593

324

91

45.38%

84.65%

升序

8693

6665

23.32%

3688

3203

13.14%

3917

308

145

92.15%

96.30%

备注:提升=(原始-优化)/原始*100%

1.png

1 数据1降序排序各算法耗时

2.png

2 数据1升序排序各算法耗时

结论:

1、原始算法排序效率:插入排序>选择排序>冒泡排序。

2、冒泡排序,对于乱序的数据1和数据2,优化算法与原始算法用时接近,无优化效果,对特殊顺序的数组3,升序的优化算法有明显的提升,降序也无优化效果。

3、选择排序和插入排序的优化算法对各组数据均能生效。

4、选择排序的优化算法对各组数据的均提升约10%

5、插入排序的优化效果相比于其他两个算法的优化效果提升最大。

6、插入排序的效率:优化算法2>优化算法1>原始算法。

说明:以上实验并未严格控制测试环境,数据仅供参考。

 

目录
相关文章
|
4天前
|
存储 监控 NoSQL
Redis处理大量数据主要依赖于其内存存储结构、高效的数据结构和算法,以及一系列的优化策略
【5月更文挑战第15天】Redis处理大量数据依赖内存存储、高效数据结构和优化策略。选择合适的数据结构、利用批量操作减少网络开销、控制批量大小、使用Redis Cluster进行分布式存储、优化内存使用及监控调优是关键。通过这些方法,Redis能有效处理大量数据并保持高性能。
22 0
|
4天前
|
分布式计算 Python
Python函数式编程学习笔记
高阶函数是能接收另一个函数作为参数的函数,如Python的map()、reduce()和filter()。map()将传入的函数应用到序列每个元素并返回迭代器,如将整数列表转换为字符串列表。reduce()对序列进行累积计算,例如求和。filter()根据给定函数返回的真值保留或丢弃序列元素,常用于筛选。sorted()函数支持自定义排序,如按绝对值或ASCII值排序。此外,还包括返回函数、匿名函数(lambda)、装饰器(用于动态增强函数功能)和偏函数(partial),用于固定函数部分参数,简化调用。
9 1
|
2天前
|
算法
MATLAB|【免费】融合正余弦和柯西变异的麻雀优化算法SCSSA-CNN-BiLSTM双向长短期记忆网络预测模型
这段内容介绍了一个使用改进的麻雀搜索算法优化CNN-BiLSTM模型进行多输入单输出预测的程序。程序通过融合正余弦和柯西变异提升算法性能,主要优化学习率、正则化参数及BiLSTM的隐层神经元数量。它利用一段简单的风速数据进行演示,对比了改进算法与粒子群、灰狼算法的优化效果。代码包括数据导入、预处理和模型构建部分,并展示了优化前后的效果。建议使用高版本MATLAB运行。
|
4天前
|
数据采集 数据可视化 数据挖掘
利用Python和Pandas库优化数据分析流程
在当今数据驱动的时代,数据分析已成为企业和个人决策的重要依据。Python作为一种强大且易于上手的编程语言,配合Pandas这一功能丰富的数据处理库,极大地简化了数据分析的流程。本文将探讨如何利用Python和Pandas库进行高效的数据清洗、转换、聚合以及可视化,从而优化数据分析的流程,提高数据分析的效率和准确性。
|
4天前
|
SQL 数据采集 数据挖掘
构建高效的Python数据处理流水线:使用Pandas和NumPy优化数据分析任务
在数据科学和分析领域,Python一直是最受欢迎的编程语言之一。本文将介绍如何通过使用Pandas和NumPy库构建高效的数据处理流水线,从而加速数据分析任务的执行。我们将讨论如何优化数据加载、清洗、转换和分析的过程,以及如何利用这些库中的强大功能来提高代码的性能和可维护性。
|
4天前
|
算法 搜索推荐 C语言
Python实现数据结构与算法
【5月更文挑战第13天】学习数据结构与算法能提升编程能力,解决复杂问题,助你面试成功。从选择资源(如《算法导论》、Coursera课程、LeetCode)到实践编码,逐步学习基本概念,通过Python实现栈、队列和快速排序。不断练习、理解原理,探索高级数据结构与算法,参与开源项目和算法竞赛,持续反思与实践,以提升技术能力。
6 0
|
4天前
|
机器学习/深度学习 算法 数据可视化
Python 数据结构和算法实用指南(四)(4)
Python 数据结构和算法实用指南(四)
10 1
|
4天前
|
机器学习/深度学习 存储 算法
Python 数据结构和算法实用指南(四)(3)
Python 数据结构和算法实用指南(四)
14 1
|
4天前
|
存储 算法 搜索推荐
Python 数据结构和算法实用指南(四)(2)
Python 数据结构和算法实用指南(四)
10 0
|
4天前
|
存储 算法 Serverless
Python 数据结构和算法实用指南(四)(1)
Python 数据结构和算法实用指南(四)
14 0