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

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

2、1 ：a ：1009-3044（2016）33-0065-03近年來(lái)，我國(guó)的軟件開發(fā)技術(shù)得到了空前的提升，軟件應(yīng)用范圍更加廣泛，這很大程度上有賴于計(jì)算機(jī)程序設(shè)計(jì)的科學(xué)性。計(jì)算機(jī)程序設(shè)計(jì)對(duì)排序問題有著較高的要求，只有確保排序工作的有效性，才能夠?qū)τ?jì)算機(jī)中存在的無(wú)序數(shù)據(jù)元素進(jìn)行科學(xué)排列，滿足設(shè)計(jì)人員的操作需求，進(jìn)而提升數(shù)據(jù)、信息查找效率1。計(jì)算機(jī)程序設(shè)計(jì)方法多種多樣，且容易受到多方面因素的影響，因此對(duì)計(jì)算機(jī)程序設(shè)計(jì)的排序問題探討有著重要的實(shí)踐意義與應(yīng)用價(jià)值。1 計(jì)算機(jī)程序設(shè)計(jì)排序問題相關(guān)概述1.1計(jì)算機(jī)程序設(shè)計(jì)的排序概述排序問題是計(jì)算機(jī)程序設(shè)計(jì)過程中極為重要的環(huán)節(jié)，相對(duì)復(fù)雜，一旦排序問題處理不得當(dāng)

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

4、。從另一方面來(lái)說，排序方法的多樣性在一定程度上使計(jì)算機(jī)程序設(shè)計(jì)人員面臨著更多的選擇，因此，相關(guān)人員必須加強(qiáng)對(duì)計(jì)算機(jī)程序設(shè)計(jì)排序問題的認(rèn)識(shí)，確保計(jì)算機(jī)程序排序的科學(xué)性與有效性，進(jìn)而為計(jì)算機(jī)程序設(shè)計(jì)提供有效的參考。1.2計(jì)算機(jī)程序設(shè)計(jì)排序基本特點(diǎn)計(jì)算機(jī)程序的有效設(shè)計(jì)與計(jì)算機(jī)程序的穩(wěn)定運(yùn)行有著密不可分的聯(lián)系，然而通過對(duì)計(jì)算機(jī)程序設(shè)計(jì)實(shí)際問題的綜合分析，可以發(fā)現(xiàn)計(jì)算機(jī)程序設(shè)計(jì)中普遍存在排序問題，其對(duì)計(jì)算機(jī)程序設(shè)計(jì)效果有著較大的影響，因此，必須明確計(jì)算機(jī)程序設(shè)計(jì)排序問題的特點(diǎn)。1.2.1排序的復(fù)雜性通常，在進(jìn)行計(jì)算機(jī)程序設(shè)計(jì)過程中，會(huì)涉及多方面的復(fù)雜內(nèi)容，這就在一定程度上加大了數(shù)據(jù)排序操作的難度與復(fù)雜性

5、，計(jì)算機(jī)程序設(shè)計(jì)排序問題更為復(fù)雜4。即使部分設(shè)計(jì)工作者制定了最佳的計(jì)算方案，其難度仍然較高，計(jì)算機(jī)程序設(shè)計(jì)的有效性難以保證。1.2.2排序的不確定性在具體的計(jì)算機(jī)程序設(shè)計(jì)工作中，往往會(huì)出現(xiàn)部分?jǐn)?shù)據(jù)及記錄插入的現(xiàn)象，其內(nèi)容不容易確定，再加上其他不確定性因素，排序問題也會(huì)隨之發(fā)生變化，造成了計(jì)算機(jī)程序設(shè)計(jì)排序的不確定性。1.2.3排序的約束性排序的約束性問題主要指的是各類數(shù)據(jù)資源信息之間的制約與影響作用，其對(duì)計(jì)算機(jī)程序設(shè)計(jì)的效果有著極為重要的影響，然而這種數(shù)據(jù)間的約束與制約關(guān)系又是普遍存在的，這也是當(dāng)前我國(guó)計(jì)算機(jī)程序設(shè)計(jì)排序問題的一大特征之一。1.2.4排序的多目標(biāo)性在數(shù)據(jù)排序的過程中，往往會(huì)出現(xiàn)

6、一些未按照順序排列的、雜亂無(wú)章的數(shù)據(jù)資源，這為計(jì)算機(jī)程序設(shè)計(jì)增加了難度，然而此類數(shù)據(jù)能夠滿足不同目標(biāo)情況的多樣化需求，因此，在對(duì)計(jì)算機(jī)程序設(shè)計(jì)的排序問題進(jìn)行解決的過程中，要充分考慮目標(biāo)的基本情況與相關(guān)設(shè)計(jì)標(biāo)準(zhǔn)，合理、科學(xué)的實(shí)施數(shù)據(jù)排序工作5，在排序過程中盡可能避免沖突，這種排序的多目標(biāo)性也是計(jì)算機(jī)程序設(shè)計(jì)的重要特征。通過對(duì)計(jì)算機(jī)程序設(shè)計(jì)排序問題基本特征的分析，可以發(fā)現(xiàn)計(jì)算機(jī)程序排序問題具有一定的復(fù)雜性，其會(huì)直接影響到計(jì)算機(jī)程序設(shè)計(jì)的效果。因此，要求計(jì)算機(jī)程序設(shè)計(jì)人員必須提升自身知識(shí)素養(yǎng)與技能水平，掌握科學(xué)、合理的排序方法，展開程序設(shè)計(jì)流程。2 計(jì)算機(jī)程序設(shè)計(jì)排序的幾種方法基于當(dāng)前的計(jì)算機(jī)程序設(shè)

7、計(jì)實(shí)際，首先需要了解常用的幾種計(jì)算機(jī)程序設(shè)計(jì)排序方法，并根據(jù)實(shí)際情況選取合理的排序方法，確保排序問題的妥善解決，提升計(jì)算機(jī)程序設(shè)計(jì)效率與實(shí)施效果，使計(jì)算機(jī)程序的各項(xiàng)功能能夠有效實(shí)現(xiàn)，為相關(guān)行業(yè)的可持續(xù)發(fā)展提供必要的技術(shù)支持。2.1選擇排序法選擇排序法主要指的是對(duì)雜亂無(wú)章的需要重新排列的數(shù)據(jù)元素通過多種方式進(jìn)行調(diào)整，達(dá)到合適的排序方式。通常，選擇排序法需要實(shí)施多次綜合對(duì)比分析，每次需在n-i+1（i=1，2，n-1）中將最小的關(guān)鍵字記錄選取為有序序列的第i個(gè)記錄，選擇排序又可分為簡(jiǎn)單選擇排序、樹形選擇排序以及堆排序三種形式。（1）簡(jiǎn)單選擇排序。在第i趟比較中，主要針對(duì)的是n-i關(guān)鍵字的對(duì)比，然后

8、從n-i+1個(gè)相關(guān)記錄中找到最小的關(guān)鍵字，將其與第i個(gè)記錄實(shí)施交換。若數(shù)組中包含了n個(gè)元素，那么需要進(jìn)行簡(jiǎn)單的選擇排序，并實(shí)施n-1次的選擇操作?？梢园l(fā)現(xiàn)，若數(shù)組本原本按照由小到大順序排列，那么僅需移動(dòng)0次便能夠達(dá)到有效排列；而若數(shù)組原本呈現(xiàn)逆序排列，那么其應(yīng)移動(dòng)的次數(shù)不超過3（n-1）次。通常在進(jìn)行選擇排序時(shí)，需要對(duì)記錄進(jìn)行n（n-1）/2次對(duì)比，其時(shí)間復(fù)雜度為o（n2）。由此可以發(fā)現(xiàn)，選擇排序關(guān)鍵詞間需要進(jìn)行大量的復(fù)雜操作，可以通過減少關(guān)鍵詞對(duì)比，降低選擇排序復(fù)雜性6。（2）樹形選擇排序，其是對(duì)簡(jiǎn)單選擇排序的有效改進(jìn)。該排序方法首先是n個(gè)關(guān)鍵字之間的比較，可以得出較小關(guān)鍵字（n/2），再次

9、進(jìn)行兩兩比較，反復(fù)上述操作，進(jìn)而從中選出最小的關(guān)鍵字，該選擇排序過程一般會(huì)采用n個(gè)節(jié)結(jié)點(diǎn)二叉樹表示。n葉子結(jié)點(diǎn)完全二叉樹深度可表示為logn2+1，次小關(guān)鍵字的選擇則需要進(jìn)行l(wèi)ogn2次比較得出。該排序方法需要較大的輔助存儲(chǔ)空間。（3）堆排法。堆排法能夠有效彌補(bǔ)樹形選擇排序的缺陷，其能夠?qū)o(wú)需的序列排列成為一個(gè)堆，在排序過程中呈現(xiàn)出非遞減或非遞增有序隊(duì)列形式，其最大時(shí)間復(fù)雜度為o（nlogn）。通常，單堆排序適用于n較大的文件，在n較小的排序中會(huì)存在較大的不穩(wěn)定性。 2.2快速排序法快速排序法在起泡排序法的基礎(chǔ)上進(jìn)行了新的改進(jìn)，其能夠通過一趟排序?qū)⑿枰判虻臄?shù)據(jù)記錄分割成為兩個(gè)獨(dú)立的部分，一部

10、分所記錄的所有關(guān)鍵字均少于另一部分關(guān)鍵字，基于此可以對(duì)這兩部分進(jìn)行相應(yīng)的排序，從另一個(gè)角度來(lái)說，快速排序穩(wěn)定性不佳。從起泡排序來(lái)看，其主要在交換的基礎(chǔ)上進(jìn)行。如在對(duì)數(shù)據(jù)進(jìn)行由小到大的排列時(shí)，首先需要將相鄰的數(shù)進(jìn)行對(duì)比，如數(shù)組8，7，5，2，1，4，經(jīng)過兩兩比較、交換，排序?yàn)?，5，2，1，4，8，最大的數(shù)字將會(huì)被沉埋，經(jīng)過反復(fù)比較，最大的數(shù)逐漸沉底。n個(gè)數(shù)的比較次數(shù)為n-1。實(shí)踐研究表明，冒泡排序在整個(gè)排序過程中僅需要一個(gè)輔助單元，其排序時(shí)間效率很大程度上與數(shù)據(jù)n相關(guān)。假設(shè)數(shù)據(jù)元素保持同一狀態(tài)，那么正序冒泡法的比較次數(shù)則為n-1次，無(wú)需移動(dòng)；其逆序冒泡法需要比較n（n-1）/2次，移動(dòng)3n（n

11、-1）/2次，從而計(jì)算出冒泡排序法的時(shí)間復(fù)雜度平均為o（n2）。通常在進(jìn)行快速排序前，需要選取一個(gè)記錄作為樞紐，并將比該記錄小的關(guān)鍵字均放置于該記錄前，相應(yīng)的比該記錄大的關(guān)鍵字則放于其后，便形成了以樞紐所在位置i為分界的兩個(gè)子序列，采用遞歸算法實(shí)現(xiàn)快速排列。若待排序列僅包含了一個(gè)記錄，那么可以認(rèn)為該隊(duì)列有序。若隊(duì)列需要進(jìn)行再次快速排序，那么需要對(duì)分割的子序列予以排序。從時(shí)間效率上來(lái)說，快速排序不失為當(dāng)前計(jì)算機(jī)程序設(shè)計(jì)排序最有效的方法。若初始記錄序列表現(xiàn)為基本有序或按照關(guān)鍵字進(jìn)行有序排列時(shí)，那么可以通過快速排序?qū)⑵滢D(zhuǎn)換為冒泡排序。2.3插入排序法所謂插入排序，主要指的是在已經(jīng)排列好的序列中加入一

12、個(gè)新的記錄，進(jìn)而得到一個(gè)新的有序表。通常，在進(jìn)行插入排序時(shí)，首先需要明確插入的位置，在首址位置建立監(jiān)視哨，避免出現(xiàn)出界現(xiàn)象。插入排列采用的是分趟操作的方式，通常，在對(duì)第i趟進(jìn)行排序時(shí)，需要從i-1前查詢合適的位置插入，當(dāng)對(duì)n個(gè)記錄進(jìn)行排序時(shí)，則需要n-1趟插入，其屬于簡(jiǎn)單的排序方法。若排列的n個(gè)記錄為正序，那么僅需要幾次比較即可，為n-1次，且無(wú)需進(jìn)行任何移動(dòng)操作。假設(shè)其處于最差狀態(tài)下那么其所需移動(dòng)的記錄為（n+2）（n-1）/2次，次數(shù)為（n+4）（n-1）/2次7。一般情況下，記錄排列多是凌亂無(wú)序的，可以綜合其最差與最好的狀況均值，并得出其時(shí)間復(fù)雜度為o（n2）。通常，若記錄n值較小，那么

13、采用直接插入排序法則相對(duì)簡(jiǎn)單，且容易實(shí)現(xiàn)，但不適用于n較大的情況。基于上述情況又出現(xiàn)了2路插入排序，該方法盡管不能夠避免移動(dòng)，然而其能夠在一定程度上降低移動(dòng)次數(shù)，希爾排序?qū)ζ渌判蚍椒ㄟM(jìn)行了新的改進(jìn)，提升了時(shí)間效率，其能夠?qū)⒋判蛴涗浄指畛蔀槎鄠€(gè)子序列實(shí)施排序，在這個(gè)過程中，關(guān)鍵字能夠?qū)崿F(xiàn)跳躍移動(dòng)，當(dāng)其形成一定的排序后，再進(jìn)行1增量插入排序。3 計(jì)算機(jī)程序設(shè)計(jì)排序方法的有效選擇排序方法的選擇對(duì)計(jì)算機(jī)程序設(shè)計(jì)效果有著極為重要的影響。然而，無(wú)論是選擇排序法、快速排序法還是插入排序法其時(shí)間復(fù)雜性都與n有著一定的聯(lián)系，即排序方法的選擇應(yīng)考慮n的大小。通常，若n較小，那么一般適于選擇直接插入法或直接選擇

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

15、少，可以實(shí)施分解，將其轉(zhuǎn)變?yōu)樽有蛄羞M(jìn)行排序，有利于排序問題的有效解決。4結(jié)束語(yǔ)新時(shí)期，我國(guó)的計(jì)算機(jī)信息技術(shù)也取得了新的進(jìn)展，計(jì)算機(jī)程序設(shè)計(jì)的排列問題逐漸成為計(jì)算機(jī)領(lǐng)域的研究重點(diǎn)，排序方法不同，其能夠解決的問題也有著明顯的差異性，各種排序方法既有著自己明顯的優(yōu)越性，又存在著一定的缺陷，因此，要加強(qiáng)對(duì)排序思想、方法及效率的分析與比較，針對(duì)具體的問題，給予相應(yīng)的排序方法，確保計(jì)算機(jī)程序設(shè)計(jì)的實(shí)現(xiàn)，為工作與生活提供幫助。參考文獻(xiàn)：1 呂雪. 計(jì)算機(jī)程序設(shè)計(jì)中基于任務(wù)驅(qū)動(dòng)模式的冒泡排序算法教學(xué)設(shè)計(jì)j. 通訊世界， 2015（15）：261-263.2 鄒汪平， zouwang-ping. 基于能力導(dǎo)向的

16、高職計(jì)算機(jī)程序設(shè)計(jì)類課程案例-任務(wù)驅(qū)動(dòng)教學(xué)模式研究j. 通化師范學(xué)院學(xué)報(bào)， 2015（6）：74-77.3 宛西原， 汪霞. 非計(jì)算機(jī)本科專業(yè)計(jì)算機(jī)程序設(shè)計(jì)課程的改革思考j. 計(jì)算機(jī)工程與科學(xué)， 2014， 36（s1）：56-59.4 韓松. 以應(yīng)用為導(dǎo)向的計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言類課程教學(xué)探討j. 無(wú)線互聯(lián)科技， 2014（10）：231-232.5 王帥， 喻歆， 何嘉. 基于mpi和openmp的排序算法并行優(yōu)化研究j. 成都信息工程大學(xué)學(xué)報(bào)， 2016（3）.6 張樂成， 靖宇， 邵梅. 基于程序設(shè)計(jì)課的計(jì)算機(jī)模擬實(shí)驗(yàn)教學(xué)實(shí)踐與探討j. 福建電腦， 2011， 27（4）：204-205.7 李鑌洋， 李博涵， 王慶全. 關(guān)于初學(xué)者學(xué)好計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的幾點(diǎn)探討j. 硅谷， 2013，