以下自考復(fù)習(xí)資料均由浙江自考網(wǎng)整理并發(fā)布，考生想要了解更多關(guān)于浙江自考報名、考試、成績查詢、畢業(yè)、歷年真題、常見問答等相關(guān)信息請關(guān)注浙江自考網(wǎng)，獲取浙江自考更多信息。
記錄中可用某一項來標(biāo)識一個記錄，則稱為關(guān)鍵字項，該數(shù)據(jù)項的值稱為關(guān)鍵字。
排序是使文件中的記錄按關(guān)鍵字遞增(或遞減)次序排列起來。·基本操作：比較關(guān)鍵字大小；改變指向記錄的指針或移動記錄。
·存儲結(jié)構(gòu)：順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)。
經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變,則稱這種排序方法是穩(wěn)定的，否則排序算法是不穩(wěn)定的。
排序過程中不涉及數(shù)據(jù)的內(nèi)、外存交換則稱之為"內(nèi)部排序"(內(nèi)排序)，反之，若存在數(shù)據(jù)的內(nèi)外存交換，則稱之為外排序。
內(nèi)部排序方法可分五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。
評價排序算法好壞的標(biāo)準(zhǔn)主要有兩條：執(zhí)行時間和所需的輔助空間，另外算法的復(fù)雜程序也是要考慮的一個因素。
插入排序：·直接插入排序：·逐個向前插入到合適位置。
·哨兵(監(jiān)視哨)有兩個作用：·作為臨變量存放R[i]
·是在查找循環(huán)中用來監(jiān)視下標(biāo)變量j是否越界。
·直接插入排序是就地的穩(wěn)定排序。時間復(fù)雜度為O(n^2)，比較次數(shù)為(n+2)(n-1)/2；移動次數(shù)為(n+4)(n-1)/2；
·希爾排序：·等間隔的數(shù)據(jù)比較并按要求順序排列，最后間隔為1。
·希爾排序是就地的不穩(wěn)定排序。時間復(fù)雜度為O(n^1.25)，比較次數(shù)為(n^1.25)；移動次數(shù)為(1.6n^1.25)；
交換排序：·冒泡排序：·自下向上確定最輕的一個。·自上向下確定最重的一個。·自下向上確定最輕的一個，后自上向下確定最重的
一個。
·冒泡排序是就地的穩(wěn)定排序。時間復(fù)雜度為O(n^2)，比較次數(shù)為n(n-1)/2；移動次數(shù)為3n(n-1)/2；
·快速排序：·以第一個元素為參考基準(zhǔn)，設(shè)定、動兩個指針，發(fā)生交換后指針交換位置，直到指針重合。重復(fù)直到排序完成。
·快速排序是非就地的不穩(wěn)定排序。時間復(fù)雜度為O(nlog2n)，比較次數(shù)為n(n-1)/2；
選擇排序：·直接選擇排序：·選擇最小的放在比較區(qū)前。
·直接選擇排序就地的不穩(wěn)定排序。時間復(fù)雜度為O(n^2)。比較次數(shù)為n(n-1)/2；
·堆排序·建堆：按層次將數(shù)據(jù)填入完全二叉樹，從int(n/2)處向前逐個調(diào)整位置。
·然后將樹根與最后一個葉子交換值并斷開與樹的連接并重建堆，直到全斷開。
·堆排序是就地不穩(wěn)定的排序，時間復(fù)雜度為O(nlog2n)，不適宜于記錄數(shù)較少的文件。。
歸并排序：·先兩個一組排序，形成(n+1)/2組，再將兩組并一組，直到剩下一組為止。
·歸并排序是非就地穩(wěn)定排序，時間復(fù)雜度是O(nlog2n),
分配排序：·箱排序：·按關(guān)鍵字的取值范圍確定箱子數(shù)，按關(guān)鍵字投入箱子，鏈接所有非空箱。
·箱排序的平均時間復(fù)雜度是線性的O(n).
·基數(shù)排序：·從低位到高位依次對關(guān)鍵字進行箱排序。
·基數(shù)排序是非就穩(wěn)定的排序，時間復(fù)雜度是O(d*n+d*rd)。
各種排序方法的比較和選擇：·.待排序的記錄數(shù)目n；n較大的要用時間復(fù)雜度為O(nlog2n)的排序方法；
·記錄的大小(規(guī)模)；記錄大最好用鏈表作為存儲結(jié)構(gòu)，而快速排序和堆排序在鏈表上難于實現(xiàn)；
·關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)；
·對穩(wěn)定性的要求；
·語言工具的條件；
·存儲結(jié)構(gòu)；
·時間和輔助空間復(fù)雜度