def insertsort(r):  #插入排序
    for i in range(1,len(r)):
        for j in range(i,0,-1):
            if r[j-1]>r[j]:
                r[j-1],r[j]=r[j],r[j-1]
    return r
def selectsort(r):  #选择排序
    for i in range(len(r)-1):
        min=i
        for j in range(i+1,len(r)):
            if r[j]<r[min]:
                min=j
        if min !=i:
            r[i],r[min]=r[min],r[i]
    return r

def bubblesort(r):  #冒泡
    for i in  range(len(r)-1):
        exchange=False
        for j in range(len(r)-1,i,-1):
            if r[j-1]>r[j]:
                r[j-1],r[j]=r[j],r[j-1]
                exchange=True
        if exchange==False:
            return r
    return r

#测试
r=[9,8,7,6,56,4,3,2,1]
print(insertsort(r))
print(selectsort(r))
print(bubblesort(r))

#用栈逆置队列
from collections import deque
def reverseduqu(qu):
    st = deque()
    while len(qu) > 0:
        st.append(qu.popleft())
    while len(st) > 0:
        qu.append(st.pop())
    return qu
qu= deque()
for i in range(10):#模拟一个队列
    qu.append(i)
print(qu)
print(reverseduqu(qu))

from collections import deque
#十进制转二进制
def tentobin(num):
    st=deque()
    while num>0:
        st.append(num%2)
        num=num//2
    while len(st)>0:
        print(st.pop(),end=" ")

tentobin(127)
print()

#反转字符串
def reverseString(s):
    L=len(s)
    s=list(s)
    for i in range(L//2):
        s[i],s[L-i-1]=s[L-i-1],s[i]

    return ''.join(s)

s="asdfghjkl"
print(reverseString(s))

def BF(s,t):
    i,j=0,0
    while i<len(s) and j<len(t) :
        if s[i]==t[j]:
            i,j=i+1,j+1
        else:
            i,j=i-j+1,0
    if j>=len(t) :
        return (i-len(t) )
    else:
        return(-1)
    
print(BF("asdfg","sd"))