|
|
以下是C語言中常用的十種排序算法：
1. 冒泡排序（Bubble Sort）
冒泡排序的核心思想是反復(fù)交換相鄰的未按順序排列的元素，通過多次遍歷數(shù)組，每次將一個未排好序的元素放到合適的位置，最終得到有序數(shù)組。時間復(fù)雜度為O(n^2)，不適用于大規(guī)模數(shù)據(jù)。
- 優(yōu)點：簡單易懂，實現(xiàn)容易。
- 缺點：效率較低，對大規(guī)模數(shù)據(jù)排序耗時長，不適合生產(chǎn)環(huán)境使用。
- 應(yīng)用場景：適用于小規(guī)模數(shù)據(jù)排序以及教學(xué)示例等場景。
## 2. 選擇排序（Selection Sort）
選擇排序的主要思想是在未排序的序列中選擇最小（或最大）的元素放到已排序序列的末尾。與冒泡排序不同的是，選擇排序每次只會進(jìn)行一次交換操作，因此其時間復(fù)雜度仍然為O(n^2)。
- 優(yōu)點：實現(xiàn)容易，內(nèi)存開銷較小。
- 缺點：效率較低，在大規(guī)模數(shù)據(jù)下表現(xiàn)不佳。
- 應(yīng)用場景：適用于小規(guī)模數(shù)據(jù)排序以及結(jié)構(gòu)性較差的數(shù)據(jù)排序。
## 3. 插入排序（Insertion Sort）
插入排序的核心思想是將待排序的序列分成已排序和未排序兩部分，每次從未排序的序列中選擇一個元素插入到已排序的序列中，直至所有元素都被插入。與前兩種排序算法不同的是，插入排序在處理近乎有序的數(shù)組時表現(xiàn)較優(yōu)，其時間復(fù)雜度為O(n^2)。
- 優(yōu)點：實現(xiàn)簡單，在排序小規(guī)模數(shù)據(jù)或近乎有序的數(shù)據(jù)時表現(xiàn)良好。
- 缺點：效率較低，在大規(guī)模數(shù)據(jù)下表現(xiàn)不佳。
- 應(yīng)用場景：適用于小規(guī)模數(shù)據(jù)排序以及對近乎有序的數(shù)據(jù)進(jìn)行排序。
## 4. 希爾排序（Shell Sort）
希爾排序是插入排序的改進(jìn)版，其主要思想是將待排序的序列按照一個增量序列（通常是n/2，n/4，...，1）分成若干個子序列，對每個子序列進(jìn)行插入排序。然后縮小增量，再進(jìn)行插入排序。最終當(dāng)增量為1時，整個序列就被排好序了。由于希爾排序多次分組排序，因此其時間復(fù)雜度介于O(n)和O(n^2)之間。
- 優(yōu)點：相較于插入排序，希爾排序的效率更高。
- 缺點：時間復(fù)雜度上界難以精確，而且受增量序列的影響較大。
- 應(yīng)用場景：適用于中等規(guī)模數(shù)據(jù)排序，比插入排序更加高效。
## 5. 歸并排序（Merge Sort）
歸并排序是一種比較高效的排序算法，其主要思想是將待排序的序列分成左右兩部分，對每部分進(jìn)行遞歸排序，最后將兩個有序的子序列合并成一個有序的序列。歸并排序的時間復(fù)雜度為O(nlogn)，但其需要開辟額外的空間用于存放臨時序列，因此其空間復(fù)雜度較高。
- 優(yōu)點：時間復(fù)雜度穩(wěn)定，具有很好的可擴(kuò)展性。
- 缺點：需要額外的內(nèi)存空間。
- 應(yīng)用場景：適用于大規(guī)模數(shù)據(jù)排序，對穩(wěn)定性和可擴(kuò)展性要求較高的場景。
## 6. 快速排序（Quick Sort）
快速排序也是一種高效的排序算法，其主要思想是選擇一個基準(zhǔn)元素，將待排序的序列分成兩部分，一部分所有元素都小于等于基準(zhǔn)元素，另一部分所有元素都大于等于基準(zhǔn)元素。然后對這兩部分分別遞歸調(diào)用快速排序函數(shù)。快速排序的時間復(fù)雜度為O(nlogn)，但其在最壞情況下性能會退化為O(n^2)。
- 優(yōu)點：效率較高，在大規(guī)模數(shù)據(jù)下表現(xiàn)良好。
- 缺點：不穩(wěn)定，存在最壞時間復(fù)雜度O(n^2)的情況。
- 應(yīng)用場景：適用于大規(guī)模數(shù)據(jù)排序，對穩(wěn)定性沒有嚴(yán)格要求的場景。
## 7. 堆排序（Heap Sort）
堆排序利用了二叉堆的數(shù)據(jù)結(jié)構(gòu)，其主要思想是將待排序的序列看成一棵完全二叉樹，對每個非葉子節(jié)點進(jìn)行堆化操作，得到一個大根堆或小根堆。然后依次將堆頂元素與末尾元素交換，并進(jìn)行堆化操作，直到所有元素被排好序。
- 優(yōu)點：效率較高，不需要額外的內(nèi)存空間。
- 缺點：不穩(wěn)定。
- 應(yīng)用場景：適用于大規(guī)模數(shù)據(jù)排序，對穩(wěn)定性沒有要求。
## 8. 計數(shù)排序（Counting Sort）
計數(shù)排序適用于元素取值范圍比較小的場景，其主要思想是通過統(tǒng)計每個元素出現(xiàn)的次數(shù)來確定元素在最終有序序列中的位置。計數(shù)排序的時間復(fù)雜度為O(n+k)，其中k為元素取值范圍。
- 優(yōu)點：效率高，穩(wěn)定。
- 缺點：需要額外的內(nèi)存空間，只能處理非負(fù)整數(shù)。
- 應(yīng)用場景：適用于元素取值范圍比較小的場景，如對年齡進(jìn)行排序等。
## 9. 桶排序（Bucket Sort）
桶排序是一種基于計數(shù)排序的改進(jìn)算法，適用于元素分布比較均勻的場景。其主要思想是將待排序的元素按照一定規(guī)則放入多個桶中，對每個桶中的元素進(jìn)行排序，最后依次將所有桶中的元素拼接成一個有序序列。桶排序的時間復(fù)雜度為O(n+k)，空間復(fù)雜度較高。
- 優(yōu)點：效率高，穩(wěn)定。
- 缺點：需要額外的內(nèi)存空間。
- 應(yīng)用場景：適用于元素分布比較均勻的場景。
## 10. 基數(shù)排序（Radix Sort）
基數(shù)排序是一種非比較排序算法，其主要思想是利用數(shù)字的位數(shù)進(jìn)行排序。對于待排序的元素，首先按照個位排序，然后按照十位排序，依次類推，直到排完最高位。基數(shù)排序的時間復(fù)雜度為O(d(n+k))，其中d為元素的最大位數(shù)，k為元素的取值范圍。
- 優(yōu)點：穩(wěn)定，適用于各種數(shù)據(jù)類型。
- 缺點：需要額外的內(nèi)存空間。
- 應(yīng)用場景：適用于元素位數(shù)相同的場景，如整數(shù)排序等。
總體來說，不同的排序算法有各自不同的特點和適用場景
## 代碼舉例
好的，以下是使用C語言編寫各種排序算法的完整示例代碼，每一行都有注釋說明。請注意，這些示例可能不包含錯誤處理和邊界檢查等必要的細(xì)節(jié)。
### 冒泡排序
```c
void bubble_sort(int arr[], int n) {
// 從第一個元素開始遍歷到倒數(shù)第二個元素
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;
}
}
}
}
```
### 選擇排序
```c
void selection_sort(int arr[], int n) {
// 從第一個元素開始遍歷到倒數(shù)第二個元素
for (int i = 0; i < n - 1; i++) {
// 假設(shè)當(dāng)前元素是未排序部分中最小的
int min_index = i;
// 遍歷未排序部分的所有元素，找到最小值的下標(biāo)
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
// 如果最小值不在已排序的位置，則將其放到已排序部分的末尾
if (min_index != i) {
int temp = arr[ i];
arr[ i] = arr[min_index];
arr[min_index] = temp;
}
}
}
```
### 插入排序
```c
void insertion_sort(int arr[], int n) {
// 從第二個元素開始遍歷
for (int i = 1; i < n; i++) {
int temp = arr[ i]; // 將當(dāng)前元素存儲在臨時變量中
int j = i - 1; // 已排序部分的最后一個元素的下標(biāo)
// 如果已排序部分中的一個元素大于當(dāng)前元素，則向右移動該元素
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
// 將當(dāng)前元素插入到正確的位置
arr[j + 1] = temp;
}
}
```
### 希爾排序
```c
void shell_sort(int arr[], int n) {
// 初始化間隔大小
for (int gap = n / 2; gap > 0; gap /= 2) {
// 對每個間隔進(jìn)行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[ i];
int j = i;
// 將未排序部分中的元素插入到已排序部分的正確位置
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
```
### 歸并排序
```c
// 合并兩個有序子數(shù)組
void merge(int arr[], int left, int mid, int right) {
int len1 = mid - left + 1; // 左子數(shù)組的長度
int len2 = right - mid; // 右子數(shù)組的長度
int L[len1], R[len2]; // 創(chuàng)建兩個臨時數(shù)組
// 將左子數(shù)組復(fù)制到 L 數(shù)組中
for (int i = 0; i < len1; i++) {
L[ i] = arr[left + i];
}
// 將右子數(shù)組復(fù)制到 R 數(shù)組中
for (int j = 0; j < len2; j++) {
R[j] = arr[mid + 1 + j];
}
int i = 0, j = 0, k = left; // i、j 和 k 分別是 L、R和 arr 數(shù)組中元素的下標(biāo)
// 比較 L 和 R 數(shù)組中的元素，將較小的一個放到 arr 數(shù)組中
while (i < len1 && j < len2) {
if (L[ i] <= R[j]) {
arr[k] = L[ i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 將剩余的元素放到 arr 數(shù)組中
while (i < len1) {
arr[k] = L[ i];
i++;
k++;
}
while (j < len2) {
arr[k] = R[j];
j++;
k++;
}
}
// 歸并排序
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // 找到數(shù)組的中間位置
merge_sort(arr, left, mid); // 對左子數(shù)組進(jìn)行歸并排序
merge_sort(arr, mid + 1, right); // 對右子數(shù)組進(jìn)行歸并排序
merge(arr, left, mid, right); // 合并兩個有序子數(shù)組
}
}
```
### 快速排序
```c
// 將數(shù)組劃分為兩部分，并返回樞軸的下標(biāo)
int partition(int arr[], int low, int high) {
int pivot = arr[low]; // 選擇第一個元素作為樞軸
while (low < high) {
// 從后向前遍歷，找到第一個小于等于樞軸的元素
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high];
// 從前向后遍歷，找到第一個大于樞軸的元素
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot; // 將樞軸放到正確位置上
return low;
}
// 快速排序
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pivot_index = partition(arr, low, high); // 劃分?jǐn)?shù)組為兩部分
quick_sort(arr, low, pivot_index - 1); // 對左子數(shù)組進(jìn)行快速排序
quick_sort(arr, pivot_index + 1, high); // 對右子數(shù)組進(jìn)行快速排序
}
}
```
這些排序算法都是經(jīng)典的基于比較的排序算法，它們的時間復(fù)雜度最好情況下都是 O(n log n)，最壞情況下為 O(n2)。在實際應(yīng)用中，可以根據(jù)具體情況選擇不同的排序算法來優(yōu)化程序性能。
|
評分
-
查看全部評分
|
