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