探索C語言中的常見排序算法
排序算法是計算機科學中至關重要的基礎知識之一，它們能夠幫助我們對數據進行有序排列，從而更高效地進行搜索、插入和刪除操作。在本篇博客中，我們將深入探討C語言中的一些常見排序算法，包括它們的工作原理、實現代碼以及性能比較。
1. 冒泡排序 (Bubble Sort)
冒泡排序是一種簡單但低效的排序算法，它通過多次遍歷數組，每次比較相鄰的元素并交換位置，將最大的元素逐漸“冒泡”到數組的末尾。雖然不太適用于大型數據集，但冒泡排序在教學和理解排序概念時仍具有一定的價值。
void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交換位置int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}2. 選擇排序 (Selection Sort)
選擇排序是一種每次選取未排序部分中最小（或最大）的元素，然后將其放置到已排序部分的末尾。雖然比冒泡排序稍微快一些，但仍然不適用于大型數據集。
void selectionSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 交換位置int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}
}3. 插入排序 (Insertion Sort)
插入排序的思想是將未排序的元素逐個插入到已排序部分的合適位置。它對于小型數據集和部分有序的數據集表現良好。
void insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}4. 快速排序 (Quick Sort)
快速排序是一種高效的分治排序算法，它通過選擇一個基準元素，將數組分成左右兩個子數組，然后遞歸地對子數組進行排序。雖然在大多數情況下表現出色，但在最壞情況下可能會導致性能下降。
void quickSort(int arr[], int low, int high) {if (low < high) {int pivot = partition(arr, low, high);quickSort(arr, low, pivot - 1);quickSort(arr, pivot + 1, high);}
}int partition(int arr[], int low, int high) {int pivot = arr[high];int i = (low - 1);for (int j = low; j <= high - 1; j++) {if (arr[j] < pivot) {i++;// 交換位置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);
}5. 歸并排序 (Merge Sort)
歸并排序是一種穩定的分治排序算法，它將數組分成兩個子數組，遞歸地對子數組進行排序，然后將排序好的子數組合并為一個有序數組。
void mergeSort(int arr[], int left, int right) {if (left < right) {int middle = left + (right - left) / 2;mergeSort(arr, left, middle);mergeSort(arr, middle + 1, right);merge(arr, left, middle, right);}
}void merge(int arr[], int left, int middle, int right) {int n1 = middle - left + 1;int n2 = right - middle;int L[n1], R[n2];for (int i = 0; i < n1; i++) {L[i] = arr[left + i];}for (int j = 0; j < n2; j++) {R[j] = arr[middle + 1 + j];}int i = 0, j = 0, k = left;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++;}
}總結
在本篇博客中，我們對C語言中的一些常見排序算法進行了簡要介紹。每個算法都有其獨特的特點和適用范圍，因此在實際應用中需要根據問題的性質選擇合適的算法。要深入理解這些算法的工作原理，最好的方法是通過實際
)
