張 晨

(安徽建筑大學(xué) 城市建設(shè)學(xué)院，安徽 合肥 238076)

當(dāng)今是信息時代，計算機處理數(shù)據(jù)信息的范圍越來越廣，需要比較的東西也越來越多，這與C語言程序有關(guān)，結(jié)構(gòu)化程序設(shè)計在 C語言程序設(shè)計中尤為重要[1]。其程序結(jié)構(gòu)包括序列結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)，在 C語言編程教學(xué)中，排序算法應(yīng)用廣泛、使用頻繁[2]，因此，對排序算法的研究一直是計算機領(lǐng)域的一個熱點問題。以往大都使用快速排序、堆排序和歸并排序方法，這三種方法涉及的問題復(fù)雜，受到選擇結(jié)構(gòu)排序比較次數(shù)影響，導(dǎo)致排序效果較差。為了優(yōu)化堆排序和編程優(yōu)化的次數(shù)，研究C語言程序設(shè)計中選擇結(jié)構(gòu)排序算法，提高其排序結(jié)果的穩(wěn)定性十分必要。

1 選擇結(jié)構(gòu)排序算法原理

C語言源程序可由一個或多個源文件組成，每個源文件可由一個或多個函數(shù)組成；不管一個源程序有多少個文件，它都有一個主函數(shù)；可以在源程序中包含預(yù)處理命令，通常將其置于源文件或源程序之前；每條語句都必須以分號結(jié)尾[3-4]。但是，對于預(yù)處理命令，不能在函數(shù)標題和括號“}”的后面加上分號；用于表示時間間隔的標識符和關(guān)鍵字之間至少要添加一個空格。如果有明顯的空白字符，也可以不顯示空白[5-6]。在編程時遵循的規(guī)則提高了算法的質(zhì)量，使得設(shè)計和閱讀更方便。對箭頭的濫用必須加以限制，也就是說，不能讓它亂成一團，而是要有條不紊[7]。但該算法必須包含某些分支和循環(huán)，并且不可能全部由無序組成，需要使用選擇結(jié)構(gòu)來解決此問題[8]。

選擇結(jié)構(gòu)包括判斷方框的流程圖，根據(jù)給定的條件P是否正確，選擇了執(zhí)行A和B，不管用什么方法，都會選擇是在結(jié)構(gòu)之后執(zhí)行，還是在 B和A兩個判斷方框中之前執(zhí)行，選擇結(jié)構(gòu)流程如圖1所示。

圖1 選擇結(jié)構(gòu)流程圖

由圖1可知，選擇結(jié)構(gòu)排序是指按照關(guān)鍵字重新排列一系列數(shù)據(jù)或元素，使其按順序(增加或減少)排列[9-10]。資料處理時，假設(shè)檔案中的項目(或記錄)為：R1，R2，R3，…，Rn

關(guān)鍵字分別是：K1，K2，K3，…，Kn，

那么排序結(jié)果就是將這n個元素按照關(guān)鍵字的條件要求(Ki≤Ki2≤Ki3≤…≤Kin或Ki≥Ki2≥Ki3≥…≥Kin)重新排列為：

Ri1，Ri2，Ri3，…，Rin

選擇結(jié)構(gòu)的選取采用了交換排序法，換序的基本思想是通過比較成對數(shù)組來確定一個順序。如有不符合之處，將兌換[11]。同樣，保持原來的次序，直到所有的關(guān)鍵字都達到指定的次序。根據(jù)“輕的高，重的低”的原則，對排序后的記錄數(shù)組進行重復(fù)掃描，直到輕泡上，重泡下[12]。為此，提出了一種改進的冒泡排序算法，它的基本思想是選擇當(dāng)前無序數(shù)組中的任意元素作為基值temp，它用來將數(shù)組劃分為兩個較小的無序數(shù)組，即左邊的記錄小于基值temp，右邊的記錄大于基值temp，最后一個排序位置為基值temp。用這種方法重復(fù)這一過程，直到所有的記錄都完成為止[13]。

2 C語言程序設(shè)計中的選擇結(jié)構(gòu)排序算法設(shè)計

C語言是一種結(jié)構(gòu)化語言，可以在硬件上實現(xiàn)編程操作，可以用來開發(fā)系統(tǒng)軟件，也可以用來開發(fā)應(yīng)用軟件。此外，由于C語言的高效率和可移植性，它被廣泛地移植到各種類型的計算機上，從而形成了不同版本的C語言。Select排序是一個重要的算法，它建立在選擇原則的基礎(chǔ)上，選擇最小(或最大)的元素，用第一個元素交換它，然后用最小(或最大)元素中剩下的元素交換它，直到所有數(shù)據(jù)元素都排好。因為每個選擇都是數(shù)據(jù)的最小(或最大)值，所以稱之為選擇排序。

C語言表達式由操作符和操作數(shù)據(jù)組成，每個操作符具有優(yōu)先權(quán)和綁定規(guī)則。具有更高優(yōu)先級的操作符會將操作數(shù)組合起來，而不必用括號表示。如果兩個運算子有相同的優(yōu)先級，則根據(jù)合并規(guī)則，使運算子與運算子一致。

假設(shè)有5組數(shù)據(jù)，分別是85、61、72、94、50存儲到C語言數(shù)組Bs中，對這5組數(shù)據(jù)進行升序排序設(shè)計。要對C語言數(shù)據(jù)進行升序設(shè)計時，需每次選擇最小的數(shù)據(jù)放在最前方。

2.1 第1趟排序過程

第1趟排序過程如表1所示。

表1 第1趟排序過程

由表1可知，5組數(shù)組下標的元素分別與Bs{m}相比存在兩種可能性：①如果數(shù)組下標的元素比數(shù)組大，則需更改最小下標值；②如果數(shù)組下標的元素比數(shù)組小，則最小下標值不變。

如果使用變量J表示元素下標，則可以將比較過程表示為：if(Bs{j}

設(shè)m=1

比較：for(j=1；j<=5；j++)

if(Bs{j}

交換：將數(shù)組Bs{1}和Bs{m}交換，數(shù)據(jù)50為最小元素，與數(shù)據(jù)85交換，放置在第一位。

第1趟排序過程確定了最小數(shù)據(jù)，也是第一個位置，還要繼續(xù)在剩余位置中進行選擇交換。

2.2 第2趟排序過程

第2趟排序過程如表2所示。

表2 第2趟排序過程

由表2可知，第2趟排序過程一共對比了3次，4組數(shù)組中下標元素分別跟Bs{m}對比，確定第2趟排序過程中的最小值。

設(shè)m=2

比較：for(j=2；j<=5；j++)

if(Bs{j}

交換：將數(shù)組Bs{2}和Bs{m}交換。

第2趟排序過程確定了第二個數(shù)據(jù)，也是第二個位置，還要繼續(xù)在剩余位置中進行選擇交換。

2.3 第3趟排序過程

以此類推，第3趟排序過程對比了兩次，數(shù)組中下標元素分別跟Bs{m}對比，確定第三個數(shù)據(jù)。

設(shè)m=3

比較：for(j=3；j<=5；j++)

if(Bs{j}

交換：將數(shù)組Bs{3}和Bs{m}交換。

2.4 第4趟排序過程

第4趟只對比了1次，將數(shù)組下表中的元素分別與Bs{m}對比，確定第四個最小數(shù)據(jù)，同時也確定了第五個數(shù)據(jù)，排序結(jié)束。

設(shè)m=4

比較：for(j=4；j<=5；j++)

if(Bs{j}

交換：將數(shù)組Bs{4}和Bs{m}交換。

通過上述排序過程可看出，5組數(shù)組中共排序4趟，第1趟比較4次，第2趟比較3次，第3趟比較2次，第4趟比較1次。每趟排序交換后的數(shù)據(jù)排序結(jié)果如圖2所示。

圖2 每趟排序交換后的數(shù)據(jù)排序結(jié)果

通過圖2所示的排序結(jié)果，即可完成C語言升序排序設(shè)計。

3 實驗分析

為了驗證C語言程序設(shè)計中選擇結(jié)構(gòu)排序算法研究的合理性，進行了實驗驗證分析。

C語言程序執(zhí)行過程中，由用戶選擇菜單，觸動計算器開始工作。假設(shè)C語言計算器程序中存在5組數(shù)據(jù)，分別將92、68、60、88、70存儲到C語言數(shù)組Fs中，分別使用快速排序、堆排序、歸并排序方法和選擇結(jié)構(gòu)排序方法，對上述5組數(shù)據(jù)排序，對比上述5組數(shù)據(jù)的排序時間，對比結(jié)果如表3所示。

表3 5組數(shù)據(jù)排序時間對比分析 s

根據(jù)表3可知，采用快速排序方法對上述5組數(shù)據(jù)進行排序的時間在12.9-15.8 s之間，采用堆排序方法對5組數(shù)據(jù)進行排序的時間在19.2-28.7 s之間，采用歸并排序方法對5組數(shù)據(jù)進行排序的時間在31.5-40.8 s之間，采用選擇結(jié)構(gòu)排序方法對5組數(shù)據(jù)進行排序的時間在3.1-5.0 s之間，采用選擇結(jié)構(gòu)排序方法對5組數(shù)據(jù)進行排序的時間比其他三種方法的排序時間短，說明使用選擇結(jié)構(gòu)排序方法，排序效率較高。

4 結(jié)論

針對C語言程序設(shè)計中的選擇結(jié)構(gòu)排序算法進行分析，指出判定排序結(jié)果好壞的標準是待排序記錄的比較時間較少，占用的空間較小。沒有任何一種排序方法能對文件的初始狀態(tài)進行最佳排序，所以在處理實際問題時應(yīng)綜合考慮，選擇更適合的排序方法，并對性能分析結(jié)果進行比較。雖然使用該方法的效果良好，但實驗條件受到限制，因此，在后期需根據(jù)多種方法來實現(xiàn)預(yù)期目標。