易語言常用算法設(shè)計(jì)圖書(編輯修改稿)
2024-08-31 01:15 本頁面
【文章內(nèi)容簡(jiǎn)介】 ，因此若表中存在等于待查值的值，則該值必定是在中間值左邊的子表中，故新的查找區(qū)是左子表。（2）類似地，若中間值小于待查值，則要查找的值必在中間值的右子表中，即新的查找區(qū)間是右子表。下一次查找是針對(duì)新的查找區(qū)間進(jìn)行的。因此，從初始的查找區(qū)間開始，每經(jīng)過一次與當(dāng)前查找區(qū)間的中點(diǎn)位置上的節(jié)點(diǎn)的比較，就確定是否成功，不成功則當(dāng)前的查找區(qū)間就縮小一半。這一過程重復(fù)直至找到中間值的值，或者直至當(dāng)前的查找區(qū)間為空（即查找失?。r(shí)為止。數(shù)據(jù)越多越能體現(xiàn)對(duì)分查找法的好處。其實(shí)，每次插入都是比較大小安排插入位置，為了插到大于和小于數(shù)值的中間。如50、559，如果給一個(gè)56，當(dāng)然知道插入到55后面，以前的代碼是從4開始一一比較，而我們可以直接把數(shù)組對(duì)分，比一下是比前一部分大，還是比后一部分大，再在剩余結(jié)果對(duì)分比較，再對(duì)分……。逐一比較平面需要比較5次，對(duì)分只需要比較2次，數(shù)據(jù)越多，越能體現(xiàn)。代碼如下： 冒泡排序是最簡(jiǎn)單也是最經(jīng)典的。這種方法的基本思想是，將待排序的元素看作是豎著排列的“氣泡”，較小的元素比較輕，從而要往上?。ㄏ喾矗^大的元素比較重，從而要往下沉）。在冒泡排序算法中我們要對(duì)這個(gè)“氣泡”序列處理若干遍。所謂一遍處理，就是自底向上檢查一遍這個(gè)序列，并同時(shí)注意兩個(gè)相鄰的元素的須序是否正確。如果發(fā)現(xiàn)兩個(gè)相鄰元素的須序不對(duì)，即“輕”的元素在下面，就交換它們的位置。顯然，處理一遍之后，“最輕”的元素就浮到了最高位置（或最重的元素沉到最低位置）；處理兩遍之后，“次輕”的元素就浮到了次高位置。在第二遍處理時(shí)，由于最高位置上的元素已是“最輕”元素，所以不必檢查。一般地，第i遍處理時(shí)，不需檢查第i高位置以上的元素，因?yàn)榻?jīng)過前面i1遍的處理，它們已正確地排好序了。 關(guān)鍵在于每循環(huán)一遍都記錄交換的次數(shù)，避免下次不必要的比較，還要記住最后交換的位置，這個(gè)位置以后的數(shù)據(jù)下次可以在之前比較。比如現(xiàn)在有一組數(shù)據(jù)，第一次先比較所有的數(shù)據(jù)，而后記下最后比較位，而每次如果有數(shù)據(jù)交換，就繼續(xù)循環(huán)比較。而比較的最后位置則是循環(huán)的最大值。代碼如下：1. 直接插值排序直接插入排序的基本思想是：每次把一個(gè)待排序的節(jié)點(diǎn)，按其關(guān)鍵字的大小插入到前面已排序好節(jié)點(diǎn)中，直到全部節(jié)點(diǎn)插入完畢。兩個(gè)重要概念。有序區(qū)：是指順序表中已排序好的部分。無序區(qū)：即表中未進(jìn)行排序的區(qū)域。例如，一維數(shù)組[2，5，6，2，9，5，47] 有序區(qū)的范圍是：【1，3】（從1到3節(jié)點(diǎn)），無序區(qū)是：【4，7】（從4到7節(jié)點(diǎn)）。對(duì)于任何一個(gè)節(jié)點(diǎn)為n（n1)的順序表,其初始有序區(qū)的范圍是【1，1】無序區(qū)的范圍是【2，n】。插入排序的基本思想就是不斷增大有序區(qū)，減小無序。直到無序區(qū)消失。直接插入排序的原理：每次將無序區(qū)的第一個(gè)節(jié)點(diǎn)插入到有序區(qū)中。例如，無序數(shù)組[8，5，6，4，3，9，4]，其初始有序區(qū)【1，1】,無序區(qū)【2，7】。第一次插入運(yùn)算，將無序區(qū)第一個(gè)節(jié)點(diǎn)“5”插到前面的有序區(qū)中。運(yùn)算后數(shù)組為[5,8,6,4,3,9,4],有序區(qū)為【1，2】無序區(qū)為【3，7】。第二次插入運(yùn)算，將無序區(qū)的第一個(gè)節(jié)點(diǎn)“6”插入到前面的有序區(qū)中，運(yùn)算后的數(shù)組為[5,6,8,4,3,9,4],其有序區(qū)為【1，3】，無序區(qū)減小成【4，7】。如此重復(fù)，經(jīng)過6次插入運(yùn)算，有序區(qū)成為【1，7】，無序區(qū)消失。此數(shù)組成為有序數(shù)組。代碼如下：本段代碼用到了查找算法和插入算法。直接插入排序法的代碼在執(zhí)行過程中，大部分時(shí)間是消耗在查找插入點(diǎn)位置和移動(dòng)節(jié)點(diǎn)上。節(jié)點(diǎn)的移動(dòng)是必須的，此類算法是無法減少移動(dòng)次數(shù)的，除非是用新的算法。而每次都從無序區(qū)首（即表的第一個(gè)節(jié)點(diǎn)）開始尋找插入點(diǎn)的過程是完全沒有必要的，可以用我們講過的二分查找法優(yōu)化此過程。以下是實(shí)現(xiàn)代碼。上面對(duì)直接插入排序進(jìn)行了優(yōu)化，我們暫且把優(yōu)化算法稱為二分直接插入排序，這種算法僅僅是對(duì)尋找插入點(diǎn)的過程做了優(yōu)化。如果我們能找到另一種方法，可同時(shí)減少尋找插入點(diǎn)的次數(shù)和移動(dòng)節(jié)點(diǎn)的次數(shù)，就可顯著的提高排序的運(yùn)算速度。以下介紹的希爾排序算法是直接插入排序法的一種變種，它能有效的減少這兩個(gè)方面的運(yùn)算量，從而顯著的提高排序操作的運(yùn)算速度。原理： 先取一個(gè)小于節(jié)點(diǎn)數(shù)的整數(shù)k作為分組單位，把表上的所有相距k的節(jié)點(diǎn)邏輯上看成一組。在個(gè)組內(nèi)進(jìn)行直接插入排序；減小k的取值，把表上的所有相距k的節(jié)點(diǎn)邏輯上看成一組。在個(gè)組內(nèi)進(jìn)行直接插入排序；重復(fù)以上步驟；最后一次k取1，即對(duì)整個(gè)表做直接插入排序。其中k稱為增量，增量的取值集合稱為增量表。例，無序數(shù)組[4,5,8,2,6,8,9,2,4,5,1,6,1,5,4,2] 增量表我們?nèi)〕伞?，3，1”（k的取值集合）。(1) 當(dāng)k＝5時(shí)，表上的邏輯分組情況為
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1