算法是在有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義明確的規(guī)則。通俗點(diǎn)說(shuō)，就是計(jì)算機(jī)解題的過(guò)程。在這個(gè)過(guò)程中，無(wú)論是形成解題思路還是編寫(xiě)程序，都是在實(shí)施某種算法。前者是推理實(shí)現(xiàn)的算法，后者是操作實(shí)現(xiàn)的算法。
一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：
1.有窮性： 一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束；
2.確切性： 算法的每一步驟必須有確切的定義；
3.輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫(huà)運(yùn)算對(duì)象的初始情況；
4.輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒(méi)有輸出的算法是毫無(wú)意義的；
5.可行性： 算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成。
合并排序（MERGE SORT）是又一類(lèi)不同的排序方法，合并的含義就是將兩個(gè)或兩個(gè)以上的有序數(shù)據(jù)序列合并成一個(gè)新的有序數(shù)據(jù)序列，因此它又叫歸并算法。它的基本思想就是假設(shè)數(shù)組A有N個(gè)元素，那么可以看成數(shù)組A是又N個(gè)有序的子序列組成，每個(gè)子序列的長(zhǎng)度為1，然后再兩兩合并，得到了一個(gè) N/2 個(gè)長(zhǎng)度為2或1的有序子序列，再兩兩合并，如此重復(fù)，值得得到一個(gè)長(zhǎng)度為N的有序數(shù)據(jù)序列為止，這種排序方法稱(chēng)為2—路合并排序。
例如數(shù)組A有7個(gè)數(shù)據(jù)，分別是： 49 38 65 97 76 13 27，那么采用歸并排序算法的操作過(guò)程如圖7所示：
初始值 [49] [38] [65] [97] [76] [13] [27]
看成由長(zhǎng)度為1的7個(gè)子序列組成
第一次合并之后 [38 49] [65 97] [13 76] [27]
看成由長(zhǎng)度為1或2的4個(gè)子序列組成
第二次合并之后 [38 49 65 97] [13 27 76]
看成由長(zhǎng)度為4或3的2個(gè)子序列組成
第三次合并之后 [13 27 38 49 65 76 97]
圖6 歸并排序算法過(guò)程圖
合并算法的核心操作就是將一維數(shù)組中前后相鄰的兩個(gè)兩個(gè)有序序列合并成一個(gè)有序序列。合并算法也可以采用遞歸算法來(lái)實(shí)現(xiàn)，形式上較為簡(jiǎn)單,但實(shí)用性很差。
合并算法的合并次數(shù)是一個(gè)非常重要的量,根據(jù)計(jì)算當(dāng)數(shù)組中有3到4個(gè)元素時(shí),合并次數(shù)
是2次,當(dāng)有5到8個(gè)元素時(shí),合并次數(shù)是3次,當(dāng)有9到16個(gè)元素時(shí),合并次數(shù)是4次，按照這一規(guī)律，當(dāng)有N個(gè)子序列時(shí)可以推斷出合并的次數(shù)是
X（2>=N,符合次條件的最小那個(gè)X）。
冒泡算法描述：
在解釋冒泡排序算法之前，先來(lái)介紹把10個(gè)數(shù)（放在數(shù)組A中）中最大的那個(gè)數(shù)放在最后位置上的一種算法。算法描述如下：
（1）從數(shù)組A[1]到A[10]，把相臨的兩個(gè)數(shù)兩兩進(jìn)行比較。即A[1]和A[2]比較，比較完后A[2]再與A[3]比較，……最后是A[9]和A[10]比較。
(2)在每次進(jìn)行比較的過(guò)程中，如果前一個(gè)數(shù)比后一個(gè)數(shù)大，則對(duì)調(diào)兩個(gè)數(shù)，也就是說(shuō)把較大的數(shù)調(diào)到后面，較小的調(diào)到前面。比如在第一次的比較中，如果A[1]比A[2]大則A[1]和A[2]的值就互換。下圖用6個(gè)數(shù)據(jù)來(lái)說(shuō)明以上的算法。
假設(shè)6個(gè)數(shù)據(jù)是：A[]=5 7 4 3 8 6
A[1] A[2] A[3] A[4] A[5] A[6]
5 7 4 3 8 6 第一次，A[1]=5和A[2]=7比較，7>5，不進(jìn)行對(duì)調(diào)。
5 7 4 3 8 6 第二次，A[2]=7和A[3]=4比較，4<7，進(jìn)行對(duì)調(diào)，
那么第二次比較完后的數(shù)據(jù)是5 4 7 3 8 6
5 4 7 3 8 6 第三次，A[3]=7和A[4]=3比較，3<7，進(jìn)行對(duì)調(diào)，
那么第三次比較完后的數(shù)據(jù)是5 4 3 7 8 6
5 4 3 7 8 6 第四次，A[4]=7和A[5]=8比較，8>7,不進(jìn)行對(duì)調(diào)。
5 4 3 7 8 6 第五次，A[6]=6和A[5]=8比較，6<8，進(jìn)行對(duì)調(diào)，
那么第五次也就是最后一次的結(jié)果是
5 4 3 7 6 8
*******************************************************
選擇排序算法描述：
在介紹選擇排序法之前先介紹一種把最小的數(shù)放在第一個(gè)位置上的算法，當(dāng)然也可以用前面所講的冒泡排序法，現(xiàn)在我們改用一種新的算法：其指導(dǎo)思想是先并不急于調(diào)換位置，先從A[1]開(kāi)始逐個(gè)檢查，看哪個(gè)數(shù)最小就記下該數(shù)所在的位置P，等一躺掃描完畢，再把A[P]和A[1]對(duì)調(diào)，這時(shí)A[1]到A[10]中最小的數(shù)據(jù)就換到了最前面的位置。算法的步驟如下：
1）、先假設(shè)A[1]中的數(shù)最小，記下此時(shí)的位置P=1；
2）、依次把A[P]和A[I]（I從2變化到10）進(jìn)行比較，每次比較時(shí)，若A[I]的數(shù)比A[P]中的數(shù)小，則把I的值賦給P，使P總是指向當(dāng)前所掃描過(guò)的最小數(shù)的位置，也就是說(shuō)A[P]總是等于所有掃描過(guò)的數(shù)最小的那個(gè)數(shù)。在依次一一比較后，P就指向10個(gè)數(shù)中最小的數(shù)所在位置，即A[P]就是10個(gè)數(shù)中最小的那個(gè)數(shù)；
3）把A[P]和A[1]的數(shù)對(duì)調(diào)，那么最小的數(shù)就在A[1]中去了，也就是在最前面了。
如果現(xiàn)在重復(fù)此算法，但每重復(fù)一次，進(jìn)行比較的數(shù)列范圍就向后移動(dòng)一個(gè)位置。即第二遍比較時(shí)范圍就從第2個(gè)數(shù)一直到第N個(gè)數(shù)，在此范圍內(nèi)找最小的數(shù)的位置P，然后把A[P]與A[2]對(duì)調(diào)，這樣從第2個(gè)數(shù)開(kāi)始到第N個(gè)數(shù)中最小數(shù)就在A[2]中了，第三遍就從第3個(gè)數(shù)到第N個(gè)數(shù)中去找最小的數(shù)，再把A[P]與A[3]對(duì)調(diào)……此過(guò)程重復(fù)N-1次后，就把A數(shù)組中N個(gè)數(shù)按從小到大的順序排好了。這種排序的方法就是選擇排序法
*****************************************************************
插入排序算法描述：
通過(guò)學(xué)習(xí)上述兩種方法可以了解排序的基本思想，也可以對(duì)任何一個(gè)無(wú)序數(shù)組作出從大到小（降序）或從小到大（升序）的排列?，F(xiàn)在假設(shè)有一個(gè)已經(jīng)有序的數(shù)據(jù)序列，要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個(gè)時(shí)候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中,從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)。
題目：A數(shù)組中有N個(gè)數(shù)據(jù)，按從小到大的順序排列，輸入一個(gè)數(shù)X，把X的值插入到數(shù)組A中，使得插入后的A數(shù)組仍然按從小到大排列。
那么這個(gè)問(wèn)題的解決算法就是：
1）、通過(guò)比較大小找到X應(yīng)插入的位置，假如應(yīng)該放在第I個(gè)位置；
2）、把從I開(kāi)始的（包括I）的所有數(shù)組元素依次向后移動(dòng)一個(gè)位置，即A[I+1]：=A[I]；
快速排序是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是：通過(guò)一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按次方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
假設(shè)要排序的數(shù)組是A[1]……A[N]，首先任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱(chēng)為一躺快速排序。一躺快速排序的算法是：
1）、設(shè)置兩個(gè)變量I、J，排序開(kāi)始的時(shí)候I：=1，J：=N；
2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A[1]；
3）、從J開(kāi)始向前搜索，即由后開(kāi)始向前搜索（J：=J-1），找到第一個(gè)小于X的值，兩者交換；
4）、從I開(kāi)始向后搜索，即由前開(kāi)始向后搜索（I：=I+1），找到第一個(gè)大于X的值，兩者交換；
5）、重復(fù)第3、4步，直到I=J；
例如：待排序的數(shù)組A的值分別是：（初始關(guān)鍵數(shù)據(jù)X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
49 38 65 97 76 13 27
進(jìn)行第一次交換后： 27 38 65 97 76 13 49
( 按照算法的第三步從后面開(kāi)始找
進(jìn)行第二次交換后： 27 38 49 97 76 13 65
( 按照算法的第四步從前面開(kāi)始找>X的值，65>49,兩者交換，此時(shí)I：=3 )
進(jìn)行第三次交換后： 27 38 13 97 76 49 65
( 按照算法的第五步將又一次執(zhí)行算法的第三步從后開(kāi)始找
進(jìn)行第四次交換后： 27 38 13 49 76 97 65
( 按照算法的第四步從前面開(kāi)始找大于X的值，97>49,兩者交換，此時(shí)J：=4 )
此時(shí)再執(zhí)行第三不的時(shí)候就發(fā)現(xiàn)I=J，從而結(jié)束一躺快速排序，那么經(jīng)過(guò)一躺快速排序之后的結(jié)果是：27 38 13 49 76 97 65，即所以大于49的數(shù)全部在49的后面，所以小于49的數(shù)全部在49的前面。
快速排序就是遞歸調(diào)用此過(guò)程——在以49為中點(diǎn)分割這個(gè)數(shù)據(jù)序列，分別對(duì)前面一部分和后面一部分進(jìn)行類(lèi)似的快速排序，從而完成全部數(shù)據(jù)序列的快速排序，最后把此數(shù)據(jù)序列變成一個(gè)有序的序列，根據(jù)這種思想對(duì)于上述數(shù)組A的快速排序的全過(guò)程如圖6所示：
初始狀態(tài) {49 38 65 97 76 13 27}
進(jìn)行一次快速排序之后劃分為 {27 38 13} 49 {76 97 65}
分別對(duì)前后兩部分進(jìn)行快速排序 {13} 27 {38}
結(jié)束 結(jié)束 {49 65} 76 {97} 49 {65} 結(jié)束
結(jié)束
*************************************************************************
圖6 快速排序全過(guò)程
快速排序的算法描述
1）、設(shè)有N（假設(shè)N=10）個(gè)數(shù)，存放在S數(shù)組中；
2）、在S[1。。N]中任取一個(gè)元素作為比較基準(zhǔn)，例如取T=S[1]，起目的就是在定出T應(yīng)在排序結(jié)果中的位置K，這個(gè)K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的數(shù)都小于S[K]，在S[K]以后的數(shù)都大于S[K]；
3）、利用分治思想（即大化小的策略）可進(jìn)一步對(duì)S[1。。K-1]和S[K+1。。N]兩組數(shù)據(jù)再進(jìn)行快速排序直到分組對(duì)象只有一個(gè)數(shù)據(jù)為止。
如具體數(shù)據(jù)如下，那么第一躺快速排序的過(guò)程是：
數(shù)組下標(biāo)： 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
I J
（1） 36 36 18 53 72 30 48 93 15 45
（2） 36 36 18 45 72 30 48 93 15 53
（3） 36 36 18 15 72 30 48 93 45 53
（4） 36 36 18 15 45 30 48 93 72 53
（5） 36 36 18 15 30 45 48 93 72 53

最新評(píng)論