一、直接插入排序 (Insertion Sort)

基本思想

直接插入排序是一種簡(jiǎn)單直觀的排序算法，就像我們打撲克牌時(shí)的操作：每次摸到一張牌，都會(huì)把它插入到手中已排好序的牌的正確位置。通過這種方式，逐步構(gòu)建一個(gè)有序序列。

步驟

1. 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序。

2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描。

3. 如果該元素（已排序）大于新元素，將該元素移到下一位置。

4. 重復(fù)步驟3，直到找到已排序的元素小于或等于新元素的位置。

5. 將新元素插入到該位置后。

6. 重復(fù)步驟2~5，直到所有元素都被排序。

C語言代碼示例

void InsertSort(int* a, int n) {for (int i = 1; i < n; i++) { // 從第二個(gè)元素開始int temp = a[i]; // 當(dāng)前要插入的元素int j = i - 1;    // 從已排序部分的最后一個(gè)元素開始比較while (j >= 0 && a[j] > temp) {a[j + 1] = a[j]; // 如果當(dāng)前元素大于新元素，向后移動(dòng)j--;}a[j + 1] = temp; // 找到插入位置后，插入新元素}
}

算法分析

• 時(shí)間復(fù)雜度：

  • 最好情況（已排好序）：O(n)，每個(gè)元素只需比較一次。

  • 平均情況和最壞情況（逆序）：O(n2)。

• 空間復(fù)雜度：O(1)，只需要一個(gè)臨時(shí)變量。

• 穩(wěn)定性：穩(wěn)定。相等元素的相對(duì)位置不會(huì)改變。

• 適用場(chǎng)景：適用于小型數(shù)據(jù)集或基本有序的數(shù)據(jù)集，效率較高。

---

二、冒泡排序 (Bubble Sort)

基本思想

冒泡排序是一種簡(jiǎn)單但效率較低的排序算法。它的名字來源于其工作方式：通過重復(fù)遍歷待排序的數(shù)列，比較相鄰的兩個(gè)元素，如果順序錯(cuò)誤就交換它們。每次遍歷后，最大的元素會(huì)像氣泡一樣“浮”到數(shù)列的末尾。

步驟

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們。

2. 對(duì)每一對(duì)相鄰元素做同樣的操作，從第一個(gè)元素到最后一個(gè)元素。經(jīng)過這一輪后，最大的元素會(huì)移動(dòng)到數(shù)列的末尾。

3. 重復(fù)上述步驟，但每次減少比較的范圍，因?yàn)樽詈蟮脑匾呀?jīng)排好序。

4. 繼續(xù)重復(fù)，直到整個(gè)數(shù)列有序。

C語言代碼示例

void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) { // 遍歷 n-1 次for (int j = 0; j < n - i - 1; j++) { // 每次減少比較范圍if (arr[j] > arr[j + 1]) { // 如果順序錯(cuò)誤，交換int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}

算法分析

• 時(shí)間復(fù)雜度：

  • 最好情況（已排好序）：O(n)，因?yàn)橹恍枰闅v一次。

  • 平均情況和最壞情況（逆序）：O(n2)。

• 空間復(fù)雜度：O(1)，只需要一個(gè)臨時(shí)變量。

• 穩(wěn)定性：穩(wěn)定。相等元素的相對(duì)位置不會(huì)改變。

• 適用場(chǎng)景：由于效率較低，通常只用于教學(xué)示例，不適合實(shí)際應(yīng)用。

---

三、希爾排序 (Shell Sort)

基本思想

希爾排序是插入排序的一種改進(jìn)版本，通過引入“增量”來分組排序，減少數(shù)據(jù)的移動(dòng)次數(shù)。它將待排序的元素分成若干組，每組內(nèi)的元素間距為某個(gè)增量，然后對(duì)每組進(jìn)行插入排序。隨著增量逐漸減小，最終增量為1時(shí)，整個(gè)序列基本有序，此時(shí)再進(jìn)行一次直接插入排序即可完成。

步驟

1. 選擇一個(gè)增量序列，例如 [n/2, n/4, ..., 1]。

2. 按增量序列的個(gè)數(shù)進(jìn)行多趟排序。

3. 每趟排序中，根據(jù)當(dāng)前增量將序列分成若干子序列，對(duì)每個(gè)子序列進(jìn)行插入排序。

4. 增量逐步減小，直到增量為1，完成排序。

C語言代碼示例

void shellSort(int arr[], int n) {for (int gap = n / 2; gap > 0; gap /= 2) { // 增量逐步減小for (int i = gap; i < n; i++) { // 對(duì)每個(gè)子序列進(jìn)行插入排序int temp = arr[i];int j = i;while (j >= gap && arr[j - gap] > temp) {arr[j] = arr[j - gap];j -= gap;}arr[j] = temp;}}
}

算法分析

• 時(shí)間復(fù)雜度：

  • 最好情況：O(n log n)。

  • 平均情況：取決于增量序列，通常在 O(n log2 n) 到 O(n^(3/2)) 之間。

  • 最壞情況：O(n2)。

• 空間復(fù)雜度：O(1)。

• 穩(wěn)定性：不穩(wěn)定。由于分組排序，可能會(huì)破壞元素的相對(duì)順序。

• 適用場(chǎng)景：適用于中等規(guī)模的數(shù)據(jù)集，性能優(yōu)于簡(jiǎn)單排序算法。

---

四、選擇排序 (Selection Sort)

基本思想

選擇排序是一種簡(jiǎn)單直觀的排序算法。它的核心思想是：每次從未排序的部分中找到最小（或最大）的元素，放到已排序部分的末尾。通過逐步縮小未排序部分的范圍，最終完成排序。

步驟

1. 在未排序的序列中找到最小元素。

2. 將最小元素與未排序部分的第一個(gè)元素交換。

3. 將已排序部分的邊界向后移動(dòng)一位。

4. 重復(fù)上述步驟，直到所有元素都被排序。

C語言代碼示例

void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) { // 遍歷 n-1 次int min_idx = i; // 假設(shè)當(dāng)前元素為最小值for (int j = i + 1; j < n; j++) { // 找到未排序部分的最小值if (arr[j] < arr[min_idx]) {min_idx = j;}}// 交換最小值與當(dāng)前元素int temp = arr[min_idx];arr[min_idx] = arr[i];arr[i] = temp;}
}

算法分析

• 時(shí)間復(fù)雜度：

  • 最好、平均和最壞情況：O(n2)。

• 空間復(fù)雜度：O(1)。

• 穩(wěn)定性：不穩(wěn)定。交換操作可能會(huì)破壞相等元素的相對(duì)順序。

• 適用場(chǎng)景：實(shí)現(xiàn)簡(jiǎn)單，適合小型數(shù)據(jù)集或教學(xué)示例。

---

五、堆排序 (Heap Sort)

基本思想

堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的排序算法。堆是一種特殊的完全二叉樹，分為大頂堆和小頂堆。堆排序利用堆的性質(zhì)，快速找到最大或最小元素，并逐步構(gòu)建有序序列。

步驟

1. 將待排序的序列構(gòu)建成一個(gè)大頂堆（升序排序）或小頂堆（降序排序）。

2. 將堆頂元素（最大值或最小值）與末尾元素交換。

3. 將剩余的元素重新調(diào)整為堆。

4. 重復(fù)上述步驟，直到所有元素都被排序。

C語言代碼示例

void heapify(int arr[], int n, int i) {int largest = i; // 假設(shè)當(dāng)前節(jié)點(diǎn)為最大值int left = 2 * i + 1; // 左子節(jié)點(diǎn)int right = 2 * i + 2; // 右子節(jié)點(diǎn)if (left < n && arr[left] > arr[largest]) {largest = left; // 如果左子節(jié)點(diǎn)更大}if (right < n && arr[right] > arr[largest]) {largest = right; // 如果右子節(jié)點(diǎn)更大}if (largest != i) {// 交換當(dāng)前節(jié)點(diǎn)與最大值節(jié)點(diǎn)int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;// 遞歸調(diào)整子樹heapify(arr, n, largest);}
}void heapSort(int arr[], int n) {// 構(gòu)建大頂堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 逐步提取堆頂元素for (int i = n - 1; i >= 0; i--) {// 交換堆頂元素與末尾元素int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 調(diào)整剩余元素為堆heapify(arr, i, 0);}
}

算法分析

• 時(shí)間復(fù)雜度：

  • 最好、平均和最壞情況：O(n log n)。

• 空間復(fù)雜度：O(1)。

• 穩(wěn)定性：不穩(wěn)定。交換操作可能會(huì)破壞相等元素的相對(duì)順序。

• 適用場(chǎng)景：適合大數(shù)據(jù)量的排序，性能穩(wěn)定。