文章目录

• 一、栈与队列
• • 1. 栈
  • 2. 队列
  • • (1). 队列的实现
    • (2). 双端队列
• 二、 排序
• • 1. 冒泡排序
  • 2. 选择排序
  • 3. 插入排序

一、栈与队列

1. 栈

• 栈的操作
  Stack() 创建一个新的空栈
  push(item) 添加一个新的元素item到栈顶
  pop() 弹出栈顶元素
  peek() 返回栈顶元素
  is_empty() 判断栈是否为空
  size() 返回栈的元素个数

#coding=utf-8

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==[]

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



if __name__=='__main__':
    s=Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    print(s.size())
    print(s.pop())
    print(s.pop())
    print(s.size())
    print(s.pop())
    print(s.pop())

运行结果:
4
4
3
2
2
1

2. 队列

(1). 队列的实现

• 队列操作
  Queue() 创建一个空的队列
  enqueue(item) 往队列中添加一个item元素
  dequeue() 从队列头部删除一个元素
  is_empty() 判断一个队列是否为空
  size() 返回队列的大小

#coding=utf-8

class Queue():
    '''队列'''
    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)


if __name__=='__main__':
    q=Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    print(q.size())
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())
    print(q.dequeue())

运行结果:
4
1
2
3
4

(2). 双端队列

• Deque() 创建一个空的双端队列
  add_front(item) 从队头加入一个item元素
  add_rear(item) 从队尾加入一个item元素
  remove_front() 从队头删除一个item元素
  remove_rear() 从队尾删除一个item元素
  is_empty() 判断双端队列是否为空
  size() 返回队列的大小

#coding=utf-8

class Dqueue():
    '''双端队列'''

    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)
if __name__=='__main__':
    d=Dqueue()
    d.add_front(23)
    d.add_rear(10)
    d.add_front(50)
    d.add_rear(2)
    print(d.pop_front())
    print(d.pop_front())
    print(d.pop_front())
    print(d.pop_rear())

运行结果:
50
23
10
2

二、 排序

1. 冒泡排序

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

#coding=utf-8
#冒泡排序
def bubble_sort(alist):
    '''冒泡排序'''
    for j in range(len(alist)-1):
        count=0
        for i in range(0,len(alist)-1-j): #左闭右开 要走到倒数第二个位置
            #从头走到尾
            if alist[i]>alist[i+1]:
                count+=1
                alist[i],alist[i+1]=alist[i+1],alist[i]

            if count==0:   #哪次过程没有交换了，直接退出
                return
# i 0>>n-2  range(0,n-1)  j=0
# i 0>>n-3  range(0,n-1-1)  j=1
# i 0>>n-4  range(0,n-1-2)  j=2
# :
# :
# :
# i 0>>n-n+1  range(0,n-n+2) j=n-2
if __name__=='__main__':
    li=[14,12,5,1,9,3,6,7,8]
    print(li)
    bubble_sort(li)
    print(li)

运行结果:
[14, 12, 5, 1, 9, 3, 6, 7, 8]
[1, 5, 3, 6, 7, 8, 9, 12, 14]

2. 选择排序

• 时间复杂度
  最优时间复杂度：O(n2)
  最坏时间复杂度：O(n2)
  稳定性：不稳定（考虑升序每次选择最大的情况）

#coding=utf-8
#选择排序
# alist=[54,336,93,17,77,31,44,55,20]
def select_sort(alist):
    '''选择排序'''
    n=len(alist)
    for i in range(n-1):
        mix=alist[i]
        for j in range(i+1,n):
            if alist[j]<mix:
                mix=alist[j]
                k=j
        alist[i],alist[k]=alist[k],alist[i]
        k=i+1

if __name__=='__main__':
    alist=[54,336,93,17,77,31,44,55,20]
    print(alist)
    select_sort(alist)
    print(alist)

运行结果:
[54, 336, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 31, 44, 54, 55, 77, 93, 336]

3. 插入排序

• 时间复杂度
  最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
  最坏时间复杂度：O(n2)
  稳定性：稳定

#coding=utf-8
#插入排序

def insert_sort(alist):
    '''插入排序'''
    n=len(alist)
    for j in range(1,n):
        i=j
        while i>0:
            if alist[i]<alist[i-1]:
                alist[i],alist[i-1]=alist[i-1],alist[i]
                i = i - 1
            else:
                break

if __name__ == '__main__':
        alist = [54, 336, 93, 17, 77, 31, 44, 55, 20]
        print(alist)
        insert_sort(alist)
        print(alist)

运行结果:
[54, 336, 93, 17, 77, 31, 44, 55, 20]
[17, 20, 31, 44, 54, 55, 77, 93, 336]