幾種算法實(shí)例

-- 記錄了幾種比較常用的算法,具體的也參考了很多文章,下面是我自己記錄.侏儒 ,冒泡,選擇,插入,快速排序,歸并排序

首先我們介紹一個(gè)測(cè)試時(shí)間的利器,通常情況我們會(huì)使用time包來(lái)測(cè)試,但是只能測(cè)試總共的時(shí)間,而這個(gè)cProfile能測(cè)試具體步驟的時(shí)間,可以看得非常清楚瓶頸在哪里.

import cProfile   #測(cè)試間的利器

def add(a,b):
    return a+b

def for_func():
    result = 0
    for i in range(1000000):
        result += i 
    return result

def main(a,b):
    print 'this is the result for a + b'
    result = add(a,b)
    print result
    print 'test for function'
    print for_func()

cProfile.run('main(1,2)')

this is the result for a + b
3
test for function
499999500000
         115 function calls in 0.144 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <ipython-input-56-3130e18dd725>:1(add)
        1    0.114    0.114    0.143    0.143 <ipython-input-57-827e3096c393>:1(for_func)
        1    0.000    0.000    0.144    0.144 <ipython-input-58-19c5a6c13393>:1(main)
        1    0.000    0.000    0.144    0.144 <string>:1(<module>)
        9    0.001    0.000    0.001    0.000 iostream.py:180(schedule)
        8    0.000    0.000    0.000    0.000 iostream.py:284(_is_master_process)
        8    0.000    0.000    0.000    0.000 iostream.py:297(_schedule_flush)
        8    0.000    0.000    0.001    0.000 iostream.py:342(write)
        9    0.000    0.000    0.000    0.000 iostream.py:87(_event_pipe)
        9    0.000    0.000    0.000    0.000 threading.py:570(isSet)
        9    0.000    0.000    0.000    0.000 threading.py:986(isAlive)
        8    0.000    0.000    0.000    0.000 utf_8.py:15(decode)
        8    0.000    0.000    0.000    0.000 {_codecs.utf_8_decode}
        8    0.000    0.000    0.000    0.000 {isinstance}
        8    0.000    0.000    0.000    0.000 {method 'decode' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        8    0.000    0.000    0.000    0.000 {nt.getpid}
        9    0.000    0.000    0.000    0.000 {nt.urandom}
        1    0.029    0.029    0.029    0.029 {range}

# 這個(gè)表示正無(wú)窮,同理-inf表示負(fù)無(wú)窮,下面我們會(huì)用到
float('inf')

inf

侏儒排序法

從第一個(gè)數(shù)字開(kāi)始和前面的進(jìn)行比較,如果小于前面的數(shù)字就交換位置然后將指針減少1然后繼續(xù)循環(huán)檢測(cè)下一個(gè). 最后的結(jié)果就是講最小的移到第一位,然后從第一位在開(kāi)始往后就像在紙上來(lái)回畫(huà)直線(xiàn)一樣每次將最小的數(shù)字放到最前面然后從最前面依次往后檢測(cè),知道在找到滿(mǎn)足條件的再次將數(shù)字移到前面.

seq = [5,4,3,2,1]

def gnomesort(seq):
    i = 0 
    while i <len(seq):
        if i == 0 or seq[i-1] <= seq[i]:
            i += 1
        else:
            seq[i-1], seq[i] = seq[i], seq[i-1]
            i -= 1
    return seq

gnomesort(seq)

[1, 2, 3, 4, 5]

插入排序

從第一個(gè)開(kāi)始,用這個(gè)數(shù)字和之前的每一個(gè)數(shù)字進(jìn)行比較直到比他前一個(gè)數(shù)字小為止,那么這個(gè)數(shù)字的位置就可以確定了-放到他的前面.當(dāng)然這個(gè)排序是從index = 0 開(kāi)始的.

seq = [5,4,3,2,1]

# 遞歸版插入排序
def ins_sort_rec(seq,i):
    '''
    遞歸是從最低層開(kāi)始排序的也就是從索引為0的地方開(kāi)始排序的
    seq 是一個(gè)列表,i是列表的長(zhǎng)度減1,也就是最后一個(gè)元素索引的位置.返回一個(gè)排序好的列表
    '''
    if i == 0:return seq
    ins_sort_rec(seq,i-1)   # 這個(gè)遞歸的使用可以理解為替換,將函數(shù)替換為這個(gè)函數(shù)的除去函數(shù)體的其他部分.
    j = i 
    while j > 0 and seq[j-1]> seq[j]:
        seq[j-1],seq[j] = seq[j],seq[j-1]
        j -= 1
    return seq
        

ins_sort_rec(seq,len(seq)-1)

[1, 2, 3, 4, 5]

# 插入排序 普通版
def ins_sort_nor(seq,i):
    '''seq 是一個(gè)列表,i是列表長(zhǎng)度-1,這里用這個(gè)數(shù)字和他前一個(gè)數(shù)字進(jìn)行比較如果小于就互換位置,互換后繼續(xù)檢查和前一個(gè)的大小比較,直到小于位置.
    '''
    for x in range(0,i):
        while x > 0 and seq[x-1] > seq[x]:
            seq[x-1],seq[x] = seq[x], seq[x-1]
            x -= 1
    return seq
    

ins_sort_nor(seq,len(seq)-1)

[1, 2, 3, 4, 5]

選擇排序

選擇排序:第一次將最大的放到最后,然后將剩下的所有中最大的放到最后,依次放到最后一個(gè).

這個(gè)排序是從數(shù)列的最后一位開(kāi)始的.

seq = [5,4,3,2,1]

# 遞歸版選擇排序
def sel_sort_res(seq,i):
    if i == 0: return seq
    max_j = i 
    for x in range(i):
        if seq[x] > seq[max_j]:
            seq[x],seq[max_j] = seq[max_j],seq[x]
    return sel_sort_res(seq,i-1)

sel_sort_res(seq,len(seq)-1)

[1, 2, 3, 4, 5]

def sel_sort_nor(seq):
    for i in range(len(seq)-1,0,-1):
        max_j = i 
        for j in range(i):
            if seq[j] >seq[max_j]:max_j = j
        seq[i],seq[max_j] = seq[max_j],seq[i]
    return seq

sel_sort_nor([2,4,1])

[1, 2, 4]

快速排序

快速排序的邏輯是: 每次選中一個(gè)參考值,然后把大于參考值的放到右邊小于參考值的放到左邊,這樣就可以確定參考值的位置,每次確定一個(gè)參考值的位置,循環(huán)往復(fù)就可以逐步確認(rèn)每個(gè)數(shù)字的位置了

def QuickSort(myList,start,end):
    #判斷l(xiāng)ow是否小于high,如果為false,直接返回
    if start < end:
        i,j = start,end
        #設(shè)置基準(zhǔn)數(shù)
        base = myList[i]  

        while i < j:  
            #如果列表后邊的數(shù),比基準(zhǔn)數(shù)大或相等,則前移一位直到有比基準(zhǔn)數(shù)小的數(shù)出現(xiàn)
            while (i < j) and (myList[j] >= base):  
                j = j - 1  

            #如找到,則把第j個(gè)元素賦值給第個(gè)元素i,此時(shí)表中i,j個(gè)元素相等
            myList[i] = myList[j]

            #同樣的方式比較前半?yún)^(qū)
            while (i < j) and (myList[i] <= base):
                i = i + 1
            myList[j] = myList[i]
        #做完第一輪比較之后,列表被分成了兩個(gè)半?yún)^(qū),并且i=j,需要將這個(gè)數(shù)設(shè)置回base
        myList[i] = base

        #遞歸前后半?yún)^(qū)
        QuickSort(myList, start, i - 1)
        QuickSort(myList, j + 1, end)
    return myList


myList = [49,38,65,97,76,13,27,49]
print("Quick Sort: ")
QuickSort(myList,0,len(myList)-1)
print(myList)

Quick Sort: 
[13, 27, 38, 49, 49, 65, 76, 97]

# 快速排序
def quick_sort(seq,start,end):
    if i < j: 
        i,j = start,end
        base = seq[i]
        while i <j:
            while i < j and seq[j] >= base:
                j -= 1
            seq[i] = seq[j]
            while i < j and seq[i] <= base:
                i += 1
            seq[j] = seq[i]
        seq[i] = base
    
    quick_sort(seq,start, i -1)
    quick_sort(seq,j+1,end)
    
    return seq

myList = [49,38,65,97,76,13,27,49]
print("Quick Sort: ")
quick_sort(myList,0,len(myList)-1)
print(myList)

Quick Sort: 
[13, 27, 38, 49, 49, 65, 76, 97]

冒泡排序

def bubble_sort(seq,order=1):
    end = len(seq)-1
    for x in range(end,0,-1):
        for y in range(x):
            if order == 1:
                if seq[y] > seq[y+1]:
                    seq[y],seq[y+1] = seq[y+1],seq[y]
            
    return seq

alist = [4,3,2,1,5,7,4,5,4,3,2,4,5,6,7,78,87,6,54,3,3]
bubble_sort(alist)

[1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 7, 7, 54, 78, 87]

這個(gè)算法中,最好的時(shí)間復(fù)雜度是 n, 最差的時(shí)間復(fù)雜度是n**2 所以是時(shí)間復(fù)雜度應(yīng)該介于這兩者之間

歸并排序法

def mergesort(seq):
    mid = len(seq)//2
    lft, rgt = seq[:mid],seq[mid:]
    if len(lft) > 1 : lft = mergesort(lft)
    if len(rgt) > 1 : rgt = mergesort(rgt)
    res = []
    while lft and rgt:
        if lft[-1] >= rgt[-1]:
            res.append(lft.pop())
        else:
            res.append(rgt.pop())
    res.reverse()
    return (lft or rgt) + res    

如何從某一個(gè)數(shù)字列表中找出彼此最接近但是不相等的兩個(gè)數(shù):

思路: 找出兩個(gè)數(shù)字的絕對(duì)差最小,兩次遍歷整個(gè)列表,兩個(gè)數(shù)的差值比較如果比上一個(gè)小那么就取用這個(gè)差值和這兩個(gè)數(shù)字

alist = [1,2,5,3,5,3.122,12,23.43,79,4,8.1,8.12]

dd = float('inf')
for x in alist:
    for y in alist:
        if x == y : continue
        d = abs(x - y)
        if d < dd:
            xx, yy,dd = x, y,d

xx,yy  # 對(duì)于這個(gè)算法來(lái)說(shuō),時(shí)間復(fù)雜度是平方級(jí)的

(8.1, 8.12)

如果使用排序好的列表進(jìn)行排序速度將會(huì)提高

newlist = sorted(alist)  # 如果使用list.sort() 方法那么原本的list的排序就會(huì)改變慎用

i = 0
dd = float('inf')
while i < len(newlist)-1:
    if newlist[i] == newlist[i+1]: 
        i +=1
    else:
        d = abs(newlist[i] - newlist[i+1])
        if d < dd:
            x,y,dd = newlist[i],newlist[i+1],d
        i += 1
x,y

(1, 2)

幾種排序的思想以及方法

冒泡算法思想：

每次相鄰元素進(jìn)行比較靠瞎，如果發(fā)現(xiàn)較小的元素在后面府瞄，就交換兩個(gè)相鄰的元素,每次循環(huán)都將最大是數(shù)據(jù)排列到結(jié)尾處.

選擇排序算法思想：

在冒泡排序上做了優(yōu)化床估，減少了交換次數(shù)肾档，在首輪選擇最大的數(shù)放在第一項(xiàng)臊旭，一輪之后第一項(xiàng)是有序的了，第二輪從第二項(xiàng)開(kāi)始選擇最大的數(shù)放在第二項(xiàng)颖医，以此類(lèi)推庐完，直到整個(gè)數(shù)組完全有序

插入排序算法思想：

和前倆種排序不同，插入排序在排序過(guò)程中是局部有序分井，隨著插入項(xiàng)的增多车猬，有序部分的項(xiàng)的位置會(huì)發(fā)生改變，而冒泡排序和選擇排序每輪確定的項(xiàng)數(shù)的位置是永遠(yuǎn)不變的尺锚。在首輪珠闰，選擇第二項(xiàng)作為插入項(xiàng)，然后取出這一項(xiàng)放在一個(gè)變量中瘫辩，和前一項(xiàng)比較而且小伏嗜，則前一項(xiàng)后移到第二項(xiàng)的位置，然后第二項(xiàng)也就是插入項(xiàng)放在前一項(xiàng)的位置伐厌，第二輪選擇第三項(xiàng)作為插入項(xiàng)然后取出和前一項(xiàng)也就是第二項(xiàng)比較如果小承绸，第二項(xiàng)后移到插入項(xiàng)，然后插入相在和第一項(xiàng)比較如果小挣轨，則第一項(xiàng)后移到第二項(xiàng)军熏，插入項(xiàng)放在第一項(xiàng)，以此類(lèi)推卷扮。

總結(jié)：

冒泡算法荡澎，每次比較如果發(fā)現(xiàn)較大的元素在后面，就交換兩個(gè)相鄰的元素晤锹。而選擇排序算法的改進(jìn)在于：先并不急于調(diào)換位置摩幔，先從Aarray[0]開(kāi)始逐個(gè)檢查，看哪個(gè)數(shù)最大就記下該數(shù)所在的位置j鞭铆，等一躺掃描完畢或衡，再把Arraymax和A[0]對(duì)調(diào)，這時(shí)Array[0]到Array[6]中最大的數(shù)據(jù)就換到了最前面的位置。所以薇宠，選擇排序每掃描一遍數(shù)組，只需要一次真正的交換艰额，而冒泡可能需要很多次澄港，比較的次數(shù)是一樣的。插入排序算法比冒泡快一倍柄沮，比選擇排序略快一點(diǎn)

seq = [7,5,3,56,7,8,3,12,2]

# 冒泡排序
def bubble_sort(seq):
    # 索引的位置
    i = len(seq)-1
    for x in range(i,0,-1):
        for y in range(x):
            if seq[y]<seq[y+1] :
                seq[y+1] , seq[y] = seq[y] ,seq[y+1]
    return seq    

bubble_sort(seq)

[56, 12, 8, 7, 7, 5, 3, 3, 2]

seq

[7, 7, 7, 7, 7, 7, 7, 12, 12]

# 侏儒算法
def gon_sort(seq,end):
    i = 0
    while i < end:
        if  i == 0 or seq[i-1] <= seq[i]:
            i += 1
        else:
            seq[i-1],seq[i] = seq[i],seq[i-1]
            i -= 1
    return seq

seq = [7,5,3,56,7,8,3,12,2,5,3,21,6]
end = len(seq)
gon_sort(seq,end)

[2, 3, 3, 3, 5, 5, 6, 7, 7, 8, 12, 21, 56]

def quick_sort(seq,start,end):
    if start < end:
        i,j = start,end
        base = seq[i]
        while i < j:
            while i < j and seq[j] >= base:
                j -= 1
            seq[i] = seq[j]
            while i < j and seq[i] <= base:
                i += 1
            seq[j] = seq[i] 
        seq[i] = base
        
        quick_sort(seq,start,i-1)
        
        quick_sort(seq,j+1,end)
    return seq

seq = [7,5,3,56,7,8,3,12,2,5,3,21,6]
start = 0
end = len(seq)-1
quick_sort(seq,start,end)

[2, 3, 3, 3, 5, 5, 6, 7, 7, 8, 12, 21, 56]

def select_sort(seq,end):
    for x in range(end,0,-1):
        max_j = end 
        for y in range(x):
            if seq[y]>seq[max_j]: max_j = y