順序存儲(chǔ)的線性表中關(guān)鍵字?jǐn)?shù)量有限的記錄的排序方法

1、挨次存儲(chǔ)的線性表中關(guān)鍵字?jǐn)?shù)目有限的記載的排序要領(lǐng)摘要關(guān)于排序已經(jīng)有很多成熟的算法，但對(duì)付一些特別的題目和有特別要求的題目，已有的一些經(jīng)典的排序算法卻不必然能滿意標(biāo)題題目要求，本文就關(guān)鍵字?jǐn)?shù)目有限的記載的排序題目提出了一個(gè)有用的算法。關(guān)鍵詞排序；關(guān)鍵字；比力；互換1弁言排序是盤算機(jī)步伐方案中的一種緊張操縱，它的成效是將一個(gè)或記載的恣意序列重新按其關(guān)鍵字的某種序次(非遞減或非遞增挨次)擺列起來，使其具有必然的挨次，以便于舉行數(shù)據(jù)查尋。通常，在排序歷程中需舉行以下兩種根本操縱：比力兩個(gè)關(guān)鍵字的巨細(xì)；將記載從一個(gè)位置挪動(dòng)到另一個(gè)位置。前一個(gè)操縱對(duì)大多數(shù)排序要領(lǐng)來說都是需要的，此后一個(gè)操縱那么隨著記載的

2、存儲(chǔ)方法和利用的排序要領(lǐng)的差異而有所差異。對(duì)付存儲(chǔ)在線性表中的記載舉行排序，其重要操縱是要通過一系列的比力使不在準(zhǔn)確位置上的記載通過互換操縱使之到達(dá)準(zhǔn)確的位置上，一次互換操縱可以互換兩筆記載的位置，因此進(jìn)步排序服從的很緊張的一個(gè)方面就是只管淘汰記載挪動(dòng)的次數(shù)。2題目的提出在現(xiàn)實(shí)題目中常常碰到如許一種特別環(huán)境的排序，即對(duì)關(guān)鍵字個(gè)數(shù)有限的記載舉行排序。比方，試圖對(duì)某次比賽的獎(jiǎng)牌榜舉行排序時(shí)就只有3個(gè)關(guān)鍵字，即：金牌、銀牌和銅牌(或一等獎(jiǎng)、二等獎(jiǎng)和三等獎(jiǎng))，全部的金牌得到者在最前面，隨后是銀牌得到者，末了是銅牌得到者。要對(duì)獎(jiǎng)牌榜排成切合要求的挨次而又要求用最少的互換次數(shù)來實(shí)現(xiàn)，對(duì)雷同如許的題目我們可

3、以用下面的標(biāo)題題目來形貌：對(duì)付一個(gè)給定的只含有3個(gè)關(guān)鍵字的記載序列，將其按非遞減挨次擺列，要求互換次數(shù)最少?，F(xiàn)假設(shè)關(guān)鍵字只有1、2、3(固然也可以是別的數(shù)據(jù)，好比9、20、57等)一個(gè)挨次存儲(chǔ)的線性表，方案一個(gè)算法將該挨次表按非遞減排序，要求互換次數(shù)最少。3算法闡發(fā)在浩繁排序算法中，選擇法排序相對(duì)付別的排序要領(lǐng)來說，均勻互換次數(shù)是最少的，尤其是在關(guān)鍵字紊亂無章的環(huán)境下利用選擇法排序可以有用地淘汰互換次數(shù)。選擇法的根本頭腦是：起首從序列中選摘關(guān)鍵字最小的記載同第一筆記載互換，再?gòu)挠嘞碌挠涊d中選摘關(guān)鍵字最小的與第二筆記載互換，如許往復(fù)下去，直到全部記載排序完成。如對(duì)付如下的初始序列：也就是原序列的

4、第0筆記載和第3筆記載舉行了互換操縱，使原第3筆記載到達(dá)了應(yīng)該到達(dá)的準(zhǔn)確位置，而原第0筆記載到達(dá)了第3筆記載的位置，但我們可以看出顯然不是它應(yīng)該到達(dá)的終極位置，以是至少還要必要一次互換操縱才有大概使該記載終極到位。終極使上述序列排成非遞減序列必要舉行4次互換操縱。其排序歷程如下：初始序列：3231221311第一次互換后：1233221311第二次互換后：1133222311第三次互換后：1113222331第四次互換后：1111222333通過上述的闡發(fā)，對(duì)關(guān)鍵字?jǐn)?shù)目有限的記載排序，用選擇法舉行顯然互換次數(shù)不是最少的。針對(duì)標(biāo)題題目要求，假設(shè)我們?cè)诨Q時(shí)盡大概地做到使兩筆記載同時(shí)到位，那么互換

5、次數(shù)必定會(huì)少于選擇法。由于要排成非遞減序列，以是關(guān)鍵字小的記載應(yīng)該在序列的前半部門，而關(guān)鍵字大的記載應(yīng)該在序列的后半部門。為此，我們可以按如下要領(lǐng)舉行排序：假設(shè)alhigh是一維數(shù)組，我們讓變量id=(l+high)/2；指針i、j作為操縱搜刮的變量，指針i用來在記載的前半部門搜刮，指針j用來在記載的后半部門搜刮；指針frntax用來記載數(shù)組前半部門中關(guān)鍵字值最大的記載位置，每次搜刮其初始值都為l，指向第一個(gè)記載位置；指針bakin用來記載數(shù)組后半部門中關(guān)鍵字值最小的記載的位置，每次搜刮時(shí)其初始值都為high，指向末了一個(gè)記載的位置；變量exhangenu記載互換的次數(shù)，其初始值為0。排序的詳

6、細(xì)歷程為：我們起首從序列的開始(第l筆記載)在序列的前半部門搜刮關(guān)鍵字值最大的記載，用變量frntax來記載尋到的關(guān)鍵字值最大的記載的位置；從序列的末了開始(第high筆記載)在序列的后半部門中搜刮關(guān)鍵字值最小的記載，用變量bakin記載序列后半部門中關(guān)鍵字值最小的記載位置。搜刮完一遍后用frntax指示的記載的關(guān)鍵字值afrntax和bakin指示的記載的關(guān)鍵字值abakin舉行比力，假設(shè)afrntaxabakin，說明這兩個(gè)位置上的記載都不在準(zhǔn)確的位置上，那么這兩個(gè)位置的記載要做一次互換，同時(shí)互換次數(shù)exhangenu增長(zhǎng)1。由于序列關(guān)鍵字的數(shù)目是有限的，一次互換有大概使兩筆記載同時(shí)到位，

7、如許就可以有用地淘汰記載互換的次數(shù)；假設(shè)在搜刮完后沒有產(chǎn)生互換，說明前半部門中全部記載的關(guān)鍵字值都不大于后半部門中全部記載的關(guān)鍵字值，那么竣事本次搜刮歷程。然后將序列分為兩個(gè)部門alid和aid+1high，在這兩個(gè)部門中別離實(shí)行上述歷程，也就是對(duì)兩部門別離舉行遞歸調(diào)用，而互換次數(shù)也相應(yīng)的為exhangenu=exhangenu+前半部門互換的次數(shù)+后半部門互換的次數(shù)。4算法實(shí)現(xiàn)顛末上面的闡發(fā)，我們給出實(shí)現(xiàn)上述歷程的算法如下：輸入：n個(gè)元素的數(shù)組a0.n-1輸出：按非落序擺列的數(shù)組a0.n-1，排序必要的元素互換次數(shù)exhangenuexhangenu=0；/初始互換次數(shù)為0if數(shù)組中的元素個(gè)

8、數(shù)大于兩個(gè)thenid=(l+high)/2；/id為中心元素的位置hile(記載還沒有搜刮完成)在數(shù)組的前半部門搜刮關(guān)鍵字值最大的記載位置，用frntax來記載該位置，其初始值為l；在數(shù)組的后半部門中搜刮關(guān)鍵字值最小的記載的位置，用bakin來記載該位置，其初始值為high；ifafrntaxabakinthenafnrtaxabakin；exhangenu=exhangenu+1；if沒有互換then/別離在數(shù)組的前半部門和后半部門中舉行遞歸處置懲罰；exhangenu+=前半部門的處置懲罰所需的互換次數(shù)+后半部門的處置懲罰所需的互換次數(shù)；else/數(shù)組中的元素個(gè)數(shù)即是2if(alahig

9、h)thenalahigh；exhangenu+；returnexhangenu；/將互換次數(shù)返回如對(duì)上面的序列操縱歷程用該要領(lǐng)操縱表示圖如下：顛末表示圖上、步的互換之后，序列釀成了下面的環(huán)境：1111222333在本例中，我們創(chuàng)造只顛末了3次互換序列就已經(jīng)釀成了非遞減排序，而互換次數(shù)比利用選擇法排序少1次。假設(shè)待排序的數(shù)據(jù)比力多，大概數(shù)據(jù)的原始位置不是像上面所舉例子一樣，那么很大概顛末第一遍的操縱之后整個(gè)序列還沒有完全到達(dá)要求，那么就將整個(gè)序列分成前后兩部門，然后在兩部門中別離實(shí)行上述歷程，即遞歸舉行處置懲罰。下面給出用語(yǔ)言實(shí)現(xiàn)上述算法的函數(shù)exhangesrt：調(diào)用方法：exhangesr

10、t(a，0，n-1)intexhangesrt(inta，intl，inthigh)inti，j，p，tep，id；intfrntax，bakin，exhangenu=0；if(high-l1)id=(l+high)/2；fr(p=l；p=id；p+)frntax=l；bakin=high；fr(i=l+1，j=high-1；i=j；i+，j-)if(afrntaxai)frntax=i；if(abakinaj)bakin=j；if(afrntaxabakin)tep=afrntax；afrntax=abakin；abakin=tep；exhangenu+；elseexhangenu+=exh

11、angesrt(a，l，id)+exhangesrt(a，id+1，high)；elseif(alahigh)tep=al；al=ahigh；ahigh=tep；exhangenu+；returnexhangenu；5與利用選擇法排序的比力下面給出利用本算法和利用選擇法舉行處置懲罰的幾組比較數(shù)據(jù)，從中可以看出在任何環(huán)境下利用本算法排序在互換次數(shù)上都少于利用選擇法排序所需的互換次數(shù)。第一組：最好環(huán)境，數(shù)據(jù)自己就有序初始數(shù)據(jù)：1111222333利用選擇法的互換次數(shù)：0利用本算法的互換次數(shù)：0第二組：最差環(huán)境，全部數(shù)據(jù)都不在準(zhǔn)確位置上初始數(shù)據(jù)：3321131222利用選擇法的互換次數(shù)：7利用本算法的互換次數(shù)：6第三組：隨機(jī)環(huán)境初始數(shù)據(jù)：3212231231利用選擇法的互換次數(shù)：5利用本算法的互換次數(shù)：3第四組：隨機(jī)環(huán)境初始數(shù)據(jù)：2133221121利用選擇法的互換次數(shù)：5利用本算法的互換次數(shù)：4第五組：隨機(jī)環(huán)境初始數(shù)據(jù)：2233123112利