数据结构和算法是计算机技术的基本功之一，北京大学的课程深入浅出，使用Python作为载体简化了编程难度。最近浏览了45-51，主要内容是查找算法与各类排序算法。排序算法的学习需要重视算法在时间复杂度和空间复杂度两个方面的表现，例如归并排序的时间复杂度达到了稳定的最优nlogn，但因为需要生成子列表，需要双倍的空间开销。而快速排序不需要额外开销，但其重要参数中值的选取受到不确定性的制约，使得极端不平衡情况下算法的性能会退化到n2，因此稳定性也是值得考虑的因素。

1 顺序查找-遍历看是否一致

def sequentialSearch(alist,item):
    pos=0
    found=False
    while pos<len(alist) and not found:
        if alist[pos]==item:
            found= True
        else:
            pos+=1
    return found

比对的次数决定了算法复杂度-O(n)
若在列表中，查找复杂度平均为n/2-数据是无序的
如果数据是升序的呢？-可以设置提前结束的代码

def orderedSequentialSearch(alist,item):
    pos=0
    found=False
    stop=False
    while pos<len(alist) and not found and not stop:
        if alist[pos]==item:
            found= True
        else:
            if alist[pos]>item:
                stop=True
            pos+=1
    return found

不改变数量级，但减少了一些查找次数

2 二分查找有序表

O(logn)从列表中间开始匹配，体现了分治策略

def binarySearch(alist,item):
    first=0
    last=len(alist)-1
    found=False
    while first<=last and not found:
        midpoint=(first+last)//2
        if alist[midpoint]==item:
            found=True
        else:
            if item<alist[midpoint]:
                last=midpoint-1
            else:
                first=midpoint+1
    return found

使用递归实现

def resSearch(alist,item):
    first=0
    last=len(alist)-1
    midpoint=(first+last)//2
    found=False
    if len(alist)==0:#Caution，结束条件
        return False
    if alist[midpoint]==item:
        found=True
    else:
        if alist[midpoint]<item:
            resSearch(alist[midpoint+1:],item)
        else:
            resSearch(alist[:midpoint],item)
    return found

list[:k]切片操作复杂度为O(k)，增加了复杂度，可以用传入索引值代替
二分查找很Coooool，但是排序并不免费。

3 冒泡排序和选择排序

Bubble Sortion！对无序表进行多次比较交换，每次包含相邻数据项比较，(n-1)*(Ki)次,ki递减

def bubbleSort(alist):
    exchanges=True
    passnum = len(alist)-1
    while passnum>0 and exchanges:#检索最大值范围逐渐减少
        exchanges=False
        for i in range(passnum):
            if alist[i]>alist[i-1]:
                exchange=True
                temp=alist[i]
                alist[i]=alist[i+1]
                alist[i+1]=temp
        passnum-=1

python支持直接交换，A,B=B,A;
无序表初始数据项的排列状况对冒泡排序没有影响;
算法过程总共需要n-1趟，随着趟数增加，比对次数逐步从n-1减少到1，并包括可能发生的数据项交换;
比对次数是1到n-1的累加，因此比对复杂度O(n2);
最好不需要交换，最坏每次都要交换，平均一半，交换复杂度O(n2);
时间效率较差，大部分操作无效，但没有多的空间开销;
性能改进：某一次比对完全没有交换发生，则可提前终止，不改变整体复杂度.

4 选择排序

多趟比对，每趟使当前最大值就位；
每趟1次交换，记录最大项位置，与本趟最后一项交换；
交换次数减少为O(n);
空间开销增大。

5 插入排序Insertion Sort

时间复杂度仍然O(n2)，思想是始终维持一个已经排好序的资料表，其位置始终在列表的前部，然后逐步扩大这个子表直到全表。经过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[position]=alist[position-1]#大值后移
            position-=1 #直到前一项小于index项
    alist[position]=currentvalue

移动操作只一次赋值，比交换的3次少，因此性能更优秀。

6 谢尔排序Shell Sort

插入最好O(n)的比对次数。谢尔排序以插入排序为基础，对无序表进行间隔划分子列表，每个子列表
执行插入排序。子列表排序的间隔越小越接近插入排序。最后一次执行标准插入排序，只需少量比对次数。
间隔由大到小

def shellSort(alist):#20
    gap=len(alist)//2#gap n/2=10 5 间隔长度也是子列表数量
    while gap>0:
        for startposition in range(gap):#0,1,2,3,4-10 0-4
            gapInsertionSort(alist,startposition,gap)
        print("After increments of size",gap,"This list is",alist)#10done
        gap=gap//2#5

def gapInsertionSort(alist,start,gap):
    for i in range(start+gap,len(alist),gap):#10,20,10 5,20,5-5,10,15
        currentvalue=alist[i]
        position=i
        while position>0 and alist[position-gap]>currentvalue:#11vs1
            alist[position]=alist[position-gap]
            position=position-gap
        alist[position]=currentvalue#finish one iteration

以插入排序为基础，但每一迭代都使得表更加有序，减少了无效比对
如果将间隔保持在2的k次方-1，时间复杂度约为O(n3/2)1.5次方

7 归并排序-分治递归

递归调用自身-核心是重复相同操作，在这里是子表怎样合并为大表

def mergeSort(alist):
    if len(alist)>1:
        mid=len(alist)//2
        lefthalf=alist[:mid]
        righthalf=alist[mid:]
        #在调用归并之前，子程序应该已经排好序
        mergesort(lefthalf)
        mergeSort(righthalf)
        i=j=k=0
        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i]<righthalf[j]:
                alist[k]=lefthalf[i]
                i+=1
            else:
                alist[k]=righthalf[j]
                j+=1
            k+=1#依次取了k-1个数
        
        while i<len(lefthalf):
            alist[k]=lefthalf[i]#从第k个开始补上更大的数
            i+=1
            k+=1

        while j<len(righthalf):
            alist[k]=righthalf[j]
            j+=1
            k+=1
    return alist

#Python Style
def mergesssort(lst):
    if len(lst)<1:
        return lst
    mid=len(lst)//2
    left=mergesssort(lst[:mid])
    right=mergesssort(lst[mid:])
    merged=[]
    while left and right:#len(list)>0-list true, REALLY COOOOOOL
        if left[0]<=right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))
    merged.extend(right if right else left)#list.extend(list)
    return merged

分裂(logn)加归并(O(n))。O(nlogn)时间上最优，但额外一倍存储空间做归并

8 快速排序Quick Sort

根据中值数据把数据表分为两半，小于中值的一般和大于中值的一半，然后递归。关键是怎么找到中位数-随意找一个数，比如第一个。分裂手段：左标右移动，遇到比中值大的停止。右标左移动，遇到比中值小的停止。【比较】。左右标所指数据项交换，继续移动直到左标位于右标右侧，中值与右标位置交换。分裂之，左边小于中值，右边大于中值【递归】。

def quickSort(alist):
    quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
    if first<last:
        splitpoint=partition(alist,first,last)
        quickSortHelper(alist,first,splitpoint-1)
        quickSortHelper(alst,splitpoint,last)

def partition(alist,first,last):
    pivotvalue=alist[first]
    leftmark=first+1
    rightmark=last
    done=False
    while not done:
        while leftmark<=rightmark and alist[leftmark]<=pivotvalue:
            leftmark+=1
        
        while alist[rightmark]>=pivotvalue and rightmark>=leftmark:
            rightmark-=1
        
        if rightmark<leftmark:
            done=True
        else:
            temp=alist[leftmark]
            alist[leftmark]=alist[rightmark]
            alist[rightmark]=temp
    temp=alist[first]
    alist[first]=alist[rightmark]
    alist[rightmark]=temp
    return rightmark

分裂logn-假如中值在中间 移动n-每项都要与中值比对。不需要额外存储空间，没有创建子列表。极端：中值偏离，始终一部分没数据则O(n2)。改变，选取头中尾中的中数，但这会产生额外的计算开销。