王承恩

摘 要 計(jì)算機(jī)排序算法是計(jì)算機(jī)軟件編程的基礎(chǔ)，也是實(shí)際生產(chǎn)生活中經(jīng)常使用的算法。文章重點(diǎn)圍繞典型算法展開敘述，并結(jié)合高考成績排名進(jìn)行程序步驟設(shè)計(jì)，以此拓展對(duì)計(jì)算機(jī)排序算法的理解和應(yīng)用。

關(guān)鍵詞 計(jì)算機(jī)；排序算法；高考成績；排名

中圖分類號(hào) TP3 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào) 1674-6708（2018）224-0141-02

排序算法在計(jì)算機(jī)程序中具有舉足輕重的地位，是計(jì)算機(jī)程序?qū)W習(xí)的基礎(chǔ)。尤其是信息大爆炸的今天，大量的數(shù)據(jù)需要處理，而往往在處理數(shù)據(jù)的第一步是按照一定的規(guī)則對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，如按特定指標(biāo)進(jìn)行排序、或進(jìn)行特定的歸一化處理等[1-2]。一個(gè)好的排序算法不僅可以降低程序?qū)τ布囊?，也?huì)使得算法執(zhí)行效率上大大提高。當(dāng)然排序算法在實(shí)際日常的生產(chǎn)生活中也有很多應(yīng)用，如對(duì)一些經(jīng)濟(jì)數(shù)據(jù)的統(tǒng)計(jì)、學(xué)生成績的排名等，需要排序算法具有一定的穩(wěn)定性，且能按照多指標(biāo)進(jìn)行一定規(guī)則的排序[ 3 ]，如本文所要研究的高考成績排序問題，在總分一致的情況下會(huì)依次按照語文、數(shù)學(xué)、外語等相關(guān)科目成績進(jìn)行排序。

文章基于對(duì)計(jì)算機(jī)排序算法的理解，對(duì)幾種經(jīng)典的計(jì)算機(jī)排序算法機(jī)理的闡述，詳細(xì)分析算法原理、算法過程，并以高考成績排名為例，提出了成績的排序規(guī)則，為進(jìn)一步學(xué)習(xí)計(jì)算機(jī)程序奠定基礎(chǔ)。

1 常見計(jì)算機(jī)排序算法[1-4]

排序算法作為計(jì)算機(jī)程序的基礎(chǔ)，所謂排序是指對(duì)一串記錄按照某個(gè)特定的關(guān)鍵字或者是規(guī)則進(jìn)行遞增（遞減）排列操作，也就是要求待排序的記錄按照特定要求規(guī)則進(jìn)行排列。看似十分簡單的問題，在眾多領(lǐng)域起到十分重要的作用，尤其是近些年發(fā)展而來的大數(shù)據(jù)處理技術(shù)對(duì)排序算法的要求越來越高，一個(gè)好的排序算法是可以經(jīng)受大量實(shí)例進(jìn)行推理和檢驗(yàn)的。

1.1 冒泡排序算法

1）冒泡法排序原理。所謂冒泡法排序其實(shí)就將小的數(shù)慢慢往上移動(dòng)到數(shù)列的頂部，是一種最為基本的排序算法?；驹硎且来螌?duì)相鄰兩個(gè)數(shù)字進(jìn)行比較，如果不是按照特定規(guī)則，則交換兩者的位置，并直至比較結(jié)束算遍歷一次，同樣進(jìn)行重復(fù)執(zhí)行，即可完成數(shù)列的排序。

2）冒泡法排序過程。如表1所示，即從上到下依次比較相鄰兩個(gè)數(shù)，如果上面的比下面的大，便進(jìn)行交換，否則維持順序不變，這樣便可將最大的數(shù)移動(dòng)到最底部，依次重復(fù)進(jìn)行即可實(shí)現(xiàn)冒泡法排序。

1.2 選擇排序算法

1）選擇法排序原理。如果說冒泡法排序相對(duì)機(jī)械，那么選擇法排序則相對(duì)直接，所以也稱為一種簡單直觀的排序算法。其基本原理是在待排序數(shù)列中直接查找最大（?。┰兀⑵渑旁谠摂?shù)列的起始位置，然后依次在剩余待排序數(shù)列中查找最大（小）元素排在已排列數(shù)列位置之后，以此重復(fù)執(zhí)行，即可完成數(shù)列的特定規(guī)則排序。

2）選擇法排序過程。如表2所示，第一遍是找到1最小，然后將1與3位置互換，依次完成排序，看似比冒泡法排序簡單，實(shí)際上選擇法排序中需要依次對(duì)數(shù)據(jù)進(jìn)行兩兩比較，但整體上是比冒泡法排序法更簡單。

1.3 插入排序算法

1）插入法排序原理。插入法排序也屬于直觀排序算法，其基本原理是依次從上到下構(gòu)建有序的數(shù)列，將待排序數(shù)字按照特定順序從后向前掃描，找到相應(yīng)位置進(jìn)行插入排序。

2）插入法排序過程。如表3所示，即首先檢查2與3，則需要將2排在最前面，接著檢查4位置不變，再繼續(xù)檢查1，則需要將其排在最前面，依次完成插入即可。

1.4 歸并排序算法

1）歸并法排序原理。歸并排序的基礎(chǔ)是歸并操作，采用分治法實(shí)現(xiàn)一個(gè)數(shù)列的各個(gè)子序列的排序，然后按照特定規(guī)則合并有序的子序列，進(jìn)而得到最終的有序數(shù)列，通常都是按照兩個(gè)有序子序列合成，這就是典型的2路歸并操作。

2）歸并法排序過程。在表格上難以描述歸并的過程，本質(zhì)上是將數(shù)據(jù)分為兩個(gè)子序列，如表4中，第一步將分為2和4，1和3和5，在分為子序列的過程中就已經(jīng)按照順序進(jìn)行排列，然后從兩個(gè)子序列中從小到大依次進(jìn)行排序。

1.5 其他排序法

除了上述幾種典型的排序算法，在實(shí)際應(yīng)用還有其他的經(jīng)典排序算法，如快速排序算法、堆排序算法，以及一些改進(jìn)型排序算法，如希爾排序算法等，在實(shí)際應(yīng)用中也十分廣泛。

2 排序算法在高考成績中的應(yīng)用分析

2.1 應(yīng)用背景介紹

在進(jìn)入高中學(xué)習(xí)以來，學(xué)校為了督促學(xué)生、班級(jí)之間的學(xué)習(xí)效果比較，以便更好地進(jìn)行自我檢查，往往會(huì)對(duì)考試成績進(jìn)行排序。不僅如此，其實(shí)只要在實(shí)際測(cè)試考試中，往往都會(huì)按照結(jié)果進(jìn)行排序。同樣高考更是離不開對(duì)成績的排名，對(duì)高考成績的排名是十分必要的，對(duì)考生自己而言知道自己在全省處于何等水平，并按照該層次可以報(bào)考相應(yīng)的學(xué)校，而對(duì)于高考招生錄取更是重要，因?yàn)槟壳案呖贾驹付紝儆谄叫兄驹福锤鱾€(gè)志愿沒有先后關(guān)系，但是錄取投檔是按照考試成績進(jìn)行投檔。本質(zhì)上就是按照高考成績投遞檔案，讓高校按照一定的先后順序進(jìn)行錄取，直至錄滿為止，可見高考成績的排名十分重要，往往會(huì)因?yàn)榕琶麊栴}影響到個(gè)人的錄取結(jié)果。

2.2 高考成績中的排序算法設(shè)計(jì)

從上述可知，高考成績排名十分重要，各省教育考試院也十分重視學(xué)生的排名規(guī)則制定，但各省的排名有個(gè)共同特點(diǎn)都是首先按照總分進(jìn)行先后排名，但是一定總分相同，后續(xù)名次如何進(jìn)行則各省略有不同。由于當(dāng)前取消了高考加分，因此排序相對(duì)較簡單一些，否則排序還會(huì)更加復(fù)雜，以下是高考成績中典型的排序規(guī)則[ 5 ]。

1）高考成績總分相同按單科成績排名，只有總分相同且單科分?jǐn)?shù)都相同時(shí)，才視為相同名次（排位分）。

2）文史類的科目順序依次為語文、外語、數(shù)學(xué)、文科綜合；即總分相同，先看語文；若語文同分，則看外語；外語同分，再看數(shù)學(xué)；若再同分，則看文科綜合。

3）理工類的科目順序依次為數(shù)學(xué)、外語、語文、理科綜合；即總分相同，先看數(shù)學(xué)；數(shù)學(xué)同分，則看外語；若外語同分，再看語文；若再同分，則看理科綜合。如果按照上述規(guī)則進(jìn)行排序，在總分上排序則可以采用多種排序算法，幾乎沒有太大區(qū)別，但在總分一致情況下則在算法設(shè)計(jì)上可以選擇冒泡法排序相對(duì)更加簡單可靠。下面以高考理科成績排序進(jìn)行算法設(shè)計(jì)，相應(yīng)的算法步驟如圖1所示。

3 結(jié)論

排序算法是計(jì)算機(jī)程序?qū)W習(xí)的基礎(chǔ)，文章主要對(duì)幾種典型的排序算法進(jìn)行了闡述，對(duì)原理和過程進(jìn)行了細(xì)致的分析。當(dāng)然對(duì)排序算法的研究還有很多，如對(duì)算法的復(fù)雜度進(jìn)行分析，復(fù)雜度又分為時(shí)間復(fù)雜度和空間復(fù)雜度，即時(shí)間消耗和內(nèi)存消耗角度進(jìn)行研究，還有對(duì)算法的穩(wěn)定性分析，所謂穩(wěn)定性分析是兩個(gè)相同元素在排序前后相對(duì)位置有無變化，沒有變化說明是穩(wěn)定的排序算法，反之便是不穩(wěn)定的算法。作為基本數(shù)據(jù)處理方法，在實(shí)際應(yīng)用中經(jīng)常使用，如本文重點(diǎn)結(jié)合自己對(duì)高考成績排名的理解，從高考排名的需求角度分析了排名的重要性和嚴(yán)謹(jǐn)性，同時(shí)結(jié)合對(duì)排序算法的理解，以高考理科成績的排名建立了程序設(shè)計(jì)步驟。

可以遇見，隨著高考的進(jìn)一步改革[ 6 ]，高考成績的排序規(guī)則也將越來越復(fù)雜，需要更精確更穩(wěn)定的排序算法來保證高考成績的嚴(yán)肅性，為高考錄取規(guī)則奠定堅(jiān)實(shí)的技術(shù)基礎(chǔ)。

參考文獻(xiàn)

[1]霍紅衛(wèi)，許進(jìn).快速排序算法研究[J].微電子學(xué)與計(jì)算機(jī)，2002，19（6）：6-9.

[2]湯亞玲，秦鋒.高效快速排序算法研究[J].計(jì)算機(jī)工程，2011，37（6）：77-78.

[3]楊繡丞，李彤，趙娜，等.計(jì)算排序算法設(shè)計(jì)與分析[J].計(jì)算機(jī)應(yīng)用研究，2014，31（3）：658-662.

[4]黃福員，聶瑞華.冒泡排序算法的改進(jìn)[J].微機(jī)發(fā)展，2003，13（11）：26-27.

[5]夏標(biāo)泉.把高考分?jǐn)?shù)轉(zhuǎn)化為名次[J].高校招生，2010（8）.

[6]王剛，袁暉.新高考改革背景下地方高校面臨的挑戰(zhàn)和應(yīng)對(duì)策略[J].學(xué)周刊，2018（6）：7-8.