2023計算機考研初試在即，在最后階段建議各位同學(xué)將知識點再系統(tǒng)復(fù)習(xí)一遍，以免有所遺漏！2022計算機考研數(shù)據(jù)結(jié)構(gòu)第七單元知識點包含內(nèi)排序、排序碼、直接插入排序等內(nèi)容。高頓考研為大家整理了2022計算機考研數(shù)據(jù)結(jié)構(gòu)第七單元知識點的詳細(xì)內(nèi)容，供大家參考復(fù)習(xí)！
內(nèi)排序：元素個數(shù)不多，排序過程只用到內(nèi)存。
排序碼：作為排序依據(jù)的關(guān)鍵字(通常是次關(guān)鍵字)。
排序的穩(wěn)定性：在線性表中可能存在多個排序碼相同的元素，如果排序前后這些元素的相對位置有可能被改變，則這種排序方法為不穩(wěn)定的排序方法。
簡單排序：從所有元素中選出排序碼最小的元素與第一個元素交換位置，從第一個元素之后的元素中選出排序碼最小的元素與第二個元素交換位置，以此類推。
比較次數(shù)與初始排列順序無關(guān)，為(n-1)加到1。
移動次數(shù)與初始排列順序有關(guān)，最多移動3(n-1)次(賦值操作有3次，包括temp)。
算法執(zhí)行時間為O(n2)。
算法所需空間大小為O(1)。
為不穩(wěn)定排序。
直接插入排序：將第一個元素看成一個有序表，將第二個元素插入該表，再插入第三個，每次插入需要通過比較來決定元素間的相對位置。
比較次數(shù)，最少為n-1次，最多為n加到2。
移動次數(shù)最少為2(n-1)次，最多為n+1加到3。
算法執(zhí)行平均時間為O(n2)。
算法執(zhí)行時間最長為O(n2)。
算法所需空間大小為O(1)。
為穩(wěn)定排序。
冒泡排序：先在n個元素間逐個比較，將較大的元素移到右邊，一趟過后，最大的元素置于最右端，再在n-1個元素之間比較，以此類推，當(dāng)某趟沒有出現(xiàn)交換情況或i<2，結(jié)束排序。(設(shè)置swap記錄是否有過交換)
比較次數(shù)，最少為n-1次(從小到大排列好時最少)，最多為n-1加到1。
移動次數(shù)，最少不移動，最多為3(n-1加到1)(從大到小排列時最多)。
算法執(zhí)行平均時間為O(n2)。
算法執(zhí)行時間最壞為O(n2)。
算法所需空間大小為O(1)。
為穩(wěn)定排序。
快速排序：從n個元素中任取一個元素，將其余元素根據(jù)排序碼大小分別置于該元素兩邊，再對兩邊以這種方式繼續(xù)排序。
算法平均執(zhí)行時間為O(nlog2n)。
最壞情況為O(n2)。
算法所需空間大小為O(log2n)。
為不穩(wěn)定排序。
實現(xiàn)：數(shù)據(jù)最開始存放在數(shù)組的1~n空間內(nèi)
以第一個元素為標(biāo)準(zhǔn)，將它置于0處，設(shè)置i=1，j=n
將j與標(biāo)準(zhǔn)元素相比較，如果j較大，則j-1(較大的數(shù)留在原處)
如果j較小，則將j與i交換(較小的數(shù)置于另一邊)
交換之后，將i與標(biāo)準(zhǔn)元素比較，如果i較小，則i+1(較小的數(shù)留在原處)
如果i較大，則將i與j交換(較大的數(shù)置于另一邊)
交換之后，繼續(xù)將j與標(biāo)準(zhǔn)元素比較(從兩邊逐步比較，逼近中間)
i和j相遇之后，結(jié)束第一趟排序，將標(biāo)準(zhǔn)元素置于i和j所在的位置
歸并排序：將n個元素視作n個有序表，將相鄰的有序表歸并，得到n/2個長度為2的有序表，以此類推，每次歸并會進行內(nèi)部的比較移動。
歸并次數(shù)為log2n。
每次歸并的比較次數(shù)不超過n-1。
移動次數(shù)都為n。
算法執(zhí)行時間為O(nlog2n)。
算法所需空間大小為O(n)。
為穩(wěn)定排序。
實現(xiàn)：設(shè)置i，j，k，i和j指向有序表的兩端，k指向輔助空間，每次歸并時，將i和j中較小的一個移入k中，并將移動的i或j移向中間，實現(xiàn)有序表的內(nèi)部排序。
堆排序：按堆的定義，將元素調(diào)整為堆，交換第一個元素和最后一個元素，再將n-1個元素調(diào)整為堆，再交換第一個元素和最后一個元素，以此類推。
算法執(zhí)行時間為O(nlog2n)。
算法所需空間為O(1)。
為不穩(wěn)定排序。