三个月算法进阶--day30
目录
异或
bit位相同为0，否则为1
任何数异或自己=把自己置零，0异或任何数=任何数，异或运算满足交换律和结合律
位运算
线性时间复杂度和常数空间复杂度(不需要额外空间)
Python的集合做临时存储方便遍历
Python的reduce
reduce(lambda x, y: x ^ y, nums) functools.reduce(int.xor,nums)
Python的range
range(7, 0, -1)
Python的交换
a[i], a[i+1] = a[i+1], a[i]
排序之冒泡排序、选择排序
大的项往后冒泡，适用性广(链表)，无需额外空间
def bubbleSort(alist):
for passnum in range(len(alist)-1, 0, -1):
for i in range(passnum):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
性能改进：监控是否提前完成排序，选择排序（每趟只进行一次交换）
比对的时间复杂度，交换的时间复杂度
选择排序的交换的时间复杂度为O(n)，比冒泡排序更优
排序之插入排序
类似整理扑克牌，性能比插入排序稍好(交换1次)
def insertionSort(alist):
for index in range(1, len(alist)):
currentvalue = alist[index]
position = index
while position > 0 and alist[position-1] > currentvalue:
alist[postion] = alist[position-1]
position = position - 1
alist[postion] = currentvalue
列表越接近有序，比对次数就越少
性能改进：谢尔排序
谢尔排序
每趟都使得列表更加接近有序，时间复杂度在O(n)和O(n^2)之间
def shellSort(alist):
sublistcount = len(alist) // 2
while sublistcount > 0:
for startposition in range(sublistcount):
gapInsertionSort(alist, startpostion, sublistcount)
sublistcount = sublistcount // 2
def gapInsertionSort(alist, start, gap):
for i in range(start+gap, len(alist), gap):
currentvalue = alist[1]
position = i
while postion >= gap and alist[postion-gap] > currentvalue:
alist[postion] = alist[postion-gap]
postion = postion - gap
alist[postion] = currentvalue
间隔多大，子列表就有多少个，越小子列表越长