那些年我刷过的题

一、迭代器

两种方法：
方法1:

list1=[1,2,3,4]
string2='abcd'
ite1=iter(list1)
ite2=iter(string2)

#两种输出方式
print(next(ite1),end=' ')
print(next(ite1),end=' ')
print(next(ite1),end=' ')
print(next(ite1))

for x in ite2:
    print(x,end=' ')

方法2:

class MyNumbers:
  def __iter__(self):
    self.a = 1
    return self   #返回一个特殊的迭代器对象
    #这个迭代器对象实现了 __next__() 方法并通过 StopIteration 异常标识迭代的完成。
 
  def __next__(self):
    
    if self.a <= 5:
      x = self.a
      self.a += 1
      return x   #返回下一个迭代器对象。
    else:
      raise StopIteration  #在 5 次迭代后停止执行：
 
myclass = MyNumbers()
myiter = iter(myclass)
 
for x in myiter:
  print(x)

二、生成器 generator

方法1:把列表[]改为()就行了

方法2:利用yield函数

yield相当于 return 返回一个值，并且记住这个返回的位置，下次迭代时，代码从yield的下一条语句开始执行。

#斐波那契数列
#非常简单的递归数列，除第一个和第二个数外，任意一个数都可由前两个数相加得到
#1 1 2 3 5
def fab(max):
    n,a,b=0,0,1   #第一个数为b=1
    while n<max:
        yield b   #首先输出1
        a,b=b,a+b  #执行完后，a在b的前面1个
        n=n+1
fab(5)
[x for x in fab(5)]  

简单地讲，yield 的作用就是把一个函数变成一个 generator，带有 yield 的函数不再是一个普通函数，Python解释器会将其视为一个 generator，调用 fab(5) 不会执行 fab 函数，而是返回一个 iterable 对象！

在 for循环执行时，每次循环都会执行 fab 函数内部的代码，执行到 yield b 时，fab 函数就返回一个迭代值，下次迭代时，代码从 yield b的下一条语句继续执行，而函数的本地变量看起来和上次中断执行前是完全一样的，于是函数继续执行，直到再次遇到 yield。

三、排序

稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
时间复杂度都为o(n^2)、空间复杂度都为o(1)（原地排序算法）的三个算法：

算法1:冒泡算法

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

def bubble(nums):
    length=len(nums)
    n=1
   
    while n<=length:
        flag=0
        for i in range(length-n):
            if nums[i]>nums[i+1]: #如果前一个比后一个大，就交换位置
                nums[i],nums[i+1]=nums[i+1],nums[i]  
                flag+=1   # 有变动就标记加1
                
            else:
                flag+=0   
        if flag==0:   #没有变动就退出while
            break
        n=n+1
        print(nums)        
    return nums

冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。

因为只有大于时才交换位置，所以数字相同的是不换位置的，所以是稳定排序算法。

算法2:插入排序

首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

def insertion(nums):
    sort1=[nums[0]]   #已排序区间
    length=len(nums)
    for i in range(1,length):
        for j in range(len(sort1)):
            if nums[i]<sort1[j]:   #符合条件，就在那个位置插入
                sort1.insert(j,nums[i])
                break    #找到第一个符合条件的数就可以跳出j这个循环了
        if j==len(sort1)-1:    #如果num[i]>=sort1的所有数，就在最后把这个数放到已排序区间
            sort1.append(nums[i])
    return sort1

原地排序算法、稳定排序算法

算法3:选择排序

def selection(nums):
    for i in range(len(nums)-1):
        nums[i],nums[nums.index(min(nums[i:]))]=min(nums[i:]),nums[i]  
        #nums[i]与i之后的最小值交换位置

原地排序算法，但不是稳定排序算法（如5 8 5 2 9）

时间复杂度：最好的与最坏的都为o(n^2)。（应该是因为不管是怎样的情况，都要全部遍历一遍、交换一遍）