基于計算機程序設(shè)計的排序問題探討

朱鵬飛

摘要：隨著我國社會主義現(xiàn)代化建設(shè)的不斷發(fā)展，我國的計算機信息技術(shù)得到了前所未有的提升，在現(xiàn)代社會生產(chǎn)與人們的生活中發(fā)揮著不可替代的作用。作為計算機程序設(shè)計中極為重要的組成部分，排序主要負(fù)責(zé)的是對某一項無規(guī)則數(shù)據(jù)元素或相關(guān)記錄的有效排列，使其形成一種以某種關(guān)鍵字或參考排列的序列。本次研究中將著重對計算機程序設(shè)計的排序特點進(jìn)行深入分析，介紹了常見的幾類計算機程序設(shè)計排序方法，并探討了計算機程序排序方法的有效選擇，為計算機程序設(shè)計排序問題的解決提供參考。

關(guān)鍵詞：計算機；程序設(shè)計；排序問題；排序方法

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）33-0065-03

近年來，我國的軟件開發(fā)技術(shù)得到了空前的提升，軟件應(yīng)用范圍更加廣泛，這很大程度上有賴于計算機程序設(shè)計的科學(xué)性。計算機程序設(shè)計對排序問題有著較高的要求，只有確保排序工作的有效性，才能夠?qū)τ嬎銠C中存在的無序數(shù)據(jù)元素進(jìn)行科學(xué)排列，滿足設(shè)計人員的操作需求，進(jìn)而提升數(shù)據(jù)、信息查找效率[1]。計算機程序設(shè)計方法多種多樣，且容易受到多方面因素的影響，因此對計算機程序設(shè)計的排序問題探討有著重要的實踐意義與應(yīng)用價值。

1 計算機程序設(shè)計排序問題相關(guān)概述

1.1計算機程序設(shè)計的排序概述

排序問題是計算機程序設(shè)計過程中極為重要的環(huán)節(jié)，相對復(fù)雜，一旦排序問題處理不得當(dāng)，將直接影響到計算機程序設(shè)計效果。一般情況下，為了便于查找，計算機中的表往往按照關(guān)鍵字的排列順序，供操作人員快速查找到所需信息，這能夠在一定程度上提升查找效率，其對于計算機程序設(shè)計有著重要的意義[2]。由于待排序記錄數(shù)量一般是不同的，因此其所采用的存儲器也有著明顯的差別，基于此可將計算機程序設(shè)計排序分為內(nèi)部排序與外部排序兩種形式，排序方法不同，其穩(wěn)定性、算法復(fù)雜性也存在明顯的差異性。目前，計算機程序設(shè)計都力圖達(dá)到對任意給定問題進(jìn)行低復(fù)雜設(shè)計進(jìn)而達(dá)到簡化算法的目的。簡單來說，就是當(dāng)某一給定問題存在多種算法時，要從其中選擇一種復(fù)雜性最低的算法，對其進(jìn)行相應(yīng)的計算，這也是算法選擇必須遵循的一個基本原則[3]。從另一方面來說，排序方法的多樣性在一定程度上使計算機程序設(shè)計人員面臨著更多的選擇，因此，相關(guān)人員必須加強對計算機程序設(shè)計排序問題的認(rèn)識，確保計算機程序排序的科學(xué)性與有效性，進(jìn)而為計算機程序設(shè)計提供有效的參考。

1.2計算機程序設(shè)計排序基本特點

計算機程序的有效設(shè)計與計算機程序的穩(wěn)定運行有著密不可分的聯(lián)系，然而通過對計算機程序設(shè)計實際問題的綜合分析，可以發(fā)現(xiàn)計算機程序設(shè)計中普遍存在排序問題，其對計算機程序設(shè)計效果有著較大的影響，因此，必須明確計算機程序設(shè)計排序問題的特點。

1.2.1排序的復(fù)雜性

通常，在進(jìn)行計算機程序設(shè)計過程中，會涉及多方面的復(fù)雜內(nèi)容，這就在一定程度上加大了數(shù)據(jù)排序操作的難度與復(fù)雜性，計算機程序設(shè)計排序問題更為復(fù)雜[4]。即使部分設(shè)計工作者制定了最佳的計算方案，其難度仍然較高，計算機程序設(shè)計的有效性難以保證。

1.2.2排序的不確定性

在具體的計算機程序設(shè)計工作中，往往會出現(xiàn)部分?jǐn)?shù)據(jù)及記錄插入的現(xiàn)象，其內(nèi)容不容易確定，再加上其他不確定性因素，排序問題也會隨之發(fā)生變化，造成了計算機程序設(shè)計排序的不確定性。

1.2.3排序的約束性

排序的約束性問題主要指的是各類數(shù)據(jù)資源信息之間的制約與影響作用，其對計算機程序設(shè)計的效果有著極為重要的影響，然而這種數(shù)據(jù)間的約束與制約關(guān)系又是普遍存在的，這也是當(dāng)前我國計算機程序設(shè)計排序問題的一大特征之一。

1.2.4排序的多目標(biāo)性

在數(shù)據(jù)排序的過程中，往往會出現(xiàn)一些未按照順序排列的、雜亂無章的數(shù)據(jù)資源，這為計算機程序設(shè)計增加了難度，然而此類數(shù)據(jù)能夠滿足不同目標(biāo)情況的多樣化需求，因此，在對計算機程序設(shè)計的排序問題進(jìn)行解決的過程中，要充分考慮目標(biāo)的基本情況與相關(guān)設(shè)計標(biāo)準(zhǔn)，合理、科學(xué)的實施數(shù)據(jù)排序工作[5]，在排序過程中盡可能避免沖突，這種排序的多目標(biāo)性也是計算機程序設(shè)計的重要特征。

通過對計算機程序設(shè)計排序問題基本特征的分析，可以發(fā)現(xiàn)計算機程序排序問題具有一定的復(fù)雜性，其會直接影響到計算機程序設(shè)計的效果。因此，要求計算機程序設(shè)計人員必須提升自身知識素養(yǎng)與技能水平，掌握科學(xué)、合理的排序方法，展開程序設(shè)計流程。

2 計算機程序設(shè)計排序的幾種方法

基于當(dāng)前的計算機程序設(shè)計實際，首先需要了解常用的幾種計算機程序設(shè)計排序方法，并根據(jù)實際情況選取合理的排序方法，確保排序問題的妥善解決，提升計算機程序設(shè)計效率與實施效果，使計算機程序的各項功能能夠有效實現(xiàn)，為相關(guān)行業(yè)的可持續(xù)發(fā)展提供必要的技術(shù)支持。

2.1選擇排序法

選擇排序法主要指的是對雜亂無章的需要重新排列的數(shù)據(jù)元素通過多種方式進(jìn)行調(diào)整，達(dá)到合適的排序方式。通常，選擇排序法需要實施多次綜合對比分析，每次需在n-i+1（i=1，2，…n-1）中將最小的關(guān)鍵字記錄選取為有序序列的第i個記錄，選擇排序又可分為簡單選擇排序、樹形選擇排序以及堆排序三種形式。（1）簡單選擇排序。在第i趟比較中，主要針對的是n-i關(guān)鍵字的對比，然后從n-i+1個相關(guān)記錄中找到最小的關(guān)鍵字，將其與第i個記錄實施交換。若數(shù)組中包含了n個元素，那么需要進(jìn)行簡單的選擇排序，并實施n-1次的選擇操作?？梢园l(fā)現(xiàn)，若數(shù)組本原本按照由小到大順序排列，那么僅需移動0次便能夠達(dá)到有效排列；而若數(shù)組原本呈現(xiàn)逆序排列，那么其應(yīng)移動的次數(shù)不超過3（n-1）次。通常在進(jìn)行選擇排序時，需要對記錄進(jìn)行n（n-1）/2次對比，其時間復(fù)雜度為O（n2）。由此可以發(fā)現(xiàn)，選擇排序關(guān)鍵詞間需要進(jìn)行大量的復(fù)雜操作，可以通過減少關(guān)鍵詞對比，降低選擇排序復(fù)雜性[6]。（2）樹形選擇排序，其是對簡單選擇排序的有效改進(jìn)。該排序方法首先是n個關(guān)鍵字之間的比較，可以得出較小關(guān)鍵字（n/2），再次進(jìn)行兩兩比較，反復(fù)上述操作，進(jìn)而從中選出最小的關(guān)鍵字，該選擇排序過程一般會采用n個節(jié)結(jié)點二叉樹表示。N葉子結(jié)點完全二叉樹深度可表示為[[logn2+1]]，次小關(guān)鍵字的選擇則需要進(jìn)行[[logn2]]次比較得出。該排序方法需要較大的輔助存儲空間。（3）堆排法。堆排法能夠有效彌補樹形選擇排序的缺陷，其能夠?qū)o需的序列排列成為一個堆，在排序過程中呈現(xiàn)出非遞減或非遞增有序隊列形式，其最大時間復(fù)雜度為O（nlogn）。通常，單堆排序適用于n較大的文件，在n較小的排序中會存在較大的不穩(wěn)定性。

2.2快速排序法

快速排序法在起泡排序法的基礎(chǔ)上進(jìn)行了新的改進(jìn)，其能夠通過一趟排序?qū)⑿枰判虻臄?shù)據(jù)記錄分割成為兩個獨立的部分，一部分所記錄的所有關(guān)鍵字均少于另一部分關(guān)鍵字，基于此可以對這兩部分進(jìn)行相應(yīng)的排序，從另一個角度來說，快速排序穩(wěn)定性不佳。從起泡排序來看，其主要在交換的基礎(chǔ)上進(jìn)行。如在對數(shù)據(jù)進(jìn)行由小到大的排列時，首先需要將相鄰的數(shù)進(jìn)行對比，如數(shù)組8，7，5，2，1，4，經(jīng)過兩兩比較、交換，排序為7，5，2，1，4，8，最大的數(shù)字將會被沉埋，經(jīng)過反復(fù)比較，最大的數(shù)逐漸沉底。N個數(shù)的比較次數(shù)為n-1。實踐研究表明，冒泡排序在整個排序過程中僅需要一個輔助單元，其排序時間效率很大程度上與數(shù)據(jù)n相關(guān)。假設(shè)數(shù)據(jù)元素保持同一狀態(tài)，那么正序冒泡法的比較次數(shù)則為n-1次，無需移動；其逆序冒泡法需要比較n（n-1）/2次，移動3n（n-1）/2次，從而計算出冒泡排序法的時間復(fù)雜度平均為O（n2）。通常在進(jìn)行快速排序前，需要選取一個記錄作為樞紐，并將比該記錄小的關(guān)鍵字均放置于該記錄前，相應(yīng)的比該記錄大的關(guān)鍵字則放于其后，便形成了以樞紐所在位置i為分界的兩個子序列，采用遞歸算法實現(xiàn)快速排列。若待排序列僅包含了一個記錄，那么可以認(rèn)為該隊列有序。若隊列需要進(jìn)行再次快速排序，那么需要對分割的子序列予以排序。從時間效率上來說，快速排序不失為當(dāng)前計算機程序設(shè)計排序最有效的方法。若初始記錄序列表現(xiàn)為基本有序或按照關(guān)鍵字進(jìn)行有序排列時，那么可以通過快速排序?qū)⑵滢D(zhuǎn)換為冒泡排序。

2.3插入排序法

所謂插入排序，主要指的是在已經(jīng)排列好的序列中加入一個新的記錄，進(jìn)而得到一個新的有序表。通常，在進(jìn)行插入排序時，首先需要明確插入的位置，在首址位置建立監(jiān)視哨，避免出現(xiàn)出界現(xiàn)象。插入排列采用的是分趟操作的方式，通常，在對第i趟進(jìn)行排序時，需要從i-1前查詢合適的位置插入，當(dāng)對n個記錄進(jìn)行排序時，則需要n-1趟插入，其屬于簡單的排序方法。若排列的n個記錄為正序，那么僅需要幾次比較即可，為n-1次，且無需進(jìn)行任何移動操作。假設(shè)其處于最差狀態(tài)下那么其所需移動的記錄為（n+2）（n-1）/2次，次數(shù)為（n+4）（n-1）/2次[7]。一般情況下，記錄排列多是凌亂無序的，可以綜合其最差與最好的狀況均值，并得出其時間復(fù)雜度為O（n2）。通常，若記錄n值較小，那么采用直接插入排序法則相對簡單，且容易實現(xiàn)，但不適用于n較大的情況。基于上述情況又出現(xiàn)了2路插入排序，該方法盡管不能夠避免移動，然而其能夠在一定程度上降低移動次數(shù)，希爾排序?qū)ζ渌判蚍椒ㄟM(jìn)行了新的改進(jìn)，提升了時間效率，其能夠?qū)⒋判蛴涗浄指畛蔀槎鄠€子序列實施排序，在這個過程中，關(guān)鍵字能夠?qū)崿F(xiàn)跳躍移動，當(dāng)其形成一定的排序后，再進(jìn)行1增量插入排序。

3 計算機程序設(shè)計排序方法的有效選擇

排序方法的選擇對計算機程序設(shè)計效果有著極為重要的影響。然而，無論是選擇排序法、快速排序法還是插入排序法其時間復(fù)雜性都與n有著一定的聯(lián)系，即排序方法的選擇應(yīng)考慮n的大小。通常，若n較小，那么一般適于選擇直接插入法或直接選擇法，這兩種排序方法需要進(jìn)行多次移動，因此，在需要記錄大量信息的條件下，可以采用直接選擇排序法。而若n較大，那么則不適于選擇需要較多移動次數(shù)的排列方法，應(yīng)盡可能選用時間復(fù)雜度小的排序法，如快速排序法、堆排序等[8]，這幾種排序方法也有著各自不同的特征，若實施的內(nèi)部排序，那么則可優(yōu)先選用快速排序法，其能夠?qū)崿F(xiàn)對任意分布關(guān)鍵字的有效排序，且能夠確保所用的平均時間最少。另外，給定數(shù)值文件的狀態(tài)也與排序方法的選擇有著極為重要的聯(lián)系，若其初始狀態(tài)顯示為正序排列，那么可以選擇直接插入法或冒泡排序法，部分排序需要對關(guān)鍵字進(jìn)行相應(yīng)的比較，然后再進(jìn)行轉(zhuǎn)移，采用二叉樹排序法對其進(jìn)行描述。若n較小，且其所記錄的關(guān)鍵字也較少，可以實施分解，將其轉(zhuǎn)變?yōu)樽有蛄羞M(jìn)行排序，有利于排序問題的有效解決。

4結(jié)束語

新時期，我國的計算機信息技術(shù)也取得了新的進(jìn)展，計算機程序設(shè)計的排列問題逐漸成為計算機領(lǐng)域的研究重點，排序方法不同，其能夠解決的問題也有著明顯的差異性，各種排序方法既有著自己明顯的優(yōu)越性，又存在著一定的缺陷，因此，要加強對排序思想、方法及效率的分析與比較，針對具體的問題，給予相應(yīng)的排序方法，確保計算機程序設(shè)計的實現(xiàn)，為工作與生活提供幫助。

參考文獻(xiàn)：

[1] 呂雪. 計算機程序設(shè)計中基于任務(wù)驅(qū)動模式的冒泡排序算法教學(xué)設(shè)計[J]. 通訊世界， 2015（15）：261-263.

[2] 鄒汪平， ZOUWang-ping. 基于能力導(dǎo)向的高職計算機程序設(shè)計類課程案例-任務(wù)驅(qū)動教學(xué)模式研究[J]. 通化師范學(xué)院學(xué)報， 2015（6）：74-77.

[3] 宛西原， 汪霞. 非計算機本科專業(yè)計算機程序設(shè)計課程的改革思考[J]. 計算機工程與科學(xué)， 2014， 36（s1）：56-59.

[4] 韓松. 以應(yīng)用為導(dǎo)向的計算機程序設(shè)計語言類課程教學(xué)探討[J]. 無線互聯(lián)科技， 2014（10）：231-232.

[5] 王帥， 喻歆， 何嘉. 基于MPI和OpenMP的排序算法并行優(yōu)化研究[J]. 成都信息工程大學(xué)學(xué)報， 2016（3）.

[6] 張樂成， 靖宇， 邵梅. 基于程序設(shè)計課的計算機模擬實驗教學(xué)實踐與探討[J]. 福建電腦， 2011， 27（4）：204-205.

[7] 李鑌洋， 李博涵， 王慶全. 關(guān)于初學(xué)者學(xué)好計算機程序設(shè)計語言的幾點探討[J]. 硅谷， 2013， 14（7）：191-192.

[8] Zhu Y， Wang J， Qu B. Multi-objective economic emission dispatch considering wind power using evolutionary algorithm based on decomposition[J]. International Journal of Electrical Power & Energy Systems， 2014， 63（12）：434-445.