分段快速排序在碩士研究生招生考試中的應用
——基于重慶X 高校2019-2020 學年度招生數據的分析

羅洪川，朱子義，謝冬冬，孫 博*

(1.西南大學 研究生院，重慶 400715；2.浙江工業大學 土木工程學院，浙江 杭州 310023)

一、高校碩士研究生招生意義

碩士研究生招生入學考試(以下簡稱“入學考試”)是考生進入我國研究生教育層次的主要渠道，其人才選拔效果影響著研究生教育的生源質量。隨著1980 年《中華人民共和國學位條例》的頒布，我國的研究生教育事業得以迅猛發展，全國研究生的招生報考規模截至到2017 年已經突破兩百萬人，2018 至2020 年兩年增加了140 萬人，受今年新冠肺炎疫情影響，預計2021 年仍將大幅度增長。入學考試作為進入研究生教育的入口及重要環節，對整個選拔過程至關重要。同時，做好高校碩士研究生招生工作，推進素質教育實施和創新人才培養，促進學生健康發展、培育國家杰出人才，對維護社會公平、普及研究生學歷層次有著重要作用。

當前，我國的碩士研究生招生考試歷經過去幾十年不斷地探索與改革，已形成一套較為完善的管理運行機制。眾所周知，現行碩士研究生招生考試主要實行初試和復試的綜合選拔制度。初試的考核方式為筆試，筆試試題由全國統一命題統考科目與招生單位自主命題的專業考試科目等共同組成。其中，統考科目主要包括思想政治理論、外語等；招生單位自主命題的專業課程一般包括兩門業務課程，主要考察考生對報考專業基礎知識和綜合能力的掌握；復試主要由筆試(可選)和面試等多種考核方式組成。部分高校在考生進入復試后采取多元的考核方式。高校同時作為招生單位和報名考試點(以下簡稱“報考點”)，既要完成作為招生單位的試卷命制、寄送、回收、整理與組織閱卷、統計成績、復核成績等一系列工作，又要完成作為報考點的試卷接收、組織考試等一系列考務工作。然而，近年來碩士研究生報考人數的巨幅增長，給碩士研究生招生工作帶來了沉重的負擔，大部分高校的招考工作人員已經不能滿足日益增長的工作量需求。因此，面臨報考人數的劇增帶來的系列問題，本文認真梳理研究生招生的各個環節，探索如何快速、準確、平穩地完成招生單位的招考工作，具有十分重要的意義。

二、高校碩士研究生招生工作現狀

本文對國內部分知名高校進行了調研，與高校碩士研究生招考工作人員進行座談，交流當前高校碩士研究生招生過程中相關環節的工作模式和經驗。經過梳理，本文認為當前我國碩士研究生招生工作主要存在以下問題。

(一)資源受限，招考難以分離

調研發現，高校招考工作人員一般在3 到6 人之間。招生工作由于其高強度、高壓力、零差錯特點導致招考工作人員流動性大，新舊工作交替無法有效銜接，導致人力資源嚴重不足。同時招生考試過程中的設備設施條件無法充分保障，只能靠人工去完成這些環節(例如折紙機，將試卷對折)，設備資源不足。

現行研究生招生考試制度下，招生單位除完成本單位招生工作以外，還需作為考點完成報考點的考務工作，招考難以分離。

(二)業務重視不夠，無法適應新形勢

研究生入學考試作為國家級重要考試之一，涉及若干環節，每個環節都需要反復仔細地完成、檢驗等才能保證準確性。然而，隨著研究生學歷層次的普及，報考人數大幅度增加，招生單位對變化的業務情況重視不夠，經驗主義已然無法適應人數劇增帶來的新問題、新形勢。

(三)自命題科目多，報考人數增加，試卷整理費時費力

隨著近年來碩士研究生報考人數的劇增，給招生單位的試題卷答卷小信封(以下簡稱“試卷小信封”)整理帶來了巨大的影響。以重慶X 高校為例，根據其2020 年報考數據，該校報考人數約為2.8 萬余人，通過統計分析，該校自命題數量較多的top20 科目如圖1 所示。可以看到單科自命題數最多已經高達4 500 余人。當回收試卷小信封后如何快速地按照(考試科目代碼-流水號)完成排序，對后續工作流程起著至關重要的作用。

圖1 重慶X 高校自命題(top20)數量示意圖

三、分段快速排序在試卷整理排序中的應用

(一)試卷整理的常規做法

試卷小信封整理排序是研究生招生工作環節中的關鍵環節之一。所謂試卷小信封整理，即是將回收的試題答卷小信封按照(考試科目代碼-流水號)排序后才能進入后續組織閱卷等工作。例如，以報考重慶X 高校(簡稱X校)2020 級考生數據為例，X 校有140 余個自主命題考試科目，有2.8 萬余人參加考試，這就意味著該校需要將5 萬余試卷小信封按自命題科目分類，然后將每個自命題科目類的若干考生試卷小信封按照該科目內流水號進行排序。

以某業務科考試科目(業務科1)為例，參加該考試科目的考生人數4 500 余人(圖1)，排序工作首先需要從回收的5 萬余試卷小信封中查找并取出業務科1 的試卷小信封4 500 余個(本文不考慮該考試科目缺考的考生小信封需要單獨挑選出去的情況，因為缺考考生數量相對于總共試卷小信封數量可以簡單忽略掉)，然后對業務科1 全部4 500 余個試卷小信封按照科目流水號進行排序。

常規做法即是使用直接插入排序算法進行排序。例如，對于業務科1 的試卷小信封，我們就是要把每個流水號為n 的小信封都放到自然數n 的位置，n∈{1，2，...，N}，其中N 為該科目參加排序的試卷小信封個數，這樣就完成了排序。直接插入排序僅適用于少量數據的排序，對于較大數據量排序使用直接插入排序的時間和人力成本消耗太高。因此，需要引入更加合理有效的排序方法，提高招生單位試卷小信封整理排序工作的效率，節省資源，更好地為后續工作環節服務。

(二)分段快速排序在試卷整理中的探索

1.快速排序

快速排序(Quick Sort)由C.A.R.Hoare 在1960 年提出。其基本思想：通過一趟排序將要排序的數據序列分成獨立的兩個部分，其中一個部分的所有數據都比另外一個部分的所有數據小(或者大)，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，直到排序完成。快速排序的流程如下：(1)首先設定一個分界值，通過該分界值將數組分成左右兩部分。(2)將大于或等于分界值的數據集中到數組右邊，小于分界值的數據集中到數組的左邊，完成一趟排序。(3)分別對左邊和右邊的數據獨立排序。(4)重復上述過程，遞歸調用該流程，直到排序完成。

為了更加直觀地理解快速排序的工作原理，假定有6個元素的數組A[]={10，6，3，5，32，1}，設定下標i=0，j=5 分別指向數組的首尾元素，初始參考值設為數組第一個元素ref=10；此時，從數組后面j=5 往前找，第一個比ref 小的數是1，則此時的序列為{1，6，3，5，32，10}，i=0，j=5，ref=10；然后從數組前面i=0 往后面找，第一個比ref 大的數為32，因此序列為{1，6，3，5，10，32}，i=4，j=5，ref=10；此時從數組后面j=5 往前面找，只有j=4 以后的數比10 小，此時，i=j=4，ref=10 成為一條分界線，ref 以左的數均小于等于ref 以右的數；分別對ref 左右兩部分數組遞歸調用上述流程，直到得到{1，3，5，6，10，32}，見表1。

表1 快速排序的各趟排序過程

2.分段快速排序在試卷整理中的應用

本文探索快速排序是否在試卷小信封整理排序工作中得到有效應用。仍以上述數據為例，若直接將業務科1的試卷小信封4 500 余個使用快速排序，雖然比直接插入排序時間復雜度降低了一個數量級，但實際上快速排序不具有可操作性。一是因為數組數據量太大，不利于操作；二是現實情況下保密場地面積有限且不利于工作人員并行工作。

基于上述問題，結合實際可操作性等因素，本文提出改進的快速排序分段快速排序，即將長度較大的數組先按照一定規則分割成若干長度較小的數組，然后針對各小數組應用快速排序。分段快速排序的流程如下：(1)獲取需要排序的數組長度(N)；(2)根據實際情況制定每堆長度(L)，同時獲得堆數T；(3)將大數組按照既定規則分到每堆；(4)分別對每堆遞歸調用快速排序算法得到每堆排序數組；(5)按照堆的順序合并數組得到最終排序結果。

為了更直觀地理解分段快速排序在試卷小信封整理排序中的應用，本文仍以業務科1 的試卷小信封為例，根據分段快速排序的流程，首先獲得需要排序的試卷小信封長度為4 500 余個；其次本文設定將4 500 余個信封分割成每段(堆)100 個試卷小信封并且獲得總堆數為45堆；然后安排工作人員根據每個試卷小信封的流水號放至到對應的45 堆中(第1 堆對應試卷小信封為第1 至100 個，第2 堆對應的試卷小信封為第101 至200 個，以此類推，…)；然后對每堆堆內遞歸調用快速排序算法，得到有序堆；最后，按照第1 堆、第2 堆、…、第45 堆的自然順序合并，得到最終4 500 余個有序試卷小信封，排序完畢。

(三)效率分析

1.時間復雜度分析

直接插入排序作為比較常用方法，原理相對簡單，但時間復雜度較高，為O(N)，適用于數據量較小的情況。快速排序是目前被認為最好的一種內部排序，其時間復雜度為O(Nlog)。本文提出的基于分段概念的快速排序，將數據龐大的任務分解成各個相同問題的小任務，從而對小任務進行遞歸調用快速排序，減少對整個大任務進行快速排序的劃分趟數。分段快速排序的時間復雜度主要由分堆的時間復雜度與每堆快速排序的時間復雜度構成。其中，分堆的任務只需要一趟從數組首尾交替搜索，直到i，j 相等即可，其時間復雜度為O(N)；對每堆長度為L 的小數組進行快速排序，其平均時間復雜度為O(Llog)，最后將每堆有序序列合并到最終的排序結果需要常數時間復雜度O(1)。因此整個分段快速排序的時間復雜度為耗時最長的決定，僅為T*O(Llog)。

2.實踐結果分析

按照本文提出的方法，與傳統排序整理方式，選擇自命題數目相同考試科目同時進行，所用時間對比趨勢如圖2 所示。

圖2 傳統方法與本文方法用時對比趨勢圖

由圖2 分析可知，本文提出的分段快速排序方法在實際應用中取得了較好的效果。隨著單科自命題數量的增多，傳統的插入排序時間復雜度成指數增長，而本文提出的方法時間復雜度接近線性增長。

四、結束語

碩士研究生招生入學考試作為國家級重要考試之一，是《國家中長期教育改革和發展規劃綱要(2010-2020年)》中的一項重要工作。入學考試整個流程歷經過去若干年的不斷探索與改革，形成了一套完整的體系。針對入學考試的各個環節，我們要仔細梳理其工作流程，探索工作方式，將快速發展的現代化信息技術的相關理念用于其中，更好地完成工作和適應社會工作的需要。本文針對入學考試過程中的試題小信封整理排序問題，面對大幅增長的報考人數等新形勢，打破傳統的直接插入排序方法，創新地提出分段快速排序的方法并在實際過程中加以檢驗應用。實踐證明，分段快速排序方法能大大縮短試卷小信封的整理排序時間，對整個研究生招生過程有極大的推動作用。

當然，除了探索高校碩士研究生招生中的各個環節如何應用現代化信息技術提高工作效率，同時招生單位應根據報考人數的巨幅增長合理增加招生工作人員，加強業務培訓，加快推進國家級考試管理部門人力資源評價體系建構，以適應新形勢；大力推進按照一級學科命題，減少招生單位自命題科目數，更好地為研究生學歷層次普及、建設中國特色社會主義現代化教育強國服務。