概念
排序問題可以分為內(nèi)部排序和外部排序。若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序；反之，若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為外部排序。
在內(nèi)部排序中，若對于兩個相等的元素 K i 和 K j （ i ≠ j ） Ki 和 Kj（i≠j） Ki和Kj（i=j），在排序前的序列中 R i Ri Ri 領(lǐng)先于 R j Rj Rj（即 i < j i<j i<j），排序后的序列中 Ri 仍領(lǐng)先于 Rj，則稱所用的排序方法是穩(wěn)定的；反之，若可能使排序后的序列中 R j Rj Rj 領(lǐng)先于 R i Ri Ri，則稱所用的排序方法是非穩(wěn)定的。
-
當待排序的數(shù)據(jù)集包含多個關(guān)鍵字，并且需要根據(jù)其中一個關(guān)鍵字進行排序，同時又需要維持其他關(guān)鍵字的相對順序時，穩(wěn)定性非常重要。這樣可以確保排序后的結(jié)果在關(guān)鍵字相同時仍然保持正確的順序，不會打亂其他關(guān)鍵字的排序。
-
在一些實際應(yīng)用中，原始數(shù)據(jù)可能已經(jīng)部分有序。如果排序算法是穩(wěn)定的，那么相等元素的相對順序?qū)⒈槐３郑粫茐脑嫉牟糠钟行蛐浴?/p>
-
在某些場景下，排序的穩(wěn)定性是問題的約束條件。例如，如果需要對學(xué)生成績進行排序，并且要求相同分數(shù)的學(xué)生按照其在班級中的考號順序排序，那么只有穩(wěn)定的排序算法才能滿足要求。
插入排序
插入排序的基本思想是將待排序的序列分成已排序和未排序的兩部分，每次從未排序的部分取出第一個元素，插入到已排序部分合適的位置，直到未排序部分為空為止。具體操作如下：
- 在 R [ 1.. i ? 1 ] R[1..i-1] R[1..i?1] 中查找 R [ i ] R[i] R[i] 的插入位置，使得 R [ 1.. j ] . k e y ≤ R [ i ] . k e y < R [ j + 1.. i ? 1 ] . k e y R[1..j].key ≤ R[i].key < R[j+1..i-1].key R[1..j].key≤R[i].key<R[j+1..i?1].key；
- 將 R [ j + 1.. i ? 1 ] R[j+1..i-1] R[j+1..i?1] 中的所有記錄均后移一個位置；
- 將 R [ i ] R[i] R[i] 插入（復(fù)制）到 R [ j + 1 ] R[j+1] R[j+1] 的位置上。
這樣就完成了一次插入操作，對于待排序的序列，重復(fù)執(zhí)行以上操作直到全部排序完成。
直接插入排序
直接插入排序的基本思想是將待排序的序列分成已排序和未排序的兩部分，每次從未排序的部分取出第一個元素，插入到已排序部分合適的位置，直到未排序部分為空為止。具體操作如下：
- 初始時，將 R [ 1 ] R[1] R[1] 看作是有序區(qū)， R [ 2.. n ] R[2..n] R[2..n] 構(gòu)成無序區(qū)；
- 依次將無序區(qū)的元素插入到有序區(qū)中，使得有序區(qū)始終有序。插入操作包括以下三步：
1）在 R [ 1.. i ? 1 ] R[1..i-1] R[1..i?1] 中查找 R [ i ] R[i] R[i] 的插入位置，使得 R [ 1.. j ] . k e y ≤ R [ i ] . k e y < R [ j + 1.. i ? 1 ] . k e y R[1..j].key ≤ R[i].key < R[j+1..i-1].key R[1..j].key≤R[i].key<R[j+1..i?1].key；
2）將 R [ j + 1.. i ? 1 ] R[j+1..i-1] R[j+1..i?1] 中的所有記錄均后移一個位置；
3）將 R [ i ] R[i] R[i] 插入（復(fù)制）到 R [ j + 1 ] R[j+1] R[j+1] 的位置上。 - 重復(fù)執(zhí)行 2 直到無序區(qū)為空，排序完成。
void InsertionSort(SqList& L) {
// 對順序表 L 作直接插入排序
for (int i = 2; i <= L.length; ++i) {
if (L.r[i].key < L.r[i - 1].key) {
// 將當前待排序的記錄暫存到監(jiān)視哨中，等待插入
L.r[0] = L.r[i];
int j;
for (j = i - 1; L.r[0].key < L.r[j].key; --j) {
// 將記錄后移，尋找插入位置
L.r[j + 1] = L.r[j];
}
L.r[j + 1] = L.r[0]; // 插入到正確位置
}
}
}
最好的情況：
- 序列順序有序，比較的次數(shù)：n-1，移動的次數(shù)：0
最壞的情況：
時間復(fù)雜度大概
O
(
n
2
)
O(n^2)
O(n2)
其他插入排序
折半插入
void BiInsertionSort(SqList &L) {
for (int i = 2; i <= L.length; ++i) {
L.r[0] = L.r[i]; // 將 L.r[i] 暫存到 L.r[0]
int low = 1, high = i - 1;
while (low <= high) {
int mid = (low + high) / 2; // 折半
if (L.r[0].key < L.r[mid].key)
high = mid - 1; // 插入點在低半?yún)^(qū)
else
low = mid + 1; // 插入點在高半?yún)^(qū)
}
for (int j = i - 1; j >= high + 1; --j) {
L.r[j + 1] = L.r[j]; // 記錄后移
}
L.r[high + 1] = L.r[0]; // 插入
}
}
L.r[high + 1] = L.r[0]; // 插入是在
h
i
g
h
+
1
high+1
high+1的位置插入（此時，low>high）
希爾排序
希爾排序（又稱縮小增量排序）
基本思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。所謂“宏觀”調(diào)整，指的是“跳躍式”的插入排序。具體做法為：
1.將記錄序列分成若干子序列，分別對每個子序列進行插入排序。
2.待整個序列中的紀錄‘基本有序’時，再對全體記錄進行一次直接插入排序。
例如：將 n n n個記錄分成 d d d個子序列：
R [ 1 ] ， R [ 1 + d ] ， R [ 1 + 2 d ] ， … ， R [ 1 + k d ] { R[1]，R[1+d]，R[1+2d]，…，R[1+kd] } R[1]，R[1+d]，R[1+2d]，…，R[1+kd]
R [ 2 ] ， R [ 2 + d ] ， R [ 2 + 2 d ] ， … ， R [ 2 + k d ] { R[2]，R[2+d]，R[2+2d]，…，R[2+kd] } R[2]，R[2+d]，R[2+2d]，…，R[2+kd]
… … …
R [ d ] ， R [ 2 d ] ， R [ 3 d ] ， … ， R [ k d ] ， R [ ( k + 1 ) d ] { R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d] } R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]
其中， d d d 稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為 1。
冒泡排序
void BubbleSort(Elem R[], int n) {
int i = n;
while (i > 1) {
int lastExchangeIndex = 1;
for (int j = 1; j < i; j++) {
if (R[j+1].key < R[j].key) {
Swap(R[j], R[j+1]);
lastExchangeIndex = j;
} //if
} //for
i = lastExchangeIndex; // 本趟進行過交換的最后一個記錄的位置
} // while
} // BubbleSort
-
起泡排序的結(jié)束條件為，最后一趟沒有進行“交換記錄”。
-
一般情況下，每經(jīng)過一趟“起泡”，i減1，但并不是每趟都如此。具體來說，每一趟排序時，我們都記錄下最后一次交換操作的位置，如果在一趟排序結(jié)束之后，最后一次交換操作的位置和上一趟排序結(jié)束時的位置相同，那么說明這次排序并沒有進行任何交換操作，也就是說從該位置之后的元素已經(jīng)有序。此時，我們便可以認為序列已經(jīng)有序了，因此結(jié)束算法的執(zhí)行。
時間復(fù)雜度大概
O
(
n
2
)
O(n^2)
O(n2)
快速排序
找一個記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動至該記錄之后。
經(jīng)過一趟排序之后，記錄的無序序列 R [ s . . t ] R[s..t] R[s..t]將分割成兩部分： R [ s . . i ? 1 ] R[s..i-1] R[s..i?1]和 R [ i + 1.. t ] R[i+1..t] R[i+1..t]，且 R [ j ] . k e y ≤ R [ i ] . k e y ≤ R [ p ] . k e y ( s ≤ j ≤ i ? 1 ) ?樞軸? ( i + 1 ≤ p ≤ t ) R[j].key\leq R[i].key \leq R[p].key (s\leq j\leq i-1)~ 樞軸 ~(i+1\leq p\leq t) R[j].key≤R[i].key≤R[p].key(s≤j≤i?1)?樞軸?(i+1≤p≤t)其中 i i i表示樞軸記錄的位置， j ≤ i ? 1 j \leq i-1 j≤i?1的記錄的關(guān)鍵字都小于等于樞軸的關(guān)鍵字， p ≥ i + 1 p \geq i+1 p≥i+1的記錄的關(guān)鍵字都大于等于樞軸的關(guān)鍵字。注意，這里假設(shè)樞軸所在的位置不是 s s s或 t t t，否則就沒有對應(yīng)的一側(cè)了。
int Partition (RedType& R[], int low, int high) {
pivotkey = R[low].key; // 用子表的第一個記錄作樞軸記錄
while (low < high) { // 從表的兩端交替地向中間掃描
while (low < high && R[high].key >= pivotkey)
--high;
R[low] ←→ R[high]; // 將比樞軸記錄小的記錄交換到低端
while (low < high && R[low].key <= pivotkey)
++low;
R[low] ←→ R[high]; // 將比樞軸記錄大的記錄交換到高端
}
return low; // 返回樞軸所在位置
} // Partition
void QSort (RedType & R[], int low, int high) {
// 對記錄序列R[low..high]進行快速排序
if (low < high) { // 長度大于1
pivotloc = Partition(R, low, high);
// 對 R[s..t] 進行一次劃分
QSort(R, low, pivotloc - 1);
// 對低子序列遞歸排序，pivotloc是樞軸位置
QSort(R, pivotloc + 1, high); // 對高子序列遞歸排序
}
} // QSort
時間復(fù)雜度： O ( n l o g n ) O(nlogn) O(nlogn)
選擇排序
從未排序的序列選擇一個最小的元素排到有序序列里
和插入排序的區(qū)別：
- 插入：找到未排序序列的第一個元素，并在有序序列里面查找到插入位置
- 選擇：找到未排序序列最小的元素，并添加到有序序列的最后處
void SelectSort(Elem R[], int n) {
// 對記錄序列 R[1..n] 進行簡單選擇排序。
for (int i = 1; i < n; ++i) {
// 選擇第 i 小的記錄，并交換到位
int j = SelectMinKey(R, i);
// 在 R[i..n] 中選擇關(guān)鍵字最小的記錄
if (i != j) {
// 與第 i 個記錄交換
R[i] ? R[j];
}
}
} // SelectSort
堆排序
光看定義還有點不太明白，但是根據(jù)樹就應(yīng)該很明晰了
建大頂堆
自下而上
歸并排序
- 歸并排序的過程基于下列基本思想進行： 將兩個或兩個以上的有序子序列 “歸并” 為一個有序序列
- 在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列
比較簡單，看一下即可
習題
各個排序
最后1個考試不涉及
-
直接插入排序：503 087 512 061 908 170 897 275 653 426
第一趟結(jié)果：087 503 512 061 908 170 897 275 653 426
第二趟結(jié)果：087 503 512 061 908 170 897 275 653 426
第三趟結(jié)果：061 087 503 512 908 170 897 275 653 426
第四趟結(jié)果：061 087 503 512 908 170 897 275 653 426
第五趟結(jié)果：061 087 170 503 512 908 897 275 653 426
第六趟結(jié)果：061 087 170 503 512 897 908 275 653 426
第七趟結(jié)果：061 087 170 275 503 512 897 908 653 426
第八趟結(jié)果：061 087 170 275 503 512 653 897 908 426
第九趟結(jié)果：061 087 170 275 426 503 512 653 897 908粗體為已經(jīng)排好序的序列 -
希爾排序初始關(guān)鍵字： 503 087 512 061 908 170 897 275 653 426
第一趟結(jié)果：d[1]=5 170 087 275 061 426 503 897 512 653 908
第二趟結(jié)果：d[2]=3 061 087 275 170 426 503 897 512 653 908
第三趟結(jié)果：d[3]=1 061 087 170 275 426 503 512 653 897 908主要注意一下希爾排序是以下標號的后x個作排序——在d[1]=5，a[0]=503是a[5]=170排序的 -
快速排序
注意，快速排序不是把比Key小的數(shù)直接隨便放到Key前面，是用low和high遍歷出來的 -
堆排序
小頂堆 -
歸并排序（自底向上）
503 087 512 061 908 170 897 275 653 426
(087 503) (061 512) (170 908) (275 897) (426 653)
(061 087 503 512) (170 275 897 908) (426 653)
(061 087 170 275 503 512 897 908) (426 653)
(061 087 170 275 426 503 512 653 897 908)
堆排序
第4問的答案應(yīng)該是錯的
監(jiān)視哨
void directInsertSort(int L[], int k) {
int i, j;
for (i = 2; i <= k; i++) {
L[k+1] = L[i];
j = i - 1;
while (L[j] > L[0]) {
L[j + 1] = L[j];
j--;
}
L[j + 1] = L[k+1];
}
}
設(shè)計算法
void process(int A[n]) {
int low = 0;
int high = n - 1;
while (low < high) {
while (low < high && A[low] < 0)
low++;
while (low < high && A[high] > 0)
high++;
if (low < high) {
// 交換 A[low] 和 A[high]
int temp = A[low];
A[low] = A[high];
A[high] = temp;
low++;
high--;
}
}
return;
}
雙指針法
時間復(fù)雜度
O
(
n
)
O(n)
O(n)文章來源：http://www.zghlxwxcb.cn/news/detail-491032.html
荷蘭國旗問題
文章來源地址http://www.zghlxwxcb.cn/news/detail-491032.html
typedef enum {RED, WHITE, BLUE} color; // 定義枚舉類型表示三種顏色
void Flag_Arrange(color a[], int n) {
int i = 0;
int j = 0;
int k = n - 1;
while (j <= k) {
switch (a[j]) {
case RED:
// a[i] 與 a[j] 交換
// 增加 i 和 j 的值，同時繼續(xù)處理下一個元素
swap(a[i], a[j]);
i++;
j++;
break;
case WHITE:
// 當遇到白色時，只需要將 j 向右移動一位
j++;
break;
case BLUE:
// a[j] 與 a[k] 交換
// 不增加 j 的值，因為可能需要再次檢查交換后的 a[j]
// 減少 k 的值，將藍色元素移至數(shù)組末尾
swap(a[j], a[k]);
k--;
break;
}
}
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法·第10章【內(nèi)部排序】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
