每天都在叫囂自己會什麼技術,什麼框架,可否意識到你每天都在被這些新名詞、新技術所迷惑,.net、xml等等技術固然誘人,可是如果自己的基礎不紮實,就像是在雲裡霧裡行走一樣,只能看到眼前,不能看到更遠的地方。這些新鮮的技術掩蓋了許多底層的原理,要想真正的學習技術還是走下雲端,扎扎實實的把基礎知識學好,有了這些基礎,要掌握那些新技術也就很容易了。
要編寫出優秀的**同樣要紮實的基礎,如果排序和查詢算法學的不好,怎麼對程式的效能進行優化?廢話不多說,本文要介紹的這些排序演算法就是基礎中的基礎,程式設計師必知!
1、直接插入排序
(1)基本思想:在要排序的一組數中,假設前面(n-1) [n>=2] 個數已經是排
好順序的,現在要把第n個數插到前面的有序數中,使得這n個數
也是排好順序的。如此反覆迴圈,直到全部排好順序。
(2)例項
2、希爾排序(也稱最小增量排序)
(1)基本思想:演算法先將要排序的一組數按某個增量d(n/2,n為要排序數的個數)分成若干組,每組中記錄的下標相差d.對每組中全部元素進行直接插入排序,然後再用乙個較小的增量(d/2)對它進行分組,在每組中再進行直接插入排序。
當增量減到1時,進行直接插入排序後,排序完成。
(2)例項:
3、簡單選擇排序
(1)基本思想:在要排序的一組數中,選出最小的乙個數與第乙個位置的數交換;
然後在剩下的數當中再找最小的與第二個位置的數交換,如此迴圈到倒數第二個數和最後乙個數比較為止。
(2)例項:
4、堆排序
(1)基本思想:堆排序是一種樹形選擇排序,是對直接選擇排序的有效改進。
堆的定義如下:具有n個元素的序列(h1,h2,...,hn),當且僅當滿足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...
,n/2)時稱之為堆。在這裡只討論滿足前者條件的堆。由堆的定義可以看出,堆頂元素(即第乙個元素)必為最大項(大頂堆)。
完全二叉樹可以很直觀地表示堆的結構。堆頂為根,其它為左子樹、右子樹。初始時把要排序的數的序列看作是一棵順序儲存的二叉樹,調整它們的儲存序,使之成為乙個堆,這時堆的根節點的數最大。
然後將根節點與堆的最後乙個節點交換。然後對前面(n-1)個數重新調整使之成為堆。依此類推,直到只有兩個節點的堆,並對它們作交換,最後得到有n個節點的有序序列。
從演算法描述來看,堆排序需要兩個過程,一是建立堆,二是堆頂與堆的最後乙個元素交換位置。所以堆排序有兩個函式組成。一是建堆的滲透函式,二是反覆呼叫滲透函式實現排序的函式。
(2)例項:
初始序列:46,79,56,38,40,84
建堆:交換,從堆中踢出最大數
剩餘結點再建堆,再交換踢出最大數
依次類推:最後堆中剩餘的最後兩個結點交換,踢出乙個,排序完成。
5、氣泡排序
(1)基本思想:在要排序的一組數中,對當前還未排好序的範圍內的全部數,自上而下對相鄰的兩個數依次進行比較和調整,讓較大的數往下沉,較小的往上冒。即:
每當兩相鄰的數比較後發現它們的排序與排序要求相反時,就將它們互換。
(2)例項:
6、快速排序
(1)基本思想:選擇乙個基準元素,通常選擇第乙個元素或者最後乙個元素,通過一趟掃瞄,將待排序列分成兩部分,一部分比基準元素小,一部分大於等於基準元素,此時基準元素在其排好序後的正確位置,然後再用同樣的方法遞迴地排序劃分的兩部分。
(2)例項:
上圖中將待排序列分成兩部分,一部分比基準元素小,一部分大於基準元素,然後對這兩部分重複上圖的求解過程。
(這只是快速排序的一種實現方式,個人認為比較容易理解)
7、歸併排序
(1)基本排序:歸併(merge)排序法是將兩個(或兩個以上)有序表合併成乙個新的有序表,即把待排序序列分為若干個子串行,每個子串行是有序的。然後再把有序子串行合併為整體有序序列。
(2)例項:
8、基數排序
(1)基本思想:將所有待比較數值(正整數)統一為同樣的數字長度,數字較短的數前面補零。然後,從最低位開始,依次進行一次排序。
這樣從最低位排序一直到最高位排序完成以後,數列就變成乙個有序序列。
(2)例項:
穩定性說明:排序前,2(或者更多)個相等的數在序列的前後位置順序和排序後它們在序列中的前後位置順序一樣。
例項:待排序數列:5,4,8,6,1,8,7,9
排序結果:1,4,5,6,7,8,8,9
穩定:1,4,5,6,7,8,8,9
不穩定:1,4,5,6,7,8,8,9
說明:對比紅色的8和紫色的8,看他們排序前後的位置。排序前,紅8在紫8前面,如果排序後紅8仍然在紫8前面,則排序演算法穩定,否則不穩定。
現在我們分析一下8種排序演算法的穩定性。
(請網友結合前面的排序基本思想來理解排序的穩定性(8種排序的基本思想已經在前面說過,這裡不再贅述)不然可能有些模糊)
(1)直接插入排序:一般插入排序,比較是從有序序列的最後乙個元素開始,如果比它大則直接插入在其後面,否則一直往前比。如果找到乙個和插入元素相等的,那麼就插入到這個相等元素的後面。
插入排序是穩定的。
(2)希爾排序:希爾排序是按照不同步長對元素進行插入排序,一次插入排序是穩定的,不會改變相同元素的相對順序,但在不同的插入排序過程中,相同的元素可能在各自的插入排序中移動,穩定性就會被破壞,所以希爾排序不穩定。
(3)簡單選擇排序:在一趟選擇,如果當前元素比乙個元素小,而該小的元素又出現在乙個和當前元素相等的元素後面,那麼交換後穩定性就被破壞了。光說可能有點模糊,來看個小例項:
858410,第一遍掃瞄,第1個元素8會和4交換,那麼原序列中2個8的相對前後順序和原序列不一致了,所以選擇排序不穩定。
(4)堆排序:堆排序的過程是從第n/2開始和其子節點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當然不會破壞穩定性。但當為n/2-1, n/2-2, ...
這些父節點擊擇元素時,有可能第n/2個父節點交換把後面乙個元素交換過去了,而第n/2-1個父節點把後面乙個相同的元素沒有交換,所以堆排序並不穩定。
(5)氣泡排序:由前面的內容可知,氣泡排序是相鄰的兩個元素比較,交換也發生在這兩個元素之間,如果兩個元素相等,不用交換。所以氣泡排序穩定。
(6)快速排序:在中樞元素和序列中乙個元素交換的時候,很有可能把前面的元素的穩定性打亂。還是看乙個小例項:
6 4 4 5 4 7 8 9,第一趟排序,中樞元素6和第三個4交換就會把元素4的原序列破壞,所以快速排序不穩定。
(7)歸併排序:在分解的子列中,有1個或2個元素時,1個元素不會交換,2個元素如果大小相等也不會交換。在序列合併的過程中,如果兩個當前元素相等時,我們把處在前面的序列的元素儲存在結果序列的前面,所以,歸併排序也是穩定的。
(8)基數排序:是按照低位先排序,然後收集;再按照高位排序,然後再收集;依次類推,直到最高位。有時候有些屬性是有優先順序順序的,先按低優先順序排序,再按高優先順序排序,最後的次序就是高優先順序高的在前,高優先順序相同的低優先順序高的在前。
基數排序基於分別排序,分別收集,所以是穩定的。
8種排序的分類,穩定性,時間複雜度和空間複雜度總結:
三種查詢演算法:順序查詢,二分法查詢(折半查詢),分塊查詢,雜湊表(以後談)
一、順序查詢的基本思想:
從表的一端開始,順序掃瞄表,依次將掃瞄到的結點關鍵字和給定值(假定為a)相比較,若當前結點關鍵字與a相等,則查詢成功;若掃瞄結束後,仍未找到關鍵字等於a的結點,則查詢失敗。
說白了就是,從頭到尾,乙個乙個地比,找著相同的就成功,找不到就失敗。很明顯的缺點就是查詢效率低。
適用於線性表的順序儲存結構和鏈式儲存結構。
計算平均查詢長度。
例如上表,查詢1,需要1次,查詢2需要2次,依次往下推,可知查詢16需要16次,
可以看出,我們只要將這些查詢次數求和(我們初中學的,上底加下底乘以高除以2),然後除以結點數,即為平均查詢長度。
設n=節點數
平均查詢長度=(n+1)/2
二、二分法查詢(折半查詢)的基本思想:
前提:(1)確定該區間的中點位置:mid=(low+high)/2
min代表區間中間的結點的位置,low代表區間最左結點位置,high代表區間最右結點位置
(2)將待查a值與結點mid的關鍵字(下面用r[mid].key)比較,若相等,則查詢成功,否則確定新的查詢區間:
如果r[mid].key>a,則由表的有序性可知,r[mid].key右側的值都大於a,所以等於a的關鍵字如果存在,必然在r[mid].
key左邊的表中。這時high=mid-1
如果r[mid].key
如果r[mid].key=a,則查詢成功。 (3)下一次查詢針對新的查詢區間,重複步驟(1)和(2) (4)在查詢過程中,low逐步增加,high逐步減少,如果high 平均查詢長度=log2(n+1)-1 注:雖然二分法查詢的效率高,但是要將表按關鍵字排序。而排序本身是一種很費時的運算,所以二分法比較適用於順序儲存結構。 為保持表的有序性,在順序結構中插入和刪除都必須移動大量的結點。因此,二分查詢特別適用於那種一經建立就很少改動而又經常需要查詢的線性表。 三、分塊查詢的基本思想: 二分查詢表使分塊有序的線性表和索引表(抽取各塊中的最大關鍵字及其起始位置構成索引表 )組成,由於表是分塊有序的,所以索引表是乙個遞增有序表,因此採用順序或二分查詢索引表,以確定待查結點在哪一塊,由於塊內無序,只能用順序查詢。 設表共n個結點,分b塊,s=n/b (分塊查詢索引表)平均查詢長度=log2(n/s+1)+s/2 (順序查詢索引表)平均查詢長度=(s2+2s+n)/(2s) 注:分塊查詢的優點是在表中插入或刪除乙個記錄時,只要找到該記錄所屬塊,就在該塊中進行插入或刪除運算(因塊內無序,所以不需要大量移動記錄)。它主要代價是增加乙個輔助陣列的儲存控制項和將初始表分塊排序的運算。 它的效能介於順序查詢和二分查詢之間 php5的優點 php5的最大特點是引入了物件導向的全部機制,並且保留了向下的相容性。程式設計師不必再編寫缺乏功能性的類,並且能夠以多種方法實現類的保護。另外,在物件的整合等方面也不再存在問題。使用php5引進了型別提示和異常處理機制,能更有效的處理和避免錯誤的發生。mysql fetch row,... 人在職場如同身處江湖,可以說是絕對的身不由己,到處潛伏著危機,到處埋伏著狙擊手,稍有不慎就有可能中招下馬,因此,身在職場最重要的是管住自己的 嘴 要懂得在什麼場合應該說什麼場面話,要懂得什麼話可以說而什麼話是絕對不可以說,尤其是某些職場禁語還是應該牢記在心,畢竟,祖輩教育的 禍從口出 是絕對有道理的... 箍筋加密區是對於抗震結構來說的。根據抗震等級的不同,箍筋加密區設定的規定也不同。一般來說,對於鋼筋混凝土框架的梁的端部和每層柱子的兩端都要進行加密。梁端的加密區長度一般取1.5倍的樑高。柱子加密區長度一般區1 6每層柱子的高度。但最底層 一層 柱子的根部應取1 3的高度 對於標準磚 240 115 ...PHP程式設計師必須掌握的知識
職場中必須知道的8條禁語
施工員必須知道的那些事