分段快速排序在碩士研究生招生考試中的應(yīng)用
——基于重慶X 高校2019-2020 學(xué)年度招生數(shù)據(jù)的分析

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

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

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

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

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

二、高校碩士研究生招生工作現(xiàn)狀

本文對國內(nèi)部分知名高校進(jìn)行了調(diào)研，與高校碩士研究生招考工作人員進(jìn)行座談，交流當(dāng)前高校碩士研究生招生過程中相關(guān)環(huán)節(jié)的工作模式和經(jīng)驗(yàn)。經(jīng)過梳理，本文認(rèn)為當(dāng)前我國碩士研究生招生工作主要存在以下問題。

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

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

現(xiàn)行研究生招生考試制度下，招生單位除完成本單位招生工作以外，還需作為考點(diǎn)完成報考點(diǎn)的考務(wù)工作，招考難以分離。

(二)業(yè)務(wù)重視不夠，無法適應(yīng)新形勢

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

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

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

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

三、分段快速排序在試卷整理排序中的應(yīng)用

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

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

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

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

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

1.快速排序

快速排序(Quick Sort)由C.A.R.Hoare 在1960 年提出。其基本思想：通過一趟排序?qū)⒁判虻臄?shù)據(jù)序列分成獨(dú)立的兩個部分，其中一個部分的所有數(shù)據(jù)都比另外一個部分的所有數(shù)據(jù)小(或者大)，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，直到排序完成?？焖倥判虻牧鞒倘缦拢?1)首先設(shè)定一個分界值，通過該分界值將數(shù)組分成左右兩部分。(2)將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊，完成一趟排序。(3)分別對左邊和右邊的數(shù)據(jù)獨(dú)立排序。(4)重復(fù)上述過程，遞歸調(diào)用該流程，直到排序完成。

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

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

2.分段快速排序在試卷整理中的應(yīng)用

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

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

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

(三)效率分析

1.時間復(fù)雜度分析

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

2.實(shí)踐結(jié)果分析

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

圖2 傳統(tǒng)方法與本文方法用時對比趨勢圖

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

四、結(jié)束語

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

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