1.抽象数据类型（ADT）
ADT=数据模型+定义在该模型上的一组操作
DS=基于某种特定语言，实现ADT的一整套算法
2.向量是数组的抽象与泛化，由一组元素按照线性次序封装而成。
3.动态空间管理：在即将发生上溢时，适当的扩大数组内部的容量
扩容时，内部开辟一个新的数组空间，将原来数组中存放的数据一一填充至新的数组空间，收回原来数组分配的空间。
1）容量递增策略：追加固定大小的容量:capacity+=INCREMENT（累计增容时间O(n^2),分摊增容时间O(n)）
2）容量加倍策略：追加加倍数量大小的容量：new_capacity=m*old_capicity（累计增容时间O(n),分摊增容时间O(1)）
4.去除无序向量中重复的元素
思路1：从第二个元素开始向后循环，在该元素之前的元素区间中查找是否存在与当前元素相同的值，若不存在则向后继续循环，若存在则删除当前元素//O(n^2)
思路2：先对需删除的重复元素做标记，然后再统一删除，稳定性保持，但因查找长度更长，从而导致更多的比对操作
思路3：先排序，后去重//O(nlogn)
5.有序向量
无序序列中，总有一对相邻元素逆序，有序序列中，任意一对相邻元素顺序
因此，相邻逆序对的数目，可用以度量向量的逆序程度
有序向量的去重操作
思路1：在有序向量中，重复的元素必然相互紧邻构成一个区间，因此，每一区间只需保留单个元素即可 #O(n^2)
li=[1,1,3,8,44,44,54,55,55,55,55,55,67,90,100,100] counter=len(li) i=0 while i<counter-1: if li[i]==li[i+1]: del li[i+1] counter=len(li) else: i=i+1 print(li)
思路二：
原算法中每一次移动只能移动一个单元，若能以重复区间为单位，成批删除雷同元素，性能将改进 #O(n)
li=[1,1,3,8,44,44,54,55,55,55,55,55,67,90,100,100] counter=len(li) i=0 temp=0 while i<counter-1: if li[i]==li[i+1]: temp=temp+1 #while elem=55 temp=4 else: move_num=counter-(i+1) while move_num>0: li[i-temp+1]=li[i+1] move_num=move_num-1 i=i+1 print(li)
直接变换下标，涉及到数组的算法采用多个下标进行操作会比较简便
li=[1,1,1,1,1,1,3,8,44,44,54,55,55,55,55,55,67,90,100,100] counter=len(li) i=0 j=1 while j<counter-1: if li[i]==li[j]: j=j+1 else: i=i+1 li[i]=li[j] j=j+1 print(li)
6.二分查找
def search(seq,aim): lo=0; hi=len(seq)-1 while lo<hi: mid=int((lo+hi)/2) if(li[mid]<aim): lo=mid+1 elif(aim<li[mid]): hi=mid else: return mid li=[1,2,9,12,42,54,98,110] aim=9 index=search(li,aim) print(index,li[index])
如何更为精细地评估查找算法的性能？
考查关键码（if语句的比较）的比较次数，即查找长度
7.斐波那契查找：
思路及原理：前述二分查找版本的效率仍有改进余地，因为不难发现转向左右分支前的关键码比较次数不等，而递归深度却相同
若能通过递归深度的不均衡，对转向成本的不均衡进行补偿，平均查找长度应能进一步缩短
比如，若设n=fib(k)-1，则可取mi=fib(k-1)-1，黄金比例，最优解
8.改进方案
思路1：无论向左或向右转向，都只进行一次比较，即所有分支只有2个方向，而不再是3个方向，e<x或x<=e
改进后，只有当元素数目hi-lo=1时，才判断该元素是否命中 while(1<hi-lo)
改进语义约定：
1)当有多个命中元素时，必须返回最靠后者
2)失败时，应返回小于e的最大者
9.冒泡排序
冒泡排序的改进，用一个变量进行记录，标明整体是否有序，每一次相邻元素比较后进行判断，若发生交换则不是整体有序
li=[11,33,4,208,22,89,182,32,69,358,222] for j in range(1,len(li)):#为外层循环次数 issorted=True for i in range(len(li)-j): current_value=li[i] next_value=li[i+1] if current_value > next_value: temp=li[i] li[i]=li[i+1] li[i+1]=temp issorted=False if issorted: break print(li)
反例：前小半部分为乱序排列，后大半部分为严格有序的序列
改进后
li=[3,32,6,43,24,11,22,33,44,55,66,77,88,99] lt=[3,6,32,24,11,22,43,33,44,55,66,77,88,99] lq=[3,6,32,24,11,22,33,43,44,55,66,77,88,99] hi=len(li) i=1 while i<hi: last=0 for j in range(len(li)-i): if li[j]>li[j+1]: temp=li[j] li[j]=li[j+1] li[j+1]=temp last=j i=i+1 hi=last print(li)
10.归并排序，时间复杂度为O(nlogn)
原理：分治策略
序列一分为二 //O(1)
子序列递归排序// 2*T(n/2)
合并有序子序列//O(n)
li=[1,3,23,32,52,66,99,1111,2222,3333] lj=[4,5,12,53,108,232] result=[] i=0 j=0 while i<len(li) or j<len(lj): if i<len(li) and (j>=len(lj) or li[i]<=lj[j]): result.append(li[i]) i=i+1 if j<len(lj) and (i>=len(li) or li[i]>lj[j]): result.append(lj[j]) j=j+1 print(result)