排序算法外文翻譯

1、<p><b>　　中文3355字</b></p><p><b>　　畢 業(yè) 論 文</b></p><p>　　外 文 文 獻(xiàn) 譯 文 及 原 文</p><p>　　學(xué) 生： </p><p>　　學(xué) 號(hào)：

2、 </p><p>　　院 （系）： 理學(xué)院 </p><p>　　專(zhuān) 業(yè)： 信息與計(jì)算科學(xué) </p><p>　　指導(dǎo)教師： </p><p>　　2014 年 6 月 20 日</p><p><b>　　排序&

3、lt;/b></p><p><b>　　1 內(nèi)部排序</b></p><p>　　目前已經(jīng)發(fā)明了許多不同的排序算法，我們將在本書(shū)討論其中大約25個(gè)算法。這樣頗使人驚訝的眾多方法，實(shí)際上還只是迄今已經(jīng)想出算法的一小部分；在我們的討論中，將略取許多現(xiàn)在已經(jīng)被廢棄的方法，或者緊緊的提及他們。為什么會(huì)有那么多的排序算法呢？在計(jì)算機(jī)的程序設(shè)計(jì)中，常有“為什么會(huì)有這樣多的

4、x方法呢？”的問(wèn)題，其中x就是某個(gè)問(wèn)題的集合。這個(gè)問(wèn)題的答案是：每種方法都有它的優(yōu)點(diǎn)和缺點(diǎn)，對(duì)于某些數(shù)據(jù)和硬件的配置來(lái)說(shuō)，它就有可能超過(guò)其它的方法?？上?，還不知道“最好”的排序方法；目前許多最好的方法，都是針對(duì)的、特定的機(jī)器，根據(jù)特定的目的，對(duì)特定對(duì)象進(jìn)行排序所得到的。用Rudyard Kipling的話(huà)說(shuō)：“有69種進(jìn)行部落安置的方法，而且它們每一種都是對(duì)的?！?lt;/p><p>　　一個(gè)好的想法是學(xué)習(xí)每種排序方

5、法，它能幫助你具體的應(yīng)用做出明智的選擇。幸而，學(xué)習(xí)這些算法并不是一項(xiàng)艱難的任務(wù)，因?yàn)樗麄兌家杂腥さ姆绞较嗷リP(guān)聯(lián)著。</p><p>　　在本章開(kāi)始時(shí)，已經(jīng)定義了將在排序研究中使用的基本術(shù)語(yǔ)和符號(hào)：記錄</p><p><b>　?。?-1）</b></p><p>　　有待安排你鍵碼的非減次序進(jìn)行排序，實(shí)質(zhì)上要求找出一個(gè)排列使得</p&g

6、t;<p><b>　?。?-2）</b></p><p>　　在本節(jié)中，我們討論內(nèi)部排序，此時(shí)，有待排序的記錄個(gè)數(shù)足夠小，以致整過(guò)過(guò)程都能在一臺(tái)計(jì)算機(jī)的高速存儲(chǔ)器中實(shí)現(xiàn)。</p><p>　　在某些情況下，會(huì)要求在存儲(chǔ)器中對(duì)這些記錄物理地重新排列，使得它們的鍵碼按次序排列。但在另外的情況下，則可能只要指明這個(gè)排序的某個(gè)輔助表就能夠了。如果每個(gè)記錄或鍵碼

7、要占用相當(dāng)多的計(jì)算機(jī)存儲(chǔ)器，則構(gòu)造一個(gè)新的指向記錄的鏈接地址表，并處理這些鏈表地址，而不是到處移動(dòng)龐大的記錄，通常更好些。這種方式稱(chēng)為地址表排序。如果鍵碼很短，但是記錄的附屬信息很長(zhǎng)，則為了獲得更高的速度，這個(gè)鍵碼即可用作鏈接地址，這就是所謂的鍵碼排序。另外一種排序方案利用了包括在每個(gè)記錄中的一個(gè)輔助鏈接字段；鏈接的方式是使這些記錄最終被鏈接在一起形成一個(gè)直接的線(xiàn)性表，每個(gè)鏈接指向下一個(gè)記錄，這就是所謂的表排序。</p>

8、<p>　　在用地址表方法或表方法進(jìn)行排序之后，諸記錄可像所希望的那樣，重新排成遞增的順序。只要求足夠容納所有記錄的新區(qū)域。后一方法通常比頭一個(gè)方法快兩倍，但是幾乎要兩倍的存儲(chǔ)空間。在許多應(yīng)用中，全然不需要移動(dòng)記錄，因?yàn)閷?duì)于隨后的尋址操作而言，使用鏈接字段通常已經(jīng)足夠了。 </p><p>　　我們將通過(guò)4個(gè)方面來(lái)說(shuō)明將要深入討論的所有排序方法，即</

9、p><p>　　a）算法的一個(gè)英語(yǔ)語(yǔ)言描述；</p><p><b>　　b）一個(gè)框圖</b></p><p>　　c）一個(gè)MIX程序；</p><p>　　d）一個(gè)排序方法的實(shí)例，它應(yīng)用與某個(gè)16個(gè)數(shù)的集合。 </p><p>　　為了方便起見(jiàn)，MIX程序通常都假定鍵碼是數(shù)值，并且能放到一個(gè)單子中

10、去；有時(shí)，甚至把鍵碼限制為一個(gè)字的一部分。次序關(guān)系“<”將是通常的算術(shù)次序；記錄將只由鍵碼</p><p>　　組成，而沒(méi)有附屬的信息。這些假定使得程序更短和更容易理解。讀者應(yīng)當(dāng)發(fā)現(xiàn)，使用地址表排序或表排序，將通過(guò)MIX程序進(jìn)行。 </p><p>　　1.1 通過(guò)計(jì)數(shù)進(jìn)行排序 </p><p>　　作為研究?jī)?nèi)部排序的一個(gè)簡(jiǎn)單示例，考慮在本章開(kāi)頭的“計(jì)數(shù)”思

11、想。這個(gè)簡(jiǎn)單的方法是這樣一個(gè)思想為基礎(chǔ)的，即在最后排好序的序列中，第j個(gè)鍵碼恰恰大于（j-1）個(gè)其它鍵碼，換言之。如果知道某個(gè)鍵碼確實(shí)超過(guò)27個(gè)其它鍵碼，而且沒(méi)有兩個(gè)鍵碼相同，則在排序之后對(duì)應(yīng)的記錄應(yīng)當(dāng)進(jìn)入位置28。所以，這個(gè)思想是比較每對(duì)鍵碼，計(jì)算有多少個(gè)鍵碼小于每一個(gè)特地給的鍵碼。</p><p>　　進(jìn)行這些比較的明顯方式是</p><p><b>　　對(duì)于</b&g

12、t;</p><p><b>　　對(duì)于</b></p><p>　　但容易看出，這些比較中有一半以上是多余的，因?yàn)闆](méi)有必要把一個(gè)鍵碼同它自己進(jìn)行比較。沒(méi)有必要比較Ka和Kb。我們只需要比較</p><p><b>　　對(duì)于</b></p><p><b>　　對(duì)于</b><

13、;/p><p>　　只需比較Ki和Kj。因此導(dǎo)出了下列算法。</p><p><b>　　算法c</b></p><p>　　本算法通過(guò)一張輔助表COUNT[1],......,COUNT[N],，對(duì)于小于一個(gè)給定鍵碼的鍵碼個(gè)數(shù)進(jìn)行計(jì)數(shù)，來(lái)實(shí)現(xiàn)用鍵碼對(duì)記錄進(jìn)行排序，算法結(jié)束時(shí)，COUNT[j]+1來(lái)確定Ri的最后位置。</p><

14、;p>　　C1：[清空COUNT] 把COUNT[1]至COUNT[N]都置成0。</p><p>　　C2：[對(duì)i進(jìn)行循環(huán)] 對(duì)i=N，N-1,....2實(shí)施步驟C3，然后結(jié)束次算法。</p><p>　　C3：[對(duì)j進(jìn)行循環(huán)] 對(duì)j=i-1，i-2,...,1實(shí)施步驟C4.</p><p>　　C4：[比較Ki和Kj] 如果Ki<Kj，則COUNT[

15、j]加1，否則COUNT[i]+1。</p><p>　　注意：次算法不涉及記錄的移動(dòng)，它類(lèi)似地址表排序，因?yàn)镃OUNT表確定這些記錄最后安排，但是由于COUNT[j]高速我們往何處移動(dòng)Rj，而不是哪一個(gè)記錄應(yīng)當(dāng)被移動(dòng)Ri的位置，故它與地址表排序略有不同。</p><p>　　通過(guò)計(jì)數(shù)進(jìn)行排序，還有另外一個(gè)方法，從有效的觀(guān)點(diǎn)看，它十分重要的：它主要應(yīng)用于許多相同的鍵碼出現(xiàn)，且所有的鍵碼都落

16、入范圍u≤kj≤v的情況，其中（v-u）很小。這些假定看來(lái)十分嚴(yán)格的限制，但是事實(shí)上將看到這一思想有不少的應(yīng)用。列如，如果把這個(gè)算法的應(yīng)用與鍵碼的頭幾位數(shù)，而不是整個(gè)鍵碼，則這個(gè)文件被部分地排序，而且這項(xiàng)任務(wù)將相當(dāng)簡(jiǎn)單。</p><p>　　1.2 通過(guò)插入進(jìn)行排序</p><p>　　有一類(lèi)重要的排序技術(shù)，是以1.2節(jié)開(kāi)頭處提到的“玩橋牌者”的方法為基礎(chǔ)的，在考察記錄Rj之前，假定以前的

17、記錄已經(jīng)排好序，然后已經(jīng)把Ri插入到已經(jīng)排好的諸多記錄的適當(dāng)位置。這個(gè)基本主題可以由若干有趣的變形。</p><p>　　1.2.1 直接插入</p><p>　　最簡(jiǎn)單的插入排序也是最顯然的。假定，而且已經(jīng)把記錄重新排好序，使得</p><p>　　把新鍵碼Kj依次地和Kj-1,...,k3,k2..進(jìn)行比較，直到發(fā)現(xiàn)Rj應(yīng)當(dāng)插入到Ri和Ri+1處。如下列算法所示

18、那樣，宜于把比較和移動(dòng)操作組合在一起，互相穿插，由于Rj“被安放到適當(dāng)?shù)膶哟沃袇^(qū)”，這種排序方式通常稱(chēng)為篩選或陷入技術(shù)。</p><p>　　算法S（直接插入排序）重新安排記錄到適當(dāng)位置；在完成排序之后，它們的鍵碼是有序的，即有。</p><p>　　S1 [對(duì)j進(jìn)行循環(huán)] 對(duì)于j=2,3,...,N實(shí)施步驟S2到S5；然后終止本算法。</p><p>　　S2 [

19、給i，K，R賦值] 置i←j-1，K←Kj，R←Rj</p><p>　　S3 [比較K:Ki] 如果則轉(zhuǎn)向步驟S5.</p><p>　　S4 [移動(dòng)Ri，i減值] 置Ri+1←Ri，然后i←i-1。如果i>0，則返回到步驟S3。</p><p>　　S5 [R進(jìn)入Ri+1] 置Ri+1←R。</p><p>　　1.2.2 二叉插入

20、和兩路插入</p><p>　　在一個(gè)直接插入排序期間，在處理第j個(gè)記錄時(shí)，平均說(shuō)來(lái)要把它的鍵碼大約同1/2j個(gè)此前已排好的鍵碼進(jìn)行比較，因此所實(shí)施比較的總數(shù)大約是1/2（1+2+3+...+N）=1/4N2,當(dāng)N適當(dāng)大時(shí)，這就已經(jīng)非常之大了。在6.2.1小節(jié)，將研究“二分查找”技術(shù)，該技術(shù)使我們能夠在僅僅lgN次仔細(xì)選擇的比較之后，就指出在那里插入第j項(xiàng)。例如，當(dāng)插入第64個(gè)記錄時(shí)，可以由對(duì)K64和K32進(jìn)行比

21、較開(kāi)始。如果是小于，則就把它同K16進(jìn)行比較，但如果是大于，則就把它同K65進(jìn)行比較，等等。于是僅僅做6次比較之后，就可知道R64應(yīng)查如得位置。插入所有N項(xiàng)所作的比較總數(shù)就大學(xué)時(shí)NlgN，這是對(duì)于1/4N2的實(shí)質(zhì)性的改進(jìn)。而6.2.1小節(jié)表示，它早在1946年就由John Mauchly在計(jì)算機(jī)排序的第一個(gè)公開(kāi)討論中述及。</p><p>　　二叉插入的困難時(shí)，它只解決問(wèn)題的一半。在已經(jīng)發(fā)現(xiàn)記錄Rj應(yīng)插入到那里之

22、后，仍然需要移動(dòng)大的1/2j個(gè)此前已排序好的記錄，以便Ri騰出位置，所以總共的運(yùn)行時(shí)間實(shí)質(zhì)上仍同N2成正比。</p><p>　　當(dāng)然，一個(gè)靈巧的程序員可以相處各種方式來(lái)減少所需要移動(dòng)的數(shù)量；頭一個(gè)這樣的技巧，如表2所示，是早在50年代時(shí)就提出的，表中排序的頭一項(xiàng)被放置在一個(gè)輸出區(qū)域的中心，而且通過(guò)向右或向左移動(dòng)騰出空間。此法比普通二叉插入節(jié)省一半運(yùn)行時(shí)間，其代價(jià)是程序稍微復(fù)雜一點(diǎn)，使用此法時(shí)，還可以不必使用N個(gè)

23、記錄所需要的更多的空間；但對(duì)于這個(gè)“兩路”插入的方法，將不作更詳細(xì)的敘述因?yàn)橐延懈嘤腥さ姆椒ā?lt;/p><p>　　1.2.3 Shell方法</p><p>　　如果有這樣的一份排序算法，它一次只把諸多項(xiàng)目移動(dòng)一個(gè)位置，則它的平均運(yùn)行時(shí)間最好也是同N2的成比例。因?yàn)樵谶@個(gè)排序過(guò)程中每個(gè)記錄都必須平均遍歷1/3N個(gè)位置。因此，如果直接對(duì)插入作實(shí)質(zhì)性的改進(jìn)，就需要一種新原理，它是這些記錄作

24、長(zhǎng)距離的跳躍，而不是一些短促的小步移動(dòng)。</p><p>　　這樣一個(gè)方法是由Donald.L.Shell于1959年提出的，我們稱(chēng)它為Shell排序，表3說(shuō)明該法的一般想法：首先把這16個(gè)記錄分成8組即（R1，R9），（R2，R10），...，（R8，R16）。分別對(duì)每組記錄進(jìn)行排序。使我們進(jìn)到表3的第二行，這稱(chēng)為“第一次掃描”。</p><p><b>　　表3 增量遞減排序

25、</b></p><p>　　Shell排序也叫做“減少增量的排序”，因?yàn)槊恳槐橥ㄟ^(guò)增量h來(lái)確定，使得我們對(duì)相距h個(gè)單位進(jìn)行排序。任何序列h1，hi-1，..，hn都可以使用此方法，只要最后的增量h0=1就行。</p><p><b>　　小結(jié)</b></p><p>　　既然我們已經(jīng)接近著極為冗長(zhǎng)的一章結(jié)尾，我們最好“整理出”已研

26、究過(guò)的最為重要的事實(shí)。</p><p>　　用于排序的一個(gè)算法，是一個(gè)這樣的過(guò)程，它重新安排一個(gè)文件的所有記錄，使得其碼處于遞增的次序，這有序的排列是有用的，因?yàn)樗严嗤挠涗浄诺揭黄?，允許有效的處理按同一個(gè)鍵碼排好的多個(gè)文件，這導(dǎo)致了有效的檢索方法，而且是計(jì)算機(jī)的刪除看上去不那么的混亂。如果無(wú)論是對(duì)那一種應(yīng)用，或無(wú)論正在使用什么樣的計(jì)算機(jī)，僅僅有一兩種排序方法，它比所有的排序方法都好，那么，事情倒好結(jié)局，事實(shí)上

27、，每種方法都有各自的優(yōu)點(diǎn)。因此所有的方法都要去記，因?yàn)樵谔氐氐沫h(huán)境中，它們是最好的。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] Bell，D．The principles of sorting．The Computer Journal 1 (1958)：71–77．</p><p>　　[2] Bose，R. C

28、，and Nelson，R.J．A sorting problem．Journal of the ACM (JACM) 9，2 (1962)：28–296．</p><p>　　[3] Halstead，M. H．Elements of Software Science．Operating．a(chǎn)nd Programming Systems Series，vol．7．Elsevier, 1977：71–77．<

29、/p><p><b>　　Sorting</b></p><p>　　1 Internal Sorting</p><p>　　Many different sorting algorithms have been invented,and we will be discussing about 25 of them in this book. T

30、his rather alarming number if methods is actually only a fraction the algorithms that have been devised so far;many methods which are now obsolete will be omitted from our discussiong,ir mentioned only briefly why are th

31、ere so many sorting methods ? For computer programming this is a special case of question,”why are there so many x methods?”, where x ranges over the set of problems; an</p><p>　　It is a good idea to learn t

32、he characteristics of each sorting method, so that an inerlligent choice can be made for particular applications Fortunately,it is not a formidable task to learn these algorithms,since they are inerrelated in intersting

33、ways.</p><p>　　At the beginning of this chaper we define the basic terminnology and notation to be used in our study of sorting: the records</p><p><b>　　(1-1)</b></p><p>

34、;　　Are sorting into nondereasing order of their keysesentially by discovering a permutation p(1) p(2)...p(N) such that </p><p><b>　?。?-2）</b></p><p>　　In the present section we are c

35、oncerned with inernal sorling ,when the number of records to be sorting is small enough that the entire process can be performed in a computers high-speed memory.</p><p>　　In some cases will want records to

36、be physiscally rearranged in memory so that their keys are in order ,while in orher cases in may be sufficient merely to have an auxiliary table of some sort which specifies the permutation. If the records and/or the key

37、s each take up quite a few table words of computer memoty , it is often better to make up a new table of link addresses whic point to the records, and to manipulate these link addresses instead of moving the bulky record

38、s around. This method is </p><p>　　All of sorting methods which we shall examine “in depth” will be illustrate in four ways,by means of</p><p>　　a) an English-language description of the algotit

39、hm,</p><p>　　b) flow diagram,</p><p>　　c) a MIX program,</p><p>　　d) an example of the sorting method applied to a given set of number.</p><p>　　An analysis of the runn

40、ing time of each sorting will be give with the MIX programs.</p><p>　　1.1 Sorting by counting</p><p>　　As a simple example of the way in which we shall study inernal sorting methods,lect us cons

41、ider the “ounting” idea mentioned near the beginning of this secion. This simple method is based on the idea that the jth key in the final sorted sequence is greater than exactly (j--1) of the other keys.Putting this ano

42、ther way.if we know that a certain key exceeds exactly 27 others,the corresponding record should go into position 28 after sorting.So the idea is to compare each pair of keys,counting how </p><p>　　The obbi

43、ous way to do the comparisons is to</p><p><b>　　. For </b></p><p><b>　　For </b></p><p>　　But it is easy to see that over half of these comparison are redund

44、at,since it is unnessary to compare a key with itself, and it is unnessary to compare Ka with Kb and later to compare ..with....we need merely to</p><p><b>　　For </b></p><p><b>

45、;　　For </b></p><p>　　Algorithm c(comparison counting) </p><p>　　This algorithm sorts COUNT[1],...,COUNT[N] on the keys by maintaining less than a given key . After the conclusion of the a

46、lgorithm,count[j]+1 specifies the final position of record</p><p>　　C1[clear Counts] Set Count[1] through COUNT[N] to zero.</p><p>　　C2[Loop on i.] Perform step C3,for i = N,N-1,...,2;then termi

47、nate the algorithm.</p><p>　　C3.[Loop on j.] Perform step C4,for j = i - 1,i - 2,...,1.</p><p>　　C4.[Compare Ki,Kj.] If Ki<Kj,increase COUNT[j] by 1;otherwise,increase COUNT[i] by 1.</p>

48、;<p>　　Note that this algorithm involves no movement of records.It is similar to an address table sort,since the COUNT table specifies the final arrangement of records;but it is somewhat differrent because COUNT[j

49、] tells us where to move Rj,instead of indicating which record should be moved into the place of Rj.(Thus the “inverse” of the permutation p(1)...p(n) is specified in the COUNT table;see Section 1.1.1).</p><p&

50、gt;　　In our discussion preceding this algorithm we failed to consider the posibility of equal keys.This is a potentially serious omission,for if equal keys complicated to equal COUNTs the final rearrangement of records w

51、ould be rather complicated.Fortunately,as exercise 2 shows,Algorithm C gives the correct result no matter how many equal keys are present.</p><p>　　Program C(Comparison counting).</p><p>　　The f

52、ollowing MTX implementation of Algorithm C assumes that Rj is stored in location INPUT+j,and COUNT[j] in location COUNT + j,for 1≤j≤N;rI1=i;rI2=j;rA=Ki=Ri;rX=COUNT[i].</p><p>　　The running time of this progr

53、am is 13N+6A+5B-4 units,where N is the number of records;A is the number of choices of two things from a set of N objects,namely ()=(N2-N)/2。</p><p>　　1.2 Sorting by Insertion </p><p>　　One of i

54、mportant families of sorting techniques is based on the “bridge player” method mentioned near the beginning of Section 1.2: Before examing record Rj,we assume that the preceding recordshave aready been sorted; then we in

55、sert Ri into its proper place among the previously sorted records. Several interesting variations on basic theme are possible.</p><p>　　1.2.1 Straight insertion</p><p>　　The simplest insertion s

56、ort is most obvious one.Assume that 1<j≤N and that record have been rearranged so that </p><p>　　We compare the way key Kj with Kj-1,...,k3,k2..,in turn,until discovering that Ri should be inserted betwee

57、n records Ri and Ri+1;then we move records. </p><p>　　Algorithm S(Straight insertion sort). Records are rearranged in place; after sorting is complete,their keys will be in order,.</p><p>　　S1.[

58、Loop on j] Perform steps S2 through S5 for j=2,3,..,N; then terminate the algorithem.</p><p>　　S2.[Set up i,K,R] Set i←j-1，K←Kj，R←Rj</p><p>　　S3.[Compare K,Ki] If K≥Ki go to S5.</p><p

59、>　　S4.[Move Ri,decrease j] Set Ri+1←Ri,then i←i-1.If i>0，go back S3.</p><p>　　S5.[R into Ri+1] Set Ri+1←R.</p><p>　　1.2.2 Binary insertion and two-way insertion.</p><p>　　Whil

60、e the jth record is being pracessed during a straight insertion sort,we compare its key with about 1/2j of the previously sorted keys,on the average;therefore the total number of comparisons performed comes to about 1/2(

61、1+2+...+N)≈1/2N2,and this gets very large when N is only moderately large. In Section 6.2.1 we shall study “Binary search” techniques ,which show where to insert the jth item after only about log2j well-chosen comparison

62、s have been made.For example ,when inserting the 64th re</p><p>　　The unfortunate difficulty with binary insertion is that it sovles only half of the problem; after we we have found where record Rj is to be

63、inserted, we still need to move about 1/2*j of the previously sort records in order to make room for Rj，so the total running time is still essentially proportional to N2。</p><p>　　Of course, a clever program

64、mer can think of various ways to reduce the amount of moving that is necessary; the first such trick, propose early in the 1950’s, is illustrated in table.Here the first item is placed in the center of an output area, an

65、d space is made for subsequent items by moving to the right or to the left, whichever is most convenient. This saves about half the running time of ordinary binary insertion, at the expense of a somewhat more complicated

66、 program, It is possible to use t</p><p>　　1.2.3 Shell’s method</p><p>　　If we have a sorting algorithm which moves items only one position at a time, its average running time will be,at best,pr

67、oportional to N2, since each record must travel an average of about 1/3*N positions during the sorting process. Therefore,if we want to make substantial improvements over straight insertion, we need some mechanise by whi

68、ch the records can take long leaps instead of short steps.</p><p>　　Such a method was proposed in 1950 by Donald L.Shell,we shall call it the diminishing increment sort.Table 3 illustrates the general idea b

69、ehind his method; Fist we divide the 16 records into 8 groups of two each,（R1，R9），（R2，R10），...，（R8，R16）.Sorting each group of records separetely takes us to the second line of Table 3; this is called the “first pass”.<

70、;/p><p><b>　　Table3</b></p><p>　　DIMINSHING INCREMENTSORT</p><p>　　The sequence of increments 8，4，2，1 is not sacred;any sequence h1，hi-1，..,hn can be used, so long as last

71、incement h1 equals 1. Some squences are much better than others; we will discuss the choice of increments later.</p><p>　　Conclusion</p><p>　　Now that we are close to the end of a very long chap

72、ter, we best "sort out" has been studied the most important facts. </p><p>　　An algorithm for sorting, is one such process, which rearrange all the records of a file, so that in the ascending order

73、 of their number, which is an ordered arrangement is useful because it is put together with the recording of the same, allowing effective treatment at the same keycode good discharge more than one file, which leads to an

74、 efficient search method is to remove the computer and look less confusion. If an application either for it, or whatever is what computers use, just having one </p><p>　　Therefore, all the methods have to re

75、member, because in an environment specifically, they are the best.</p><p><b>　　Reference</b></p><p>　　[1] Bell，D．The principles of sorting．The Computer Journal 1 (1958)：71–77．</p&

76、gt;<p>　　[2] Bose，R. C，and Nelson，R.J．A sorting problem．Journal of the ACM (JACM) 9，2 (1962)：28–296．</p><p>　　[3] Halstead，M. H．Elements of Software Science．Operating．a(chǎn)nd Programming Systems Series，vo