文档章节

Python十大经典排序算法

o
 osc_nhwfplmt
发布于 2019/10/02 02:26
字数 2911
阅读 5
收藏 0
def

行业解决方案、产品招募中!想赚钱就来传!>>>

现在很多的事情都可以用算法来解决,在编程上,算法有着很重要的地位,将算法用函数封装起来,使程序能更好的调用,不需要反复编写。

Python十大经典算法:

 

一、插入排序

1.算法思想

从第二个元素开始和前面的元素进行比较,如果前面的元素比当前元素大,则将前面元素 后移,当前元素依次往前,直到找到比它小或等于它的元素插入在其后面,

然后选择第三个元素,重复上述操作,进行插入,依次选择到最后一个元素,插入后即完成所有排序。

2.代码实现

 1 def insertion_sort(arr):
 2     #插入排序
 3     # 第一层for表示循环插入的遍数
 4     for i in range(1, len(arr)):
 5         # 设置当前需要插入的元素
 6         current = arr[i]
 7         # 与当前元素比较的比较元素
 8         pre_index = i - 1
 9         while pre_index >= 0 and arr[pre_index] > current:
10             # 当比较元素大于当前元素则把比较元素后移
11             arr[pre_index + 1] = arr[pre_index]
12             # 往前选择下一个比较元素
13             pre_index -= 1
14         # 当比较元素小于当前元素,则将当前元素插入在 其后面
15         arr[pre_index + 1] = current
16     return arr

二、选择排序

1.算法思想

设第一个元素为比较元素,依次和后面的元素比较,比较完所有元素找到最小的元素,将它和第一个元素互换,重复上述操作,我们找出第二小的元素和第二个位置的元素互换,以此类推找出剩余最小元素将它换到前面,即完成排序。

2.代码实现

 1 def selection_sort(arr):
 2     #选择排序
 3     # 第一层for表示循环选择的遍数
 4     for i in range(len(arr) - 1):
 5         # 将起始元素设为最小元素
 6         min_index = i
 7         # 第二层for表示最小元素和后面的元素逐个比较
 8         for j in range(i + 1, len(arr)):
 9             if arr[j] < arr[min_index]:
10                 # 如果当前元素比最小元素小,则把当前元素角标记为最小元素角标
11                 min_index = j
12         # 查找一遍后将最小元素与起始元素互换
13         arr[min_index], arr[i] = arr[i], arr[min_index]
14     return arr

 

三、冒泡排序

1.算法思想

从第一个和第二个开始比较,如果第一个比第二个大,则交换位置,然后比较第二个和第三个,逐渐往后,经过第一轮后最大的元素已经排在最后,

所以重复上述操作的话第二大的则会排在倒数第二的位置。,那重复上述操作n-1次即可完成排序,因为最后一次只有一个元素所以不需要比较。

2.代码实现

 1 def bubble_sort(arr):
 2     #冒泡排序
 3     # 第一层for表示循环的遍数
 4     for i in range(len(arr) - 1):
 5         # 第二层for表示具体比较哪两个元素
 6         for j in range(len(arr) - 1 - i):
 7             if arr[j] > arr[j + 1]:
 8                 # 如果前面的大于后面的,则交换这两个元素的位置
 9                 arr[j], arr[j + 1] = arr[j + 1], arr[j]
10     return arr

 

四、快速排序

1.算法思想

找出基线条件,这种条件必须尽可能简单,不断将问题分解(或者说缩小规模),直到符合基线条件。

2.代码实现

 1 def quick_sort(arr):
 2   if len(arr) < 2:
 3     # 基线条件:为空或只包含一个元素的数组是“有序”的
 4     return arr
 5   else:
 6     # 递归条件
 7     pivot = arr[0]
 8     # 由所有小于基准值的元素组成的子数组
 9     less = [i for i in arr[1:] if i <= pivot]
10     # 由所有大于基准值的元素组成的子数组
11     greater = [i for i in array[1:] if i > pivot]
12     return quicksort(less) + [pivot] + quicksort(greater)
13 
14 print(quick_sort([10, 5, 2, 3]))

 

五、归并排序

1.算法思想

归并排序是分治法的典型应用。分治法(Divide-and-Conquer):将原问题划分成 n 个规模较小而结构与原问题相似的子问题;递归地解决这些问题,然后再合并其结果,就得到原问题的解,分解后的数列很像一个二叉树。

具体实现步骤:

  1. 使用递归将源数列使用二分法分成多个子列

  2. 申请空间将两个子列排序合并然后返回

  3. 将所有子列一步一步合并最后完成排序

  4. 注:先分解再归并

2.代码实现

 1 def merge_sort(arr):
 2     #归并排序
 3     if len(arr) == 1:
 4         return arr
 5     # 使用二分法将数列分两个
 6     mid = len(arr) // 2
 7     left = arr[:mid]
 8     right = arr[mid:]
 9     # 使用递归运算
10     return marge(merge_sort(left), merge_sort(right))
11 
12 
13 def marge(left, right):
14     #排序合并两个数列
15     result = []
16     # 两个数列都有值
17     while len(left) > 0 and len(right) > 0:
18         # 左右两个数列第一个最小放前面
19         if left[0] <= right[0]:
20             result.append(left.pop(0))
21         else:
22             result.append(right.pop(0))
23     # 只有一个数列中还有值,直接添加
24     result += left
25     result += right
26     return result

六、希尔排序

1.算法思想

希尔排序的整体思想是将固定间隔的几个元素之间排序,然后再缩小这个间隔。这样到最后数列就成为了基本有序数列。

具体步骤:

  1. 计算一个增量(间隔)值

  2. 对元素进行增量元素进行比较,比如增量值为7,那么就对0,7,14,21…个元素进行插入排序

  3. 然后对1,8,15…进行排序,依次递增进行排序

  4. 所有元素排序完后,缩小增量比如为3,然后又重复上述第2,3步

  5. 最后缩小增量至1时,数列已经基本有序,最后一遍普通插入即可

2.代码实现

 1 def shell_sort(arr):
 2     #希尔排序
 3     # 取整计算增量(间隔)值
 4     gap = len(arr) // 2
 5     while gap > 0:
 6         # 从增量值开始遍历比较
 7         for i in range(gap, len(arr)):
 8             j = i
 9             current = arr[i]
10             # 元素与他同列的前面的每个元素比较,如果比前面的小则互换
11             while j - gap >= 0 and current < arr[j - gap]:
12                 arr[j] = arr[j - gap]
13                 j -= gap
14             arr[j] = current
15         # 缩小增量(间隔)值
16         gap //= 2
17     return arr

七、基数排序

1.算法思想

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

2.代码实现

2.1由桶排序改造,从最低位到最高位依次桶排序,最后输出最后排好的列表。

 1 def RadixSort(list,d):
 2     for k in range(d):#d轮排序
 3         # 每一轮生成10个列表
 4         s=[[] for i in range(10)]#因为每一位数字都是0~9,故建立10个桶
 5         for i in list:
 6             # 按第k位放入到桶中
 7             s[i//(10**k)%10].append(i)
 8         # 按当前桶的顺序重排列表
 9         list=[j for i in s for j in i]
10     return list

2.2简单实现

 1 from random import randint
 2 def radix_sort():
 3   A = [randint(1, 99999999) for _ in xrange(9999)]
 4   for k in xrange(8):
 5     S = [ [] for _ in xrange(10)]
 6     for j in A:
 7       S[j / (10 ** k) % 10].append(j)
 8     A = [a for b in S for a in b]
 9   for i in A:
10     print i

八、计数排序

1.算法思想

对每一个输入元素x,确定小于x的元素个数。利用这一信息,就可以直接把x 放在它在输出数组上的位置上了,运行时间为O(n),但其需要的空间不一定,空间浪费大。

2.代码实现

 1 from numpy.random import randint
 2 def Conuting_Sort(A):
 3     k = max(A)          # A的最大值,用于确定C的长度
 4     C = [0]*(k+1)       # 通过下表索引,临时存放A的数据
 5     B = (len(A))*[0]    # 存放A排序完成后的数组
 6     for i in range(0, len(A)):
 7         C[A[i]] += 1    # 记录A有哪些数字,值为A[i]的共有几个
 8     for i in range(1, k+1):
 9         C[i] += C[i-1]  # A中小于i的数字个数为C[i]
10     for i in range(len(A)-1, -1, -1):
11         B[C[A[i]]-1] = A[i] # C[A[i]]的值即为A[i]的值在A中的次序
12         C[A[i]] -= 1    # 每插入一个A[i],则C[A[i]]减一
13     return B

九、堆排序

1.算法思想

堆分为最大堆和最小堆,是完全二叉树。堆排序就是把堆顶的最大数取出,将剩余的堆继续调整为最大堆,具体过程在第二块有介绍,以递归实现 ,

剩余部分调整为最大堆后,再次将堆顶的最大数取出,再将剩余部分调整为最大堆,这个过程持续到剩余数只有一个时结束。

2.代码实现

 1 import time,random
 2 def sift_down(arr, node, end):
 3     root = node
 4     #print(root,2*root+1,end)
 5     while True:
 6         # 从root开始对最大堆调整
 7         child = 2 * root +1  #left child
 8         if child  > end:
 9             #print('break',)
10             break
11         print("v:",root,arr[root],child,arr[child])
12         print(arr)
13         # 找出两个child中交大的一个
14         if child + 1 <= end and arr[child] < arr[child + 1]: #如果左边小于右边
15             child += 1 #设置右边为大
16         if arr[root] < arr[child]:
17             # 最大堆小于较大的child, 交换顺序
18             tmp = arr[root]
19             arr[root] = arr[child]
20             arr[child]= tmp
21             # 正在调整的节点设置为root
22             #print("less1:", arr[root],arr[child],root,child)
23             root = child #
24             #[3, 4, 7, 8, 9, 11, 13, 15, 16, 21, 22, 29]
25             #print("less2:", arr[root],arr[child],root,child)
26         else:
27             # 无需调整的时候, 退出
28             break
29     #print(arr)
30     print('-------------')
31  
32 def heap_sort(arr):
33     # 从最后一个有子节点的孩子还是调整最大堆
34     first = len(arr) // 2 -1
35     for i in range(first, -1, -1):
36         sift_down(arr, i, len(arr) - 1)
37     #[29, 22, 16, 9, 15, 21, 3, 13, 8, 7, 4, 11]
38     print('--------end---',arr)
39     # 将最大的放到堆的最后一个, 堆-1, 继续调整排序
40     for end in range(len(arr) -1, 0, -1):
41         arr[0], arr[end] = arr[end], arr[0]
42         sift_down(arr, 0, end - 1)
43         #print(arr)

十、桶排序

1.算法思想

为了节省空间和时间,我们需要指定要排序的数据中最小以及最大的数字的值,来方便桶排序算法的运算。

2.代码实现

 1 #桶排序
 2 def bucket_sort(the_list):
 3     #设置全为0的数组
 4     all_list = [0 for i in range(100)]
 5     last_list = []
 6     for v in the_list:
 7         all_list[v] = 1 if all_list[v]==0 else all_list[v]+1
 8     for i,t_v in enumerate(all_list):
 9         if t_v != 0:
10             for j in range(t_v):
11                 last_list.append(i)
12     return last_list

 总结:

在编程中,算法都是相通的,算法重在算法思想,相当于将一道数学上的应用题的每个条件,区间,可能出现的结果进行分解,分步骤的实现它。算法就是将具体问题的共性抽象出来,将步骤用编程语言来实现。通过这次对排序算法的整理,加深了对各算法的了解,具体的代码是无法记忆的,通过对算法思想的理解,根据伪代码来实现具体算法的编程,才是真正了解算法。

o
粉丝 1
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Python开发者社区整站源码--Pythoner

pythoner.net 整站源代码 依赖模块 Django 1.4.2 PIL DjangoVerifyCode 0.2.2 开发环境配置 运行scripts目录下的setupenv.sh文件,将会自动安装配置所需环境 设置本地环境变量:export env=D...

~T.y~
2013/04/10
3.2K
0
Python数据分析工具包--Pandas

Python Data Analysis Library 或 pandas 是连接 SciPy 和 NumPy 的一种工具,该工具是为了解决数据分析任务而创建的。Pandas 纳入了大量库和一些标准的数据模型,提供了高效地操作大型数据集...

匿名
2012/10/30
2.1W
2
Python-tesseract

Python-tesseract 是 Tesseract OCR 的 Python 封装包,可作常用的图片文件读取和解码。 示例代码: import cv2.cv as cv import tesseract api = tesseract.TessBaseAPI() api.Init(".","e......

李三石
2012/11/08
6.2K
0
开源物理项目--OSP

OSP (OpenSource Physics)开源物理项目是一个完整的 Java 应用套件用来模拟不同的物理系统,覆盖天文学、电磁学、经典力学、量子力学、光学和相对论。 下载后只需要简单运行 java -jar file...

匿名
2013/04/23
1.8K
0
纯Python图形GUI库--PyQtGraph

pyqtgraph 是纯 Python 图形 GUI 库,基于PyQT4 /pyside和NumPy。它主要目的用于在数学/科学/工程中。MIT的开源许可下发布。 主要特点: 基本的2D交互视图中框绘制 线和散点图 数据可平移/缩...

匿名
2013/05/16
9.6K
0

没有更多内容

加载失败,请刷新页面

加载更多

数据库—从注入到提权的全家桶套餐

这是 酒仙桥六号部队 的第 55 篇文章。 全文共计5397个字,预计阅读时长17分钟。 前言 偶然看到了最新的数据库流行度排名,发现在前5名的关系型数据库中,日常渗透测试见到最多的便是MySQL,...

一名白帽的成长史
前天
0
0
Linux安装 jdk tomcat mysql

安装 jdk # 华为云镜像jdk下载:https://repo.huaweicloud.com/java/jdk/# 1. 上传jdk解压至 /usr/local# 2. vim /etc/profile export JAVA_HOME=/usr/local/jdk export PATH=......

codeccb
4分钟前
0
0
「MoreThanJava」Day 5:面向对象进阶-继承详解

「MoreThanJava」 宣扬的是 「学习,不止 CODE」,本系列 Java 基础教程是自己在结合各方面的知识之后,对 Java 基础的一个总回顾,旨在 「帮助新朋友快速高质量的学习」。 当然 不论新老朋友...

我没有三颗心脏
前天
0
0
了解 JS 压缩图片,这一篇就够了

△ 是新朋友吗?记得先点web前端学习圈关注我哦~ 前言 公司的移动端业务需要在用户上传图片是由前端压缩图片大小,再上传到服务器,这样可以减少移动端上行流量,减少用户上传等待时长,优化...

web前端学习圈
今天
0
0
int32的最大值是多少? - What is the maximum value for an int32?

问题: I can never remember the number. 我永远记不住这个数字。 I need a memory rule. 我需要一个记忆规则。 解决方案: 参考一: https://stackoom.com/question/Obf/int-的最大值是多少...

javail
7分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部