數(shù)據(jù)結(jié)構(gòu)和算法是計(jì)算機(jī)技術(shù)的基本功之一，北京大學(xué)的課程深入淺出渠驼，使用Python作為載體簡(jiǎn)化了編程難度。最近瀏覽了45-51曾沈，主要內(nèi)容是查找算法與各類排序算法。排序算法的學(xué)習(xí)需要重視算法在時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面的表現(xiàn)，例如歸并排序的時(shí)間復(fù)雜度達(dá)到了穩(wěn)定的最優(yōu)nlogn，但因?yàn)樾枰勺恿斜眚严枰p倍的空間開銷。而快速排序不需要額外開銷障涯，但其重要參數(shù)中值的選取受到不確定性的制約，使得極端不平衡情況下算法的性能會(huì)退化到n2膳汪，因此穩(wěn)定性也是值得考慮的因素唯蝶。

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

比對(duì)的次數(shù)決定了算法復(fù)雜度-O(n)
若在列表中，查找復(fù)雜度平均為n/2-數(shù)據(jù)是無序的
如果數(shù)據(jù)是升序的呢遗嗽？-可以設(shè)置提前結(jié)束的代碼

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

不改變數(shù)量級(jí)粘我，但減少了一些查找次數(shù)

2 二分查找有序表

O(logn)從列表中間開始匹配，體現(xiàn)了分治策略

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

使用遞歸實(shí)現(xiàn)

def resSearch(alist,item):
    first=0
    last=len(alist)-1
    midpoint=(first+last)//2
    found=False
    if len(alist)==0:#Caution痹换，結(jié)束條件
        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]切片操作復(fù)雜度為O(k)征字，增加了復(fù)雜度都弹，可以用傳入索引值代替
二分查找很Coooool，但是排序并不免費(fèi)匙姜。

3 冒泡排序和選擇排序

Bubble Sortion畅厢！對(duì)無序表進(jìn)行多次比較交換，每次包含相鄰數(shù)據(jù)項(xiàng)比較氮昧，(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;
無序表初始數(shù)據(jù)項(xiàng)的排列狀況對(duì)冒泡排序沒有影響;
算法過程總共需要n-1趟，隨著趟數(shù)增加郭计，比對(duì)次數(shù)逐步從n-1減少到1霸琴，并包括可能發(fā)生的數(shù)據(jù)項(xiàng)交換;
比對(duì)次數(shù)是1到n-1的累加椒振，因此比對(duì)復(fù)雜度O(n2);
最好不需要交換昭伸，最壞每次都要交換，平均一半澎迎，交換復(fù)雜度O(n2);
時(shí)間效率較差庐杨，大部分操作無效，但沒有多的空間開銷;
性能改進(jìn)：某一次比對(duì)完全沒有交換發(fā)生夹供，則可提前終止灵份，不改變整體復(fù)雜度.

4 選擇排序

多趟比對(duì)，每趟使當(dāng)前最大值就位哮洽；
每趟1次交換填渠，記錄最大項(xiàng)位置，與本趟最后一項(xiàng)交換鸟辅；
交換次數(shù)減少為O(n);
空間開銷增大氛什。

5 插入排序Insertion Sort

時(shí)間復(fù)雜度仍然O(n2)，思想是始終維持一個(gè)已經(jīng)排好序的資料表匪凉，其位置始終在列表的前部枪眉，然后逐步擴(kuò)大這個(gè)子表直到全表。經(jīng)過n-1趟的比對(duì)插入再层。比對(duì)尋找新項(xiàng)的插入位置贸铜。

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 #直到前一項(xiàng)小于index項(xiàng)
    alist[position]=currentvalue

移動(dòng)操作只一次賦值，比交換的3次少聂受，因此性能更優(yōu)秀蒿秦。

6 謝爾排序Shell Sort

插入最好O(n)的比對(duì)次數(shù)。謝爾排序以插入排序?yàn)榛A(chǔ)蛋济，對(duì)無序表進(jìn)行間隔劃分子列表棍鳖，每個(gè)子列表
執(zhí)行插入排序。子列表排序的間隔越小越接近插入排序瘫俊。最后一次執(zhí)行標(biāo)準(zhǔn)插入排序鹊杖，只需少量比對(duì)次數(shù)悴灵。
間隔由大到小

def shellSort(alist):#20
    gap=len(alist)//2#gap n/2=10 5 間隔長(zhǎng)度也是子列表數(shù)量
    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

以插入排序?yàn)榛A(chǔ)，但每一迭代都使得表更加有序骂蓖，減少了無效比對(duì)
如果將間隔保持在2的k次方-1积瞒，時(shí)間復(fù)雜度約為O(n3/2)1.5次方

7 歸并排序-分治遞歸

遞歸調(diào)用自身-核心是重復(fù)相同操作，在這里是子表怎樣合并為大表

def mergeSort(alist):
    if len(alist)>1:
        mid=len(alist)//2
        lefthalf=alist[:mid]
        righthalf=alist[mid:]
        #在調(diào)用歸并之前登下，子程序應(yīng)該已經(jīng)排好序
        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個(gè)數(shù)
        
        while i<len(lefthalf):
            alist[k]=lefthalf[i]#從第k個(gè)開始補(bǔ)上更大的數(shù)
            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)時(shí)間上最優(yōu)，但額外一倍存儲(chǔ)空間做歸并

8 快速排序Quick Sort

根據(jù)中值數(shù)據(jù)把數(shù)據(jù)表分為兩半被芳，小于中值的一般和大于中值的一半缰贝，然后遞歸。關(guān)鍵是怎么找到中位數(shù)-隨意找一個(gè)數(shù)畔濒，比如第一個(gè)剩晴。分裂手段：左標(biāo)右移動(dòng)，遇到比中值大的停止侵状。右標(biāo)左移動(dòng)赞弥，遇到比中值小的停止∪ば郑【比較】绽左。左右標(biāo)所指數(shù)據(jù)項(xiàng)交換，繼續(xù)移動(dòng)直到左標(biāo)位于右標(biāo)右側(cè)艇潭，中值與右標(biāo)位置交換拼窥。分裂之，左邊小于中值蹋凝，右邊大于中值【遞歸】鲁纠。

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-假如中值在中間 移動(dòng)n-每項(xiàng)都要與中值比對(duì)。不需要額外存儲(chǔ)空間仙粱，沒有創(chuàng)建子列表房交。極端：中值偏離，始終一部分沒數(shù)據(jù)則O(n2)伐割。改變候味，選取頭中尾中的中數(shù)，但這會(huì)產(chǎn)生額外的計(jì)算開銷隔心。