栈与队列、冒泡排序、选择排序、插入排序

1588-刘同学

发表文章数:19

首页 » 数据结构 » 正文

栈,也称堆栈,是一种容器,可存入数据元素、访问元素、删除元素,特点是只允许在容器的一端进行加入数据和输出数据的运算,没有了位置概念,保证任何时候可以访问、删除的元素都是此前最后存入的那个元素,确定了一种默认的访问顺序。
由于栈数据结构只允许在一端进行操作,因而按照后进先出的原理运作。
栈与队列、冒泡排序、选择排序、插入排序

栈的功能代码实现

这里可以直接引用list顺序表的特点进行构建:

class Stack(object):
    """栈"""
    def __init__(self):
        self.__list = []

    def push(self, item):
        """添加一个新的元素item到栈顶"""
        self.__list.append(item)

    def pop(self):
        """弹出栈顶元素"""
        return self.__list.pop()

    def peek(self):
        """返回栈顶元素"""
        if self.__list:
            return self.__list[-1]
        else:
            return None

    def is_empty(self):
        """判断栈是否为空"""
        return self.__list == []
        # return not self.__list

    def size(self):
        """返回栈的元素个数"""
        return len(self.__list)

队列

队列只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
队列是一种先进先出的线性表。允许插入的一端为队尾,允许删除的一端为队头。队列不允许在中间部位进行操作。排在第一个的优先出列,最后来的排在队伍最后。
栈与队列、冒泡排序、选择排序、插入排序

队列的功能代码实现

队列可以使用顺序表的结构搭建

class Queue(object):
    """队列"""
    def __init__(self):
        self.__list = []

    def enqueue(self, item):
        """往队列中添加一个item元素"""
        self.__list.append(item)

    def dequeue(self):
        """从队列头部删除一个元素"""
        return self.__list.pop(0)

    def is_empty(self):
        """判断一个队列是否为空"""
        return self.__list == []

    def size(self):
        """返回队列的大小"""
        return len(self.__list)

双端队列

双端队列是一种具有队列和栈的性质的数据结构。双端队列的元素可以从两端弹出,其限定插入和删除操作在表的两端进行。双端队列可以在任意一端入队和出队。
栈与队列、冒泡排序、选择排序、插入排序
类似于两个栈底合在一起。

双端队列功能代码实现

class Deque(object):
    """双端队列"""
    def __init__(self):
        self.__list = []

    def add_front(self, item):
        """往队列中添加一个item元素"""
        self.__list.insert(0, item)

    def add_rear(self, item):
        """往队列中添加一个item元素"""
        self.__list.append(item)

    def pop_front(self):
        """从队列头部删除一个元素"""
        return self.__list.pop(0)

    def pop_rear(self):
        """从队列头部删除一个元素"""
        return self.__list.pop()

    def is_empty(self):
        """判断一个队列是否为空"""
        return self.__list == []

    def size(self):
        """返回队列的大小"""
        return len(self.__list)

排序与搜索

排序算法是一种将一串数据依照特定顺序进行排列的一种算法。

排序算法的稳定性

稳定排序算法会让原本有相等键值的记录维持相对次序。
假设对以下的数按第一个数字大小顺序排序:
(4,1)(3,1)(3,7)(5,6)
则会有两种结果:
(3,1)(3,7)(4,1)(5,6) ====>维持次序
(3,7)(3,1)(4,1)(5,6) ====>次序被改变
不稳定排序算法可能会在相等的键值中改变记录的相对次序,但是稳定排序算法不会如此。

冒泡排序

冒泡排序是一种简单地排序算法,它重复遍历要排序的数列,一次比较两个元素,如果顺序错误就把他们交换。遍历数列的工作是重复进行直到没有再需要交换,也就是排序完成。

冒泡排序算法:

1.比较相邻的元素,如果第一个比第二个大,就交换他们两个
2.对每一个相邻元素做同样的工作,从开始第一对到结尾的最后一对,最后的元素是最大的数
3.针对所有元素重复以上步骤,除了最后一个
4.持续步骤,直到没有数字需要比较

时间复杂度

·最优时间复杂度:O(n)(表示遍历一次发现没有任何可以交换的元素,排序结束)
·最坏时间复杂度:O(n2)
·稳定性:稳定

冒泡排序代码实现

def bubble_sort(alist):
    """冒泡排序"""
    n = len(alist)
    for j in range(n-1):
        count = 0
        for i in range(0, n-1-j):
            # 指针从头走到尾
            if alist[i] > alist[i+1]:
                alist[i],alist[i+1] = alist[i+1], alist[i]
                count += 1
        if 0 == count:    #第一次遍历发现已经是正序,直接结束遍历
            return

选择排序

首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列末尾,直到所有元素排序完毕。

时间复杂度

·最优时间复杂度:O(n2)
·最坏时间复杂度:O(n2)
·稳定性:不稳定

选择排序功能代码实现

def select_sort(alist):
    """选择排序"""
    n = len(alist)
    for j in range(n-1): # j: 0 ~ n-2
        min_index = j
        for i in range(j+1, n):
            if alist[min_index] > alist[i]:
                min_index = i
        alist[j], alist[min_index] = alist[min_index], alist[j]

插入排序

通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。在扫描过程中,需要反复把已排序元素逐步向后挪位,为新元素提供插入空间。

插入排序功能代码实现

def insert_sort(alist):
    """插入排序"""
    n = len(alist)
    # 从右边的无序序列中取出多少个元素执行这样的过程
    for j in range(1, n):
        # j = [1, 2, 3, n-1]
        # i 代表内层循环起始值
        i = j
        # 执行从右边的无序序列中取出第一个元素,即i位置的元素,然后将其插入到前面的正确位置中
        while i > 0:
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
                i -= 1
            else:
                break

时间复杂度

·最优时间复杂度:O(n)
·最坏时间复杂度:O(n2)
·稳定性:稳定

未经允许不得转载:作者:1588-刘同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《栈与队列、冒泡排序、选择排序、插入排序》 发布于2021-02-24

分享到:
赞(1) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录