Python数据结构与算法学习第五天

1043-李同学

发表文章数:31

热门标签

首页 » 数据结构 » 正文

一.栈结构实现

栈可以用顺序表实现,也可以用链表实现。
栈的操作
1.Stack() 创建一个新的空栈
2.push(item) 添加一个新的元素item到栈顶
3.pop() 弹出栈顶元素
4.peek() 返回栈顶元素
5.is_empty() 判断栈是否为空
6.size() 返回栈的元素个数
代码实现: 利用顺序表
Python数据结构与算法学习第五天
上图代码为定义类。
Python数据结构与算法学习第五天
上图代码为操作与结果,栈是先进后出,所以先将1、2、3顺序压入栈中,最后弹出结果顺序为3、2、1。

二.队列的实现

同栈一样,队列也可以用顺序表或者链表实现。
队列的操作
1.Queue() 创建一个空的队列
2.enqueue(item) 往队列中添加一个item元素
3.dequeue() 从队列头部删除一个元素
4.is_empty() 判断一个队列是否为空
5.size() 返回队列的大小
代码实现: 利用顺序表实现
Python数据结构与算法学习第五天
上图为实现队列的代码,队列与栈不同,队列为先进先出,可以设想为右边进,左边出的模型。
Python数据结构与算法学习第五天
操作为先顺序添加1、2、3,当出队列时,则结果为1、2、3。

三.双端队列

双端队列(deque,全名double-ended queue),是一种具有队列和栈的性质的数据结构。
双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。Python数据结构与算法学习第五天
操作
Dequeue() 创建一个空的双端队列
enqueue_front(self,item)从队头加入一个item元素
enqueue_rear(self, item)从队尾加入一个item元素
delqueue_front(self)从队头删除一个item元素
delqueue_rear(self)从队尾删除一个item元素
is_empty() 判断双端队列是否为空
size() 返回队列的大小

代码实现
Python数据结构与算法学习第五天
双端队列可以从头部和尾部添加或者删除元素。

四.冒泡排序

冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的尾端。
冒泡排序算法的运作如下:
比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
代码实现:
Python数据结构与算法学习第五天
上图代码为实现冒泡排序的代码,首先定义冒泡排序函数,先测试序列长度n,外层循环的意思是需要进行n-1次的冒泡过程才能完成每个元素的排序,内层循环为当前i位置的元素与后一个位置的元素进行比较,若比后一个元素的位置大,则二者调换位置,n-1-j的意思为对比到n-1-j位置的元素,例如当j=0时,需要对比到n-2与n-1(最后一个元素),这时,最后一个元素已经为最大的元素,则下次循环无需再次与最后一个元素进行比较,这时j+1=1,下次循环只需要对比到倒数第二个元素即可。count的作用为计数,当内层循环一次后,发现没有进行位置调换操作,则说明列表本身就是有序序列,则可以直接退出循环,降低时间复杂度。

五.选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。
Python数据结构与算法学习第五天
上图为实现选择排序代码,先定义选择函数,在计算列表长度n,min_index表示当前的最小值。外层循环表示选择排序需要进行n次排序,同时也代表最小元素从第j开始排序。内层循环是从j后面的第一个元素开始比较,如果j比j后的第一个元素大,则将j后面的一个元素的位置给min_index,以此类推,直到最后一个元素,可以找到当前循环下的最小元素,然后再将j开始时的位置与找到内层循环中最小元素进行调换,再开始下一次外层循环。

六.插入排序

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
Python数据结构与算法学习第五天
上图为实现插入排序的代码,首先定义插入排序函数,再测试列表长度,首先先选择第一个元素为有序列表,则循环从第二个元素开始进行插入。内层循环为无序元素与有序元素进行比较,然后插入。例如当第二个元素与第一个元素进行比较时,若第二个比第一个小,则调换二者的位置,,否则插入后面,组成新的有序序列。下一次循环时,第三个元素首先与第二个比,若比第二个小,则调换位置,再与第一个比较,否则直接插入最后,组成新的有序列表。当i=0时,则表示插入完毕退出循环。

未经允许不得转载:作者:1043-李同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Python数据结构与算法学习第五天》 发布于2020-06-09

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录