排序是計算機科學中非常重要的基礎算法之一。無論是在數據分析、數據庫查詢還是圖形界面中，我們都可能會遇到排序問題。本文將介紹幾種常見的排序算法，并提供其C語言實現代碼。排序算法的效率和應用場景有很大關系，不同的算法有不同的時間復雜度和空間復雜度。

1. 冒泡排序（Bubble Sort）

冒泡排序是最簡單的排序算法之一。它通過重復交換相鄰的元素，將最大或最小的元素逐漸“冒泡”到序列的一端。雖然實現簡單，但其時間復雜度較高，通常不適用于大規模數據的排序。

實現邏輯：

冒泡排序的核心思想是通過不斷交換相鄰的元素，將較大的元素逐步“冒泡”到數組的一端。每一輪排序，都會將一個最大（或最小）元素放到正確的位置。具體步驟如下：

1. 從數組的第一個元素開始，依次比較相鄰的元素。如果前一個元素比后一個元素大，就交換它們的位置。
2. 這樣，經過第一輪比較后，最大的元素被移動到數組的最后一個位置。
3. 在下一輪比較時，忽略已經排序好的部分（即已排好序的元素），只比較剩余部分，依此類推。
4. 當某一輪排序中沒有發生任何交換時，說明數組已經有序，可以提前結束排序。

1.1 冒泡排序的C語言實現

#include <stdio.h>// 冒泡排序函數
void bubbleSort(int arr[], int n) {int i, j, temp;// 外層循環控制比較的輪次for (i = 0; i < n-1; i++) {// 內層循環進行相鄰元素的比較與交換for (j = 0; j < n-i-1; j++) {// 如果當前元素大于下一個元素，則交換它們if (arr[j] > arr[j+1]) {temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}
}// 打印數組的函數
void printArray(int arr[], int size) {int i;for (i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr)/sizeof(arr[0]); // 獲取數組長度printf("原始數組: \n");printArray(arr, n);bubbleSort(arr, n); // 調用冒泡排序printf("排序后的數組: \n");printArray(arr, n); // 打印排序后的數組return 0;
}

1.2 時間復雜度：

• 最壞時間復雜度：O(n^2)
• 最好時間復雜度：O(n)（當數組已經有序時）

2. 選擇排序（Selection Sort）

實現邏輯：

選擇排序的核心思想是每一次從未排序部分中選擇一個最小（或最大）元素，并將其放到已排序部分的末尾。具體步驟如下：

1. 從數組的第一個元素開始，假設它是最小的元素，遍歷剩余部分，找到真正的最小元素。
2. 將最小元素與當前元素交換位置。
3. 繼續從下一個元素開始，重復上述操作，直到整個數組有序。

與冒泡排序不同，選擇排序每次只進行一次交換，即使找到最小值，也不會像冒泡排序那樣進行多次交換。

2.1 選擇排序的C語言實現

#include <stdio.h>// 選擇排序函數
void selectionSort(int arr[], int n) {int i, j, minIndex, temp;// 外層循環每次選擇一個最小值for (i = 0; i < n-1; i++) {minIndex = i; // 假設當前元素是最小的// 內層循環找出未排序部分中的最小元素for (j = i+1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j; // 更新最小值的索引}}// 交換當前元素和最小元素temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}
}// 打印數組的函數
void printArray(int arr[], int size) {int i;for (i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {64, 25, 12, 22, 11};int n = sizeof(arr)/sizeof(arr[0]); // 獲取數組長度printf("原始數組: \n");printArray(arr, n);selectionSort(arr, n); // 調用選擇排序printf("排序后的數組: \n");printArray(arr, n); // 打印排序后的數組return 0;
}

2.2 時間復雜度：

• 最壞時間復雜度：O(n^2)
• 最好時間復雜度：O(n^2)

3. 插入排序（Insertion Sort）

插入排序將數組分為已排序部分和未排序部分，每次取未排序部分的第一個元素，將其插入到已排序部分的合適位置，直到整個數組有序。

實現邏輯：

插入排序的核心思想是將數組分為已排序和未排序兩部分，依次將未排序部分的元素插入到已排序部分的合適位置。具體步驟如下：

1. 從第二個元素開始，將其與前面的元素進行比較，找到它應該插入的位置。
2. 將插入位置之后的元素依次右移，直到找到合適的位置。
3. 將當前元素插入到合適位置。
4. 重復上述操作，直到數組全部有序。

3.1 插入排序的C語言實現

#include <stdio.h>// 插入排序函數
void insertionSort(int arr[], int n) {int i, key, j;// 從第二個元素開始，每次將一個元素插入到已排序部分for (i = 1; i < n; i++) {key = arr[i]; // 保存當前要插入的元素j = i - 1;// 將已排序部分大于 key 的元素向右移動while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];j = j - 1;}// 將 key 插入到正確的位置arr[j+1] = key;}
}// 打印數組的函數
void printArray(int arr[], int size) {int i;for (i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {12, 11, 13, 5, 6};int n = sizeof(arr)/sizeof(arr[0]); // 獲取數組長度printf("原始數組: \n");printArray(arr, n);insertionSort(arr, n); // 調用插入排序printf("排序后的數組: \n");printArray(arr, n); // 打印排序后的數組return 0;
}

3.2 時間復雜度：

• 最壞時間復雜度：O(n^2)
• 最好時間復雜度：O(n)（當數組已經有序時）

4. 快速排序（Quick Sort）

快速排序是一種分治法排序算法，它通過一個基準元素將數組分為兩個子數組，然后遞歸地排序這兩個子數組。由于其平均時間復雜度較低，快速排序在實際應用中非常高效。

實現邏輯：

快速排序是一種分治算法，其核心思想是通過一個基準元素將數組分為兩部分：一部分比基準元素小，另一部分比基準元素大。然后遞歸地對這兩部分進行排序，直到整個數組有序。具體步驟如下：

1. 選擇一個基準元素（通常選擇數組的第一個元素、最后一個元素或隨機選擇一個元素）。
2. 將數組重新排列，使得所有比基準元素小的元素都在基準元素的左邊，所有比基準元素大的元素都在右邊。
3. 基準元素就位后，將左子數組和右子數組遞歸地進行快速排序。
4. 遞歸的終止條件是子數組的大小為1或0。

快速排序通過分治策略來將大問題分解為小問題，因此具有較高的效率。

4.1 快速排序的C語言實現

#include <stdio.h>// 分區操作：將數組分為兩個子數組
int partition(int arr[], int low, int high) {int pivot = arr[high]; // 選擇最右側元素作為基準int i = low - 1; // i 是已排序部分的邊界// 遍歷數組，將小于基準的元素放到左邊，大于基準的放到右邊for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++; // 更新已排序部分的邊界// 交換 arr[i] 和 arr[j]int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 將基準元素放到正確位置int temp = arr[i+1];arr[i+1] = arr[high];arr[high] = temp;return i + 1; // 返回基準元素的索引
}// 快速排序函數
void quickSort(int arr[], int low, int high) {if (low < high) {// 獲取分區后的基準元素索引int pi = partition(arr, low, high);// 分別對左子數組和右子數組進行快速排序quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}// 打印數組的函數
void printArray(int arr[], int size) {int i;for (i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr)/sizeof(arr[0]); // 獲取數組長度printf("原始數組: \n");printArray(arr, n);quickSort(arr, 0, n-1); // 調用快速排序printf("排序后的數組: \n");printArray(arr, n); // 打印排序后的數組return 0;
}

4.2 時間復雜度：

• 最壞時間復雜度：O(n^2)
• 最好時間復雜度：O(n log n)
• 平均時間復雜度：O(n log n)

5. 歸并排序（Merge Sort）

歸并排序也是一種分治法排序算法，它將數組分為兩個子數組，分別對它們排序后再合并。歸并排序是一個穩定的排序算法，適用于大規模數據。

實現邏輯：

歸并排序也是一種分治算法，核心思想是將數組分成兩個子數組，分別對其進行排序，然后將兩個已排序的子數組合并成一個大的有序數組。具體步驟如下：

1. 將數組遞歸地分割成兩半，直到每個子數組只包含一個元素。
2. 然后將這些小的有序子數組逐步合并成更大的有序子數組。
3. 在合并時，始終保持兩個子數組之間的有序性。

歸并排序的關鍵操作是合并兩個已排序的子數組，合并過程是線性時間復雜度。

5.1 歸并排序的C語言實現

#include <stdio.h>// 合并兩個已排序的子數組
void merge(int arr[], int l, int m, int r) {int n1 = m - l + 1; // 左子數組的大小int n2 = r - m;     // 右子數組的大小// 創建臨時數組int L[n1], R[n2];// 將數據拷貝到臨時數組for (int i = 0; i < n1; i++)L[i] = arr[l + i];for (int j = 0; j < n2; j++)R[j] = arr[m + 1 + j];int i = 0, j = 0, k = l;// 合并兩個臨時數組while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 將剩余的元素拷貝到原數組while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}
}// 歸并排序函數
void mergeSort(int arr[], int l, int r) {if (l < r) {int m = l + (r - l) / 2; // 計算中間位置mergeSort(arr, l, m); // 對左半部分進行歸并排序mergeSort(arr, m + 1, r); // 對右半部分進行歸并排序merge(arr, l, m, r); // 合并兩個已排序的子數組}
}// 打印數組的函數
void printArray(int arr[], int size) {int i;for (i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr)/sizeof(arr[0]); // 獲取數組長度printf("原始數組: \n");printArray(arr, n);mergeSort(arr, 0, n-1); // 調用歸并排序printf("排序后的數組: \n");printArray(arr, n); // 打印排序后的數組return 0;
}

5.2 時間復雜度：

• 最壞時間復雜度：O(n log n)
• 最好時間復雜度：O(n log n)
• 平均時間復雜度：O(n log n)

---

總結

本文介紹了幾種經典的排序算法，包括冒泡排序、選擇排序、插入排序、快速排序和歸并排序。每種排序算法都有其特定的優缺點，適用于不同的應用場景。在選擇排序算法時，需要根據數據的規模、要求的時間復雜度以及是否需要穩定排序來做出決策。通過理解這些排序算法的實現和性能特點，您可以在實際開發中更加高效地選擇合適的排序算法。

版權聲明：本文為原創文章，轉載請注明出處。