本文實(shí)例為大家分享了Python常用算法的具體代碼，供大家參考，具體內(nèi)容如下

1.算法定義

算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。也就是說(shuō)，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問題。不同的算法可能用不同的時(shí)間、空間或效率來(lái)完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來(lái)衡量。

一個(gè)算法應(yīng)該具有以下七個(gè)重要的特征：

①有窮性（Finiteness）：算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止；

②確切性(Definiteness)：算法的每一步驟必須有確切的定義；

③輸入項(xiàng)(Input)：一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸     入是指算法本身定出了初始條件；

④輸出項(xiàng)(Output)：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒       有輸出的算法是毫無(wú)意義的；

⑤可行性(Effectiveness)：算法中執(zhí)行的任何計(jì)算步驟都是可以被分解為基本的可執(zhí)行       的操作步，即每個(gè)計(jì)算步都可以在有限時(shí)間內(nèi)完成（也稱之為有效性）；

⑥高效性(High efficiency)：執(zhí)行速度快，占用資源少；

⑦健壯性(Robustness)：對(duì)數(shù)據(jù)響應(yīng)正確。

2. 時(shí)間復(fù)雜度

計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間,時(shí)間復(fù)雜度常用大O符號(hào)（大O符號(hào)（Big O notation）是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào)。更確切地說(shuō)，它是用另一個(gè)（通常更簡(jiǎn)單的）函數(shù)來(lái)描述一個(gè)函數(shù)數(shù)量級(jí)的漸近上界。在數(shù)學(xué)中，它一般用來(lái)刻畫被截?cái)嗟臒o(wú)窮級(jí)數(shù)尤其是漸近級(jí)數(shù)的剩余項(xiàng)；在計(jì)算機(jī)科學(xué)中，它在分析算法復(fù)雜性的方面非常有用。）表述，使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱為是漸近的，它考察當(dāng)輸入值大小趨近無(wú)窮時(shí)的情況。

大O，簡(jiǎn)而言之可以認(rèn)為它的含義是“order of”（大約是）。

無(wú)窮大漸近

大O符號(hào)在分析算法效率的時(shí)候非常有用。舉個(gè)例子，解決一個(gè)規(guī)模為 n 的問題所花費(fèi)的時(shí)間（或者所需步驟的數(shù)目）可以被求得：T(n) = 4n^2 - 2n + 2。
當(dāng) n 增大時(shí)，n^2; 項(xiàng)將開始占主導(dǎo)地位，而其他各項(xiàng)可以被忽略——舉例說(shuō)明：當(dāng) n = 500，4n^2; 項(xiàng)是 2n 項(xiàng)的1000倍大，因此在大多數(shù)場(chǎng)合下，省略后者對(duì)表達(dá)式的值的影響將是可以忽略不計(jì)的。

數(shù)學(xué)表示掃盲貼 python算法表示概念掃盲教程

一、計(jì)算方法

1.一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒有必要對(duì)每個(gè)算法都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。
一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度。記為T(n)。

2.一般情況下，算法的基本操作重復(fù)執(zhí)行的次數(shù)是模塊n的某一個(gè)函數(shù)f（n），因此，算法的時(shí)間復(fù)雜度記做：T（n）=O（f（n））。隨著模塊n的增大，算法執(zhí)行的時(shí)間的增長(zhǎng)率和f（n）的增長(zhǎng)率成正比，所以f（n）越小，算法的時(shí)間復(fù)雜度越低，算法的效率越高。
在計(jì)算時(shí)間復(fù)雜度的時(shí)候，先找出算法的基本操作，然后根據(jù)相應(yīng)的各語(yǔ)句確定它的執(zhí)行次數(shù)，再找出T（n）的同數(shù)量級(jí)（它的同數(shù)量級(jí)有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n?。页龊?，f（n）=該數(shù)量級(jí)，若T(n)/f(n)求極限可得到一常數(shù)c，則時(shí)間復(fù)雜度T（n）=O（f（n））。

3.常見的時(shí)間復(fù)雜度

按數(shù)量級(jí)遞增排列，常見的時(shí)間復(fù)雜度有：
常數(shù)階O(1),  對(duì)數(shù)階O(log2n),  線性階O(n),  線性對(duì)數(shù)階O(nlog2n),  平方階O(n^2)， 立方階O(n^3),...， k次方階O(n^k), 指數(shù)階O(2^n) 。
其中，

1.O(n)，O(n^2)， 立方階O(n^3),...， k次方階O(n^k) 為多項(xiàng)式階時(shí)間復(fù)雜度，分別稱為一階時(shí)間復(fù)雜度，二階時(shí)間復(fù)雜度。。。。
2.O(2^n)，指數(shù)階時(shí)間復(fù)雜度，該種不實(shí)用
3.對(duì)數(shù)階O(log2n),   線性對(duì)數(shù)階O(nlog2n)，除了常數(shù)階以外，該種效率最高

例：算法：

 for（i=1;i<=n;++i）
 {
 for(j=1;j<=n;++j)
 {
 c[ i ][ j ]=0; //該步驟屬于基本操作 執(zhí)行次數(shù)：n^2
 for(k=1;k<=n;++k)
 c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬于基本操作 執(zhí)行次數(shù)：n^3
 }
 }

  則有 T（n）= n^2+n^3，根據(jù)上面括號(hào)里的同數(shù)量級(jí)，我們可以確定 n^3為T（n）的同數(shù)量級(jí)
  則有f（n）= n^3，然后根據(jù)T（n）/f（n）求極限可得到常數(shù)c
  則該算法的 時(shí)間復(fù)雜度：T（n）=O（n^3)

四、 定義：如果一個(gè)問題的規(guī)模是n，解這一問題的某一算法所需要的時(shí)間為T(n)，它是n的某一函數(shù) T(n)稱為這一算法的“時(shí)間復(fù)雜性”。

當(dāng)輸入量n逐漸加大時(shí)，時(shí)間復(fù)雜性的極限情形稱為算法的“漸近時(shí)間復(fù)雜性”。

我們常用大O表示法表示時(shí)間復(fù)雜性，注意它是某一個(gè)算法的時(shí)間復(fù)雜性。大O表示只是說(shuō)有上界，由定義如果f(n)=O(n)，那顯然成立f(n)=O(n^2)，它給你一個(gè)上界，但并不是上確界，但人們?cè)诒硎镜臅r(shí)候一般都習(xí)慣表示前者。

此外，一個(gè)問題本身也有它的復(fù)雜性，如果某個(gè)算法的復(fù)雜性到達(dá)了這個(gè)問題復(fù)雜性的下界，那就稱這樣的算法是最佳算法。

“大O記法”：在這種描述中使用的基本參數(shù)是 n，即問題實(shí)例的規(guī)模，把復(fù)雜性或運(yùn)行時(shí)間表達(dá)為n的函數(shù)。這里的“O”表示量級(jí) (order)，比如說(shuō)“二分檢索是 O(logn)的”,也就是說(shuō)它需要“通過(guò)logn量級(jí)的步驟去檢索一個(gè)規(guī)模為n的數(shù)組”記法 O ( f(n) )表示當(dāng) n增大時(shí)，運(yùn)行時(shí)間至多將以正比于 f(n)的速度增長(zhǎng)。

這種漸進(jìn)估計(jì)對(duì)算法的理論分析和大致比較是非常有價(jià)值的，但在實(shí)踐中細(xì)節(jié)也可能造成差異。例如，一個(gè)低附加代價(jià)的O(n2)算法在n較小的情況下可能比一個(gè)高附加代價(jià)的 O(nlogn)算法運(yùn)行得更快。當(dāng)然，隨著n足夠大以后，具有較慢上升函數(shù)的算法必然工作得更快。

O(1)

Temp=i;i=j;j=temp;                   

以上三條單個(gè)語(yǔ)句的頻度均為1，該程序段的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無(wú)關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。如果算法的執(zhí)行時(shí)間不隨著問題規(guī)模n的增加而增長(zhǎng)，即使算法中有上千條語(yǔ)句，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。此類算法的時(shí)間復(fù)雜度是O(1)。

O(n^2)

2.1. 交換i和j的內(nèi)容

sum=0；                 （一次）
     for(i=1;i<=n;i++)       （n次 ）
        for(j=1;j<=n;j++) （n^2次 ）
         sum++；       （n^2次 ）

解：T(n)=2n^2+n+1 =O(n^2)

2.2. 

for (i=1;i<n;i++)
    {
        y=y+1;         ①  
        for (j=0;j<=(2*n);j++)   
           x++;        ②     
    }        

解： 語(yǔ)句1的頻度是n-1
          語(yǔ)句2的頻度是(n-1)*(2n+1)=2n^2-n-1
          f(n)=2n^2-n-1+(n-1)=2n^2-2
          該程序的時(shí)間復(fù)雜度T(n)=O(n^2).        

O(n)      

2.3.

a=0;
b=1;                      ①
    for (i=1;i<=n;i++) ②
    { 
       s=a+b;　　　?、?br />        b=a;　　　　?、?nbsp;
       a=s;　　　　　⑤
    }

解：語(yǔ)句1的頻度：2,       
           語(yǔ)句2的頻度： n,       
          語(yǔ)句3的頻度： n-1,       
          語(yǔ)句4的頻度：n-1,   
          語(yǔ)句5的頻度：n-1,                                 
          T(n)=2+n+3(n-1)=4n-1=O(n).
O(log2n )

2.4. 

    i=1;       ①
    while (i<=n)
       i=i*2; ②

解： 語(yǔ)句1的頻度是1, 
          設(shè)語(yǔ)句2的頻度是f(n),   則：2^f(n)<=n;f(n)<=log2n   
          取最大值f(n)= log2n,
          T(n)=O(log2n )

O(n^3)

2.5.

for(i=0;i<n;i++)
    { 
       for(j=0;j<i;j++) 
       {
          for(k=0;k<j;k++)
             x=x+2; 
       }
    }

解：當(dāng)i=m, j=k的時(shí)候,內(nèi)層循環(huán)的次數(shù)為k當(dāng)i=m時(shí), j 可以取 0,1,...,m-1 , 所以這里最內(nèi)循環(huán)共進(jìn)行了0+1+...+m-1=(m-1)m/2次所以,i從0取到n, 則循環(huán)共進(jìn)行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以時(shí)間復(fù)雜度為O(n^3).                                 

我們還應(yīng)該區(qū)分算法的最壞情況的行為和期望行為。如快速排序的最 壞情況運(yùn)行時(shí)間是 O(n^2)，但期望時(shí)間是 O(nlogn)。通過(guò)每次都仔細(xì) 地選擇基準(zhǔn)值，我們有可能把平方情況 (即O(n^2)情況)的概率減小到幾乎等于 0。在實(shí)際中，精心實(shí)現(xiàn)的快速排序一般都能以 (O(nlogn)時(shí)間運(yùn)行。

下面是一些常用的記法：

訪問數(shù)組中的元素是常數(shù)時(shí)間操作，或說(shuō)O(1)操作。一個(gè)算法如 果能在每個(gè)步驟去掉一半數(shù)據(jù)元素，如二分檢索，通常它就取 O(logn)時(shí)間。用strcmp比較兩個(gè)具有n個(gè)字符的串需要O(n)時(shí)間。常規(guī)的矩陣乘算法是O(n^3)，因?yàn)樗愠雒總€(gè)元素都需要將n對(duì) 元素相乘并加到一起，所有元素的個(gè)數(shù)是n^2。

指數(shù)時(shí)間算法通常來(lái)源于需要求出所有可能結(jié)果。例如，n個(gè)元 素的集合共有2n個(gè)子集,所以要求出所有子集的算法將是O(2n)的。指數(shù)算法一般說(shuō)來(lái)是太復(fù)雜了，除非n的值非常小，因?yàn)?，?這個(gè)問題中增加一個(gè)元素就導(dǎo)致運(yùn)行時(shí)間加倍。不幸的是，確實(shí)有許多問題 (如著名的“巡回售貨員問題” )，到目前為止找到的算法都是指數(shù)的。如果我們真的遇到這種情況，通常應(yīng)該用尋找近似最佳結(jié)果的算法替代之。 

常用排序 

冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort），是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡(jiǎn)單的排序算法。
它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。
這個(gè)算法的名字由來(lái)是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名。

data_set = [ 9,1,22,31,45,3,6,2,11 ]
 
loop_count = 0
for j in range(len(data_set)):
 for i in range(len(data_set) - j- 1): # -1 是因?yàn)槊看伪葘?duì)的都 是i 與i +1,不減1的話,最后一次對(duì)比會(huì)超出list 獲取范圍,-j是因?yàn)?每一次大loop就代表排序好了一個(gè)最大值,放在了列表最后面,下次loop就不用再運(yùn)算已經(jīng)排序好了的值 了
 if data_set[i] > data_set[i+1]: #switch
 tmp = data_set[i]
 data_set[i] = data_set[i+1]
 data_set[i+1] = tmp
 loop_count +=1
 print(data_set)
print(data_set)
print("loop times", loop_count)

選擇排序

The algorithm works by selecting the smallest unsorted item and then swapping it with the item in the next position to be filled.

The selection sort works as follows: you look through the entire array for the smallest element, once you find it you swap it (the smallest element) with the first element of the array. Then you look for the smallest element in the remaining array (an array without the first element) and swap it with the second element. Then you look for the smallest element in the remaining array (an array without first and second elements) and swap it with the third element, and so on. Here is an example,

data_set = [ 9,1,22,31,45,3,6,2,11 ]
 
smallest_num_index = 0 #初始列表最小值,默認(rèn)為第一個(gè)
 
loop_count = 0
for j in range(len(data_set)):
 for i in range(j,len(data_set)):
 if data_set[i] < data_set[smallest_num_index]: #當(dāng)前值 比之前選出來(lái)的最小值 還要小,那就把它換成最小值
 smallest_num_index = i
 loop_count +=1
 else:
 print("smallest num is ",data_set[smallest_num_index])
 tmp = data_set[smallest_num_index]
 data_set[smallest_num_index] = data_set[j]
 data_set[j] = tmp
 
 print(data_set)
 print("loop times", loop_count)

The worst-case runtime complexity is O(n2).　　 

插入排序(Insertion Sort)

插入排序(Insertion Sort)的基本思想是：將列表分為2部分，左邊為排序好的部分，右邊為未排序的部分，循環(huán)整個(gè)列表，每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置，直到全部記錄插入完成為止。

插入排序非常類似于整撲克牌。

在開始摸牌時(shí)，左手是空的，牌面朝下放在桌上。接著，一次從桌上摸起一張牌，并將它插入到左手一把牌中的正確位置上。為了找到這張牌的正確位置，要將它與手中已有的牌從右到左地進(jìn)行比較。無(wú)論什么時(shí)候，左手中的牌都是排好序的。

也許你沒有意識(shí)到，但其實(shí)你的思考過(guò)程是這樣的：現(xiàn)在抓到一張7，把它和手里的牌從右到左依次比較，7比10小，應(yīng)該再往左插，7比5大，好，就插這里。為什么比較了10和5就可以確定7的位置？為什么不用再比較左邊的4和2呢？因?yàn)檫@里有一個(gè)重要的前提：手里的牌已經(jīng)是排好序的。現(xiàn)在我插了7之后，手里的牌仍然是排好序的，下次再抓到的牌還可以用這個(gè)方法插入。編程對(duì)一個(gè)數(shù)組進(jìn)行插入排序也是同樣道理，但和插入撲克牌有一點(diǎn)不同，不可能在兩個(gè)相鄰的存儲(chǔ)單元之間再插入一個(gè)單元，因此要將插入點(diǎn)之后的數(shù)據(jù)依次往后移動(dòng)一個(gè)單元。

 source = [92, 77, 67, 8, 6, 84, 55, 85, 43, 67]
 
 
for index in range(1,len(source)):
 current_val = source[index] #先記下來(lái)每次大循環(huán)走到的第幾個(gè)元素的值
 position = index
 
 while position > 0 and source[position-1] > current_val: #當(dāng)前元素的左邊的緊靠的元素比它大,要把左邊的元素一個(gè)一個(gè)的往右移一位,給當(dāng)前這個(gè)值插入到左邊挪一個(gè)位置出來(lái)
 source[position] = source[position-1] #把左邊的一個(gè)元素往右移一位
 position -= 1 #只一次左移只能把當(dāng)前元素一個(gè)位置 ,還得繼續(xù)左移只到此元素放到排序好的列表的適當(dāng)位置 為止
 
 source[position] = current_val #已經(jīng)找到了左邊排序好的列表里不小于current_val的元素的位置,把current_val放在這里
 print(source)

結(jié)果：

[77, 92, 67, 8, 6, 84, 55, 85, 43, 67]
[67, 77, 92, 8, 6, 84, 55, 85, 43, 67]
[8, 67, 77, 92, 6, 84, 55, 85, 43, 67]
[6, 8, 67, 77, 92, 84, 55, 85, 43, 67]
[6, 8, 67, 77, 84, 92, 55, 85, 43, 67]
[6, 8, 55, 67, 77, 84, 92, 85, 43, 67]
[6, 8, 55, 67, 77, 84, 85, 92, 43, 67]
[6, 8, 43, 55, 67, 77, 84, 85, 92, 67]
[6, 8, 43, 55, 67, 67, 77, 84, 85, 92]

#更容易理解的版本

 data_set = [ 9,1,22,9,31,-5,45,3,6,2,11 ]
for i in range(len(data_set)):
 #position = i
 while i > 0 and data_set[i] < data_set[i-1]:# 右邊小于左邊相鄰的值
 tmp = data_set[i]
 data_set[i] = data_set[i-1]
 data_set[i-1] = tmp
 i -= 1
 # position = i
 # while position > 0 and data_set[position] < data_set[position-1]:# 右邊小于左邊相鄰的值
 # tmp = data_set[position]
 # data_set[position] = data_set[position-1]
 # data_set[position-1] = tmp
 # position -= 1

快速排序（quick sort）

設(shè)要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個(gè)數(shù)據(jù)（通常選用數(shù)組的第一個(gè)數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱為一趟快速排序。值得注意的是，快速排序不是一種穩(wěn)定的排序算法，也就是說(shuō)，多個(gè)相同的值的相對(duì)位置也許會(huì)在算法結(jié)束時(shí)產(chǎn)生變動(dòng)　　

注：在待排序的文件中，若存在多個(gè)關(guān)鍵字相同的記錄，經(jīng)過(guò)排序后這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變，該排序方法是穩(wěn)定的；若具有相同關(guān)鍵字的記錄之間的相對(duì)次序發(fā)生改變，則稱這種排序方法是不穩(wěn)定的。
要注意的是，排序算法的穩(wěn)定性是針對(duì)所有輸入實(shí)例而言的。即在所有可能的輸入實(shí)例中，只要有一個(gè)實(shí)例使得算法不滿足穩(wěn)定性要求，則該排序算法就是不穩(wěn)定的。

排序演示

示例

假設(shè)用戶輸入了如下數(shù)組：

創(chuàng)建變量i=0（指向第一個(gè)數(shù)據(jù)）, j=5(指向最后一個(gè)數(shù)據(jù)), k=6(賦值為第一個(gè)數(shù)據(jù)的值)。
我們要把所有比k小的數(shù)移動(dòng)到k的左面，所以我們可以開始尋找比6小的數(shù)，從j開始，從右往左找，不斷遞減變量j的值，我們找到第一個(gè)下標(biāo)3的數(shù)據(jù)比6小，于是把數(shù)據(jù)3移到下標(biāo)0的位置，把下標(biāo)0的數(shù)據(jù)6移到下標(biāo)3，完成第一次比較：

i=0 j=3 k=6
接著，開始第二次比較，這次要變成找比k大的了，而且要從前往后找了。遞加變量i，發(fā)現(xiàn)下標(biāo)2的數(shù)據(jù)是第一個(gè)比k大的，于是用下標(biāo)2的數(shù)據(jù)7和j指向的下標(biāo)3的數(shù)據(jù)的6做交換，數(shù)據(jù)狀態(tài)變成下表：

i=2 j=3 k=6
稱上面兩次比較為一個(gè)循環(huán)。
接著，再遞減變量j，不斷重復(fù)進(jìn)行上面的循環(huán)比較。
在本例中，我們進(jìn)行一次循環(huán)，就發(fā)現(xiàn)i和j“碰頭”了：他們都指向了下標(biāo)2。于是，第一遍比較結(jié)束。得到結(jié)果如下，凡是k(=6)左邊的數(shù)都比它小，凡是k右邊的數(shù)都比它大：

如果i和j沒有碰頭的話，就遞加i找大的，還沒有，就再遞減j找小的，如此反復(fù)，不斷循環(huán)。注意判斷和尋找是同時(shí)進(jìn)行的。
然后，對(duì)k兩邊的數(shù)據(jù)，再分組分別進(jìn)行上述的過(guò)程，直到不能再分組為止。
注意：第一遍快速排序不會(huì)直接得到最終結(jié)果，只會(huì)把比k大和比k小的數(shù)分到k的兩邊。為了得到最后結(jié)果，需要再次對(duì)下標(biāo)2兩邊的數(shù)組分別執(zhí)行此步驟，然后再分解數(shù)組，直到數(shù)組不能再分解為止（只有一個(gè)數(shù)據(jù)），才能得到正確結(jié)果。

#_*_coding:utf-8_*_
__author__ = 'Alex Li'
 
 
def quick_sort(array,left,right):
 '''
 
 :param array:
 :param left: 列表的第一個(gè)索引
 :param right: 列表最后一個(gè)元素的索引
 :return:
 '''
 if left >=right:
 return
 low = left
 high = right
 key = array[low] #第一個(gè)值
 
 while low < high:#只要左右未遇見
 while low < high and array[high] > key: #找到列表右邊比key大的值 為止
 high -= 1
 #此時(shí)直接 把key(array[low]) 跟 比它大的array[high]進(jìn)行交換
 array[low] = array[high]
 array[high] = key
 
 
 while low < high and array[low] <= key : #找到key左邊比key大的值，這里為何是<=而不是<呢？你要思考。。。
 low += 1
 #array[low] =
 #找到了左邊比k大的值 ,把a(bǔ)rray[high](此時(shí)應(yīng)該剛存成了key) 跟這個(gè)比key大的array[low]進(jìn)行調(diào)換
 array[high] = array[low]
 array[low] = key
 
 quick_sort(array,left,low-1) #最后用同樣的方式對(duì)分出來(lái)的左邊的小組進(jìn)行同上的做法
 quick_sort(array,low+1, right)#用同樣的方式對(duì)分出來(lái)的右邊的小組進(jìn)行同上的做法
 
 
 
if __name__ == '__main__':
 
 array = [96,14,10,9,6,99,16,5,1,3,2,4,1,13,26,18,2,45,34,23,1,7,3,22,19,2]
 #array = [8,4,1, 14, 6, 2, 3, 9,5, 13, 7,1, 8,10, 12]
 print("before sort:", array)
 quick_sort(array,0,len(array)-1)
 
 print("-------final -------")
 print(array)

二叉樹

樹的特征和定義

樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀地看，它是數(shù)據(jù)元素（在樹中稱為結(jié)點(diǎn)）按分支關(guān)系組織起來(lái)的結(jié)構(gòu)，很象自然界中的樹那樣。樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹形象表示。樹在計(jì)算機(jī)領(lǐng)域中也得到廣泛應(yīng)用，如在編譯源程序時(shí)，可用樹表示源程序的語(yǔ)法結(jié)構(gòu)。又如在數(shù)據(jù)庫(kù)系統(tǒng)中，樹型結(jié)構(gòu)也是信息的重要組織形式之一。一切具有層次關(guān)系的問題都可用樹來(lái)描述。

樹(Tree)是元素的集合。我們先以比較直觀的方式介紹樹。下面的數(shù)據(jù)結(jié)構(gòu)是一個(gè)樹：

樹有多個(gè)節(jié)點(diǎn)(node)，用以儲(chǔ)存元素。某些節(jié)點(diǎn)之間存在一定的關(guān)系，用連線表示，連線稱為邊(edge)。邊的上端節(jié)點(diǎn)稱為父節(jié)點(diǎn)，下端稱為子節(jié)點(diǎn)。樹像是一個(gè)不斷分叉的樹根。

每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)(children)，而該節(jié)點(diǎn)是相應(yīng)子節(jié)點(diǎn)的父節(jié)點(diǎn)(parent)。比如說(shuō)，3,5是6的子節(jié)點(diǎn)，6是3,5的父節(jié)點(diǎn)；1,8,7是3的子節(jié)點(diǎn), 3是1,8,7的父節(jié)點(diǎn)。樹有一個(gè)沒有父節(jié)點(diǎn)的節(jié)點(diǎn)，稱為根節(jié)點(diǎn)(root)，如圖中的6。沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)(leaf)，比如圖中的1,8,9,5節(jié)點(diǎn)。從圖中還可以看到，上面的樹總共有4個(gè)層次，6位于第一層，9位于第四層。樹中節(jié)點(diǎn)的最大層次被稱為深度。也就是說(shuō)，該樹的深度(depth)為4。

如果我們從節(jié)點(diǎn)3開始向下看，而忽略其它部分。那么我們看到的是一個(gè)以節(jié)點(diǎn)3為根節(jié)點(diǎn)的樹：

三角形代表一棵樹

再進(jìn)一步，如果我們定義孤立的一個(gè)節(jié)點(diǎn)也是一棵樹的話，原來(lái)的樹就可以表示為根節(jié)點(diǎn)和子樹(subtree)的關(guān)系:

上述觀察實(shí)際上給了我們一種嚴(yán)格的定義樹的方法：

1. 樹是元素的集合。

2. 該集合可以為空。這時(shí)樹中沒有元素，我們稱樹為空樹 (empty tree)。

3. 如果該集合不為空，那么該集合有一個(gè)根節(jié)點(diǎn)，以及0個(gè)或者多個(gè)子樹。根節(jié)點(diǎn)與它的子樹的根節(jié)點(diǎn)用一個(gè)邊(edge)相連。

上面的第三點(diǎn)是以遞歸的方式來(lái)定義樹，也就是在定義樹的過(guò)程中使用了樹自身(子樹)。由于樹的遞歸特征，許多樹相關(guān)的操作也可以方便的使用遞歸實(shí)現(xiàn)。我們將在后面看到。

樹的實(shí)現(xiàn)

樹的示意圖已經(jīng)給出了樹的一種內(nèi)存實(shí)現(xiàn)方式: 每個(gè)節(jié)點(diǎn)儲(chǔ)存元素和多個(gè)指向子節(jié)點(diǎn)的指針。然而，子節(jié)點(diǎn)數(shù)目是不確定的。一個(gè)父節(jié)點(diǎn)可能有大量的子節(jié)點(diǎn)，而另一個(gè)父節(jié)點(diǎn)可能只有一個(gè)子節(jié)點(diǎn)，而樹的增刪節(jié)點(diǎn)操作會(huì)讓子節(jié)點(diǎn)的數(shù)目發(fā)生進(jìn)一步的變化。這種不確定性就可能帶來(lái)大量的內(nèi)存相關(guān)操作，并且容易造成內(nèi)存的浪費(fèi)。

一種經(jīng)典的實(shí)現(xiàn)方式如下:

樹的內(nèi)存實(shí)現(xiàn)

擁有同一父節(jié)點(diǎn)的兩個(gè)節(jié)點(diǎn)互為兄弟節(jié)點(diǎn)(sibling)。上圖的實(shí)現(xiàn)方式中，每個(gè)節(jié)點(diǎn)包含有一個(gè)指針指向第一個(gè)子節(jié)點(diǎn)，并有另一個(gè)指針指向它的下一個(gè)兄弟節(jié)點(diǎn)。這樣，我們就可以用統(tǒng)一的、確定的結(jié)構(gòu)來(lái)表示每個(gè)節(jié)點(diǎn)。

計(jì)算機(jī)的文件系統(tǒng)是樹的結(jié)構(gòu)，比如Linux文件管理背景知識(shí)中所介紹的。在UNIX的文件系統(tǒng)中，每個(gè)文件(文件夾同樣是一種文件)，都可以看做是一個(gè)節(jié)點(diǎn)。非文件夾的文件被儲(chǔ)存在葉節(jié)點(diǎn)。文件夾中有指向父節(jié)點(diǎn)和子節(jié)點(diǎn)的指針(在UNIX中，文件夾還包含一個(gè)指向自身的指針，這與我們上面見到的樹有所區(qū)別)。在git中，也有類似的樹狀結(jié)構(gòu)，用以表達(dá)整個(gè)文件系統(tǒng)的版本變化 (參考版本管理三國(guó)志)。

二叉樹：　

二叉樹是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合、每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的有序樹。它或者是空集，或者是由一個(gè)根和稱為左、右子樹的兩個(gè)不相交的二叉樹組成。

特點(diǎn)：

（1）二叉樹是有序樹，即使只有一個(gè)子樹，也必須區(qū)分左、右子樹；

（2）二叉樹的每個(gè)結(jié)點(diǎn)的度不能大于2，只能取0、1、2三者之一；

（3）二叉樹中所有結(jié)點(diǎn)的形態(tài)有5種：空結(jié)點(diǎn)、無(wú)左右子樹的結(jié)點(diǎn)、只有左子樹的結(jié)點(diǎn)、只有右子樹的結(jié)點(diǎn)和具有左右子樹的結(jié)點(diǎn)。

二叉樹(binary)是一種特殊的樹。二叉樹的每個(gè)節(jié)點(diǎn)最多只能有2個(gè)子節(jié)點(diǎn)：

二叉樹

由于二叉樹的子節(jié)點(diǎn)數(shù)目確定，所以可以直接采用上圖方式在內(nèi)存中實(shí)現(xiàn)。每個(gè)節(jié)點(diǎn)有一個(gè)左子節(jié)點(diǎn)(left children)和右子節(jié)點(diǎn)(right children)。左子節(jié)點(diǎn)是左子樹的根節(jié)點(diǎn)，右子節(jié)點(diǎn)是右子樹的根節(jié)點(diǎn)。

如果我們給二叉樹加一個(gè)額外的條件，就可以得到一種被稱作二叉搜索樹(binary search tree)的特殊二叉樹。二叉搜索樹要求：每個(gè)節(jié)點(diǎn)都不比它左子樹的任意元素小，而且不比它的右子樹的任意元素大。

(如果我們假設(shè)樹中沒有重復(fù)的元素，那么上述要求可以寫成：每個(gè)節(jié)點(diǎn)比它左子樹的任意節(jié)點(diǎn)大，而且比它右子樹的任意節(jié)點(diǎn)小)

二叉搜索樹，注意樹中元素的大小

二叉搜索樹可以方便的實(shí)現(xiàn)搜索算法。在搜索元素x的時(shí)候，我們可以將x和根節(jié)點(diǎn)比較:

1. 如果x等于根節(jié)點(diǎn)，那么找到x，停止搜索 (終止條件)

2. 如果x小于根節(jié)點(diǎn)，那么搜索左子樹

3. 如果x大于根節(jié)點(diǎn)，那么搜索右子樹

二叉搜索樹所需要進(jìn)行的操作次數(shù)最多與樹的深度相等。n個(gè)節(jié)點(diǎn)的二叉搜索樹的深度最多為n，最少為log(n)。

二叉樹的遍歷

遍歷即將樹的所有結(jié)點(diǎn)訪問且僅訪問一次。按照根節(jié)點(diǎn)位置的不同分為前序遍歷，中序遍歷，后序遍歷。

前序遍歷：根節(jié)點(diǎn)->左子樹->右子樹

中序遍歷：左子樹->根節(jié)點(diǎn)->右子樹

后序遍歷：左子樹->右子樹->根節(jié)點(diǎn)

例如：求下面樹的三種遍歷

前序遍歷：abdefgc

中序遍歷：debgfac

后序遍歷：edgfbca

二叉樹的類型

(1)完全二叉樹——若設(shè)二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層有葉子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都是從左到右依次排布，這就是完全二叉樹。

(2)滿二叉樹——除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹。

(3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區(qū)別于AVL算法），它是一棵二叉排序樹，且具有以下性質(zhì)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹都是一棵平衡二叉樹

如何判斷一棵樹是完全二叉樹？按照定義

教材上的說(shuō)法：一個(gè)深度為k，節(jié)點(diǎn)個(gè)數(shù)為 2^k - 1 的二叉樹為滿二叉樹。這個(gè)概念很好理解，就是一棵樹，深度為k，并且沒有空位。

首先對(duì)滿二叉樹按照廣度優(yōu)先遍歷（從左到右）的順序進(jìn)行編號(hào)。

一顆深度為k二叉樹，有n個(gè)節(jié)點(diǎn)，然后，也對(duì)這棵樹進(jìn)行編號(hào)，如果所有的編號(hào)都和滿二叉樹對(duì)應(yīng)，那么這棵樹是完全二叉樹。

如何判斷平衡二叉樹？

（b）左邊的圖 左子數(shù)的高度為3，右子樹的高度為1，相差超過(guò)1

（b）右邊的圖 -2的左子樹高度為0 右子樹的高度為2，相差超過(guò)1

二叉樹遍歷實(shí)現(xiàn)

class TreeNode(object):
 def __init__(self,data=0,left=0,right=0):
 self.data = data
 self.left = left
 self.right = right
 
class BTree(object):
 def __init__(self,root=0):
 self.root = root
 
 
 def preOrder(self,treenode):
 if treenode is 0:
 return
 print(treenode.data)
 self.preOrder(treenode.left)
 self.preOrder(treenode.right)
 def inOrder(self,treenode):
 if treenode is 0:
 return
 self.inOrder(treenode.left)
 print(treenode.data)
 self.inOrder(treenode.right)
 
 def postOrder(self,treenode):
 if treenode is 0:
 return
 self.postOrder(treenode.left)
 self.postOrder(treenode.right)
 print(treenode.data)
if __name__ == '__main__':
 n1 = TreeNode(data=1)
 n2 = TreeNode(2,n1,0)
 n3 = TreeNode(3)
 n4 = TreeNode(4)
 n5 = TreeNode(5,n3,n4)
 n6 = TreeNode(6,n2,n5)
 n7 = TreeNode(7,n6,0)
 n8 = TreeNode(8)
 root = TreeNode('root',n7,n8)
 
 bt = BTree(root)
 print("preOrder".center(50,'-'))
 print(bt.preOrder(bt.root))
 
 print("inOrder".center(50,'-'))
 print (bt.inOrder(bt.root))
 
 print("postOrder".center(50,'-'))
 print (bt.postOrder(bt.root))

堆排序

堆排序，顧名思義，就是基于堆。因此先來(lái)介紹一下堆的概念。
堆分為最大堆和最小堆，其實(shí)就是完全二叉樹。最大堆要求節(jié)點(diǎn)的元素都要大于其孩子，最小堆要求節(jié)點(diǎn)元素都小于其左右孩子，兩者對(duì)左右孩子的大小關(guān)系不做任何要求，其實(shí)很好理解。有了上面的定義，我們可以得知，處于最大堆的根節(jié)點(diǎn)的元素一定是這個(gè)堆中的最大值。其實(shí)我們的堆排序算法就是抓住了堆的這一特點(diǎn)，每次都取堆頂?shù)脑?，將其放在序列最后面，然后將剩余的元素重新調(diào)整為最大堆，依次類推，最終得到排序的序列。

堆排序就是把堆頂?shù)淖畲髷?shù)取出,

將剩余的堆繼續(xù)調(diào)整為最大堆,具體過(guò)程在第二塊有介紹,以遞歸實(shí)現(xiàn)

剩余部分調(diào)整為最大堆后,再次將堆頂?shù)淖畲髷?shù)取出,再將剩余部分調(diào)整為最大堆,這個(gè)過(guò)程持續(xù)到剩余數(shù)只有一個(gè)時(shí)結(jié)束

#_*_coding:utf-8_*_
__author__ = 'Alex Li'
import time,random
def sift_down(arr, node, end):
 root = node
 #print(root,2*root+1,end)
 while True:
 # 從root開始對(duì)最大堆調(diào)整
 
 child = 2 * root +1 #left child
 if child > end:
 #print('break',)
 break
 print("v:",root,arr[root],child,arr[child])
 print(arr)
 # 找出兩個(gè)child中交大的一個(gè)
 if child + 1 <= end and arr[child] < arr[child + 1]: #如果左邊小于右邊
 child += 1 #設(shè)置右邊為大
 
 if arr[root] < arr[child]:
 # 最大堆小于較大的child, 交換順序
 tmp = arr[root]
 arr[root] = arr[child]
 arr[child]= tmp
 
 # 正在調(diào)整的節(jié)點(diǎn)設(shè)置為root
 #print("less1:", arr[root],arr[child],root,child)
 
 root = child #
 #[3, 4, 7, 8, 9, 11, 13, 15, 16, 21, 22, 29]
 #print("less2:", arr[root],arr[child],root,child)
 else:
 # 無(wú)需調(diào)整的時(shí)候, 退出
 break
 #print(arr)
 print('-------------')
 
def heap_sort(arr):
 # 從最后一個(gè)有子節(jié)點(diǎn)的孩子還是調(diào)整最大堆
 first = len(arr) // 2 -1
 for i in range(first, -1, -1):
 sift_down(arr, i, len(arr) - 1)
 #[29, 22, 16, 9, 15, 21, 3, 13, 8, 7, 4, 11]
 print('--------end---',arr)
 # 將最大的放到堆的最后一個(gè), 堆-1, 繼續(xù)調(diào)整排序
 for end in range(len(arr) -1, 0, -1):
 arr[0], arr[end] = arr[end], arr[0]
 sift_down(arr, 0, end - 1)
 #print(arr)
def main():
 # [7, 95, 73, 65, 60, 77, 28, 62, 43]
 # [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]
 #l = [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]
 #l = [16,9,21,13,4,11,3,22,8,7,15,27,0]
 array = [16,9,21,13,4,11,3,22,8,7,15,29]
 #array = []
 #for i in range(2,5000):
 # #print(i)
 # array.append(random.randrange(1,i))
 
 print(array)
 start_t = time.time()
 heap_sort(array)
 end_t = time.time()
 print("cost:",end_t -start_t)
 print(array)
 #print(l)
 #heap_sort(l)
 #print(l)
 
 
if __name__ == "__main__":
 main()

人類能理解的版本

dataset = [16,9,21,3,13,14,23,6,4,11,3,15,99,8,22]

for i in range(len(dataset)-1,0,-1):
 print("-------",dataset[0:i+1],len(dataset),i)
 #for index in range(int(len(dataset)/2),0,-1):
 for index in range(int((i+1)/2),0,-1):
 print(index)
 p_index = index

 l_child_index = p_index *2 - 1
 r_child_index = p_index *2
 print("l index",l_child_index,'r index',r_child_index)
 p_node = dataset[p_index-1]
 left_child = dataset[l_child_index]

 if p_node < left_child: # switch p_node with left child
 dataset[p_index - 1], dataset[l_child_index] = left_child, p_node
 # redefine p_node after the switch ,need call this val below
 p_node = dataset[p_index - 1]

 if r_child_index < len(dataset[0:i+1]): #avoid right out of list index range
 #if r_child_index < len(dataset[0:i]): #avoid right out of list index range
 #print(left_child)
 right_child = dataset[r_child_index]
 print(p_index,p_node,left_child,right_child)

 # if p_node < left_child: #switch p_node with left child
 # dataset[p_index - 1] , dataset[l_child_index] = left_child,p_node
 # # redefine p_node after the switch ,need call this val below
 # p_node = dataset[p_index - 1]
 #
 if p_node < right_child: #swith p_node with right child
 dataset[p_index - 1] , dataset[r_child_index] = right_child,p_node
 # redefine p_node after the switch ,need call this val below
 p_node = dataset[p_index - 1]

 else:
 print("p node [%s] has no right child" % p_node)


 #最后這個(gè)列表的第一值就是最大堆的值，把這個(gè)最大值放到列表最后一個(gè)， 把神剩余的列表再調(diào)整為最大堆

 print("switch i index", i, dataset[0], dataset[i] )
 print("before switch",dataset[0:i+1])
 dataset[0],dataset[i] = dataset[i],dataset[0]
 print(dataset)

希爾排序（shell sort）

希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本,該方法的基本思想是：先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序，待整個(gè)序列中的元素基本有序（增量足夠?。r(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況），效率是很高的，因此希爾排序在時(shí)間效率比直接插入排序有較大提高

首先要明確一下增量的取法：

第一次增量的取法為： d=count/2;

第二次增量的取法為: d=(count/2)/2;

最后一直到: d=1;

看上圖觀測(cè)的現(xiàn)象為：

d=3時(shí)：將40跟50比，因50大，不交換。

              將20跟30比，因30大，不交換。

              將80跟60比，因60小，交換。

d=2時(shí)：將40跟60比，不交換，拿60跟30比交換，此時(shí)交換后的30又比前面的40小，又要將40和30交換，如上圖。

              將20跟50比，不交換，繼續(xù)將50跟80比，不交換。

d=1時(shí)：這時(shí)就是前面講的插入排序了，不過(guò)此時(shí)的序列已經(jīng)差不多有序了，所以給插入排序帶來(lái)了很大的性能提高。

希爾排序代碼

import time,random

#source = [8, 6, 4, 9, 7, 3, 2, -4, 0, -100, 99]
#source = [92, 77, 8,67, 6, 84, 55, 85, 43, 67]

source = [ random.randrange(10000+i) for i in range(10000)]
#print(source)



step = int(len(source)/2) #分組步長(zhǎng)

t_start = time.time()


while step >0:
 print("---step ---", step)
 #對(duì)分組數(shù)據(jù)進(jìn)行插入排序

 for index in range(0,len(source)):
 if index + step < len(source):
 current_val = source[index] #先記下來(lái)每次大循環(huán)走到的第幾個(gè)元素的值
 if current_val > source[index+step]: #switch
 source[index], source[index+step] = source[index+step], source[index]

 step = int(step/2)
else: #把基本排序好的數(shù)據(jù)再進(jìn)行一次插入排序就好了
 for index in range(1, len(source)):
 current_val = source[index] # 先記下來(lái)每次大循環(huán)走到的第幾個(gè)元素的值
 position = index

 while position > 0 and source[
  position - 1] > current_val: # 當(dāng)前元素的左邊的緊靠的元素比它大,要把左邊的元素一個(gè)一個(gè)的往右移一位,給當(dāng)前這個(gè)值插入到左邊挪一個(gè)位置出來(lái)
 source[position] = source[position - 1] # 把左邊的一個(gè)元素往右移一位
 position -= 1 # 只一次左移只能把當(dāng)前元素一個(gè)位置 ,還得繼續(xù)左移只到此元素放到排序好的列表的適當(dāng)位置 為止

 source[position] = current_val # 已經(jīng)找到了左邊排序好的列表里不小于current_val的元素的位置,把current_val放在這里
 print(source)

t_end = time.time() - t_start

print("cost:",t_end)

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論