一、选择排序

def choose_sort(lis:list)->list:
    n = len(lis)
    for i in range(n-1):
        a = i # 最小元素指针
        for j in range(i+1,n):
            # 从后面找一个最小的元素
            if lis[j] < lis[a]:
                a = j
        if a != i:
            lis[i],lis[a] = lis[a],lis[i]
    return lis

二、冒泡排序

def bubble_sort(lis:list)->list:
    n = len(lis)
    for i in range(n-1):
        for j in range(n-i-1):
            if lis[j] > lis[j+1]:
                lis[j],lis[j+1]=lis[j+1],lis[j]
    return lis

三、插入排序

def insert_sort(lis:list)->list:
    n = len(lis)
    for i in range(1,n):
        # 0-1位置有序
        # 想让0-i位置有序
        for j in range(i,1,-1):
            # 当前元素位置为j
            if lis[j-1] > lis[j]:
                lis[j-1],lis[j] = lis[j],lis[j-1]
            else: # 如果当前元素没有小于前一个元素，说明顺序正常
                break
    return lis

四、位运算面试题

一个列表，全是整数，要求时间复杂度o（n），空间复杂度o（1）
1. 有一种数出现奇数次，其余数出现偶数次，找出出现奇数次的数
  a. ero=0 该数与列表的所有数异或，最终得到的数就是出现奇数次的数
  b. 原因：假设有【1，2，1，1，1，2，2，3，3】 等价于 1^2^1^1^1^2^2^3^3 等价于 1^1^1^1^2^2^2^3^3 自己异或自己等于0 前面四个1异或出来就是0 三个2异或出来就是2 后面俩三异或出来就是0 最终式子异或出来是2 ero异或2为2
2. 有两种数出现奇数次，其余数出现偶数次，找出出现奇数次的数
  a. ero1 与列表所有的是数异或，最终得到a^b ，ero2=a或者b ero1^ero2得到的就是另外一个数
  b. 列表中的元素异或，那么偶数个异或成0，奇数个的异或成自己，那么ero1=a^b ero不是0，那么ero至少有一位为1（int 32位），假设该位为第x位，那么x位上a和b两个元素不一样，否则异或出来就是0。ero2只跟第x位是1的异或，那么ero2要么是a要么是b，ero1^ero2得到另外一个数
  c. 一个数&自己的补码 得到该数最右边的1
  d. 下面代码注意这里&不等于1，要么等于0，要么等于rightOne

class Solve(object):
    def __init__(self,lis:list):
        self.lis = lis
    def solve_one(self)->int:
        ero = 0
        for val in self.lis:
            ero ^= val
        return ero
    def solve_two(self)->tuple:
        ero = 0
        for val in self.lis:
            ero ^=val
        ero2 = 0
        right_one = ero&(~ero+1) #提取最右边1的位置
        for val in self.lis:
            if val & right_one == right_one: # 这里等于right_one或者是0
                ero2 ^= val
        return ero^ero2,ero2