標題: C語言常用排序算法介紹 [打印本頁]
作者: rong666    時間: 2023-3-27 22:38
標題: C語言常用排序算法介紹
以下是C語言中常用的十種排序算法：

1. 冒泡排序（Bubble Sort）

冒泡排序的核心思想是反復交換相鄰的未按順序排列的元素，通過多次遍歷數(shù)組，每次將一個未排好序的元素放到合適的位置，最終得到有序數(shù)組。時間復雜度為O(n^2)，不適用于大規(guī)模數(shù)據(jù)。

- 優(yōu)點：簡單易懂，實現(xiàn)容易。
- 缺點：效率較低，對大規(guī)模數(shù)據(jù)排序耗時長，不適合生產(chǎn)環(huán)境使用。
- 應(yīng)用場景：適用于小規(guī)模數(shù)據(jù)排序以及教學示例等場景。

## 2. 選擇排序（Selection Sort）

選擇排序的主要思想是在未排序的序列中選擇最小（或最大）的元素放到已排序序列的末尾。與冒泡排序不同的是，選擇排序每次只會進行一次交換操作，因此其時間復雜度仍然為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)，其時間復雜度為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ù)進行排序。

## 4. 希爾排序（Shell Sort）

希爾排序是插入排序的改進版，其主要思想是將待排序的序列按照一個增量序列（通常是n/2，n/4，...，1）分成若干個子序列，對每個子序列進行插入排序。然后縮小增量，再進行插入排序。最終當增量為1時，整個序列就被排好序了。由于希爾排序多次分組排序，因此其時間復雜度介于O(n)和O(n^2)之間。

- 優(yōu)點：相較于插入排序，希爾排序的效率更高。
- 缺點：時間復雜度上界難以精確，而且受增量序列的影響較大。
- 應(yīng)用場景：適用于中等規(guī)模數(shù)據(jù)排序，比插入排序更加高效。

## 5. 歸并排序（Merge Sort）

歸并排序是一種比較高效的排序算法，其主要思想是將待排序的序列分成左右兩部分，對每部分進行遞歸排序，最后將兩個有序的子序列合并成一個有序的序列。歸并排序的時間復雜度為O(nlogn)，但其需要開辟額外的空間用于存放臨時序列，因此其空間復雜度較高。

- 優(yōu)點：時間復雜度穩(wěn)定，具有很好的可擴展性。
- 缺點：需要額外的內(nèi)存空間。
- 應(yīng)用場景：適用于大規(guī)模數(shù)據(jù)排序，對穩(wěn)定性和可擴展性要求較高的場景。

## 6. 快速排序（Quick Sort）

快速排序也是一種高效的排序算法，其主要思想是選擇一個基準元素，將待排序的序列分成兩部分，一部分所有元素都小于等于基準元素，另一部分所有元素都大于等于基準元素。然后對這兩部分分別遞歸調(diào)用快速排序函數(shù)�？焖倥判虻臅r間復雜度為O(nlogn)，但其在最壞情況下性能會退化為O(n^2)。

- 優(yōu)點：效率較高，在大規(guī)模數(shù)據(jù)下表現(xiàn)良好。
- 缺點：不穩(wěn)定，存在最壞時間復雜度O(n^2)的情況。
- 應(yīng)用場景：適用于大規(guī)模數(shù)據(jù)排序，對穩(wěn)定性沒有嚴格要求的場景。

## 7. 堆排序（Heap Sort）

堆排序利用了二叉堆的數(shù)據(jù)結(jié)構(gòu)，其主要思想是將待排序的序列看成一棵完全二叉樹，對每個非葉子節(jié)點進行堆化操作，得到一個大根堆或小根堆。然后依次將堆頂元素與末尾元素交換，并進行堆化操作，直到所有元素被排好序。

- 優(yōu)點：效率較高，不需要額外的內(nèi)存空間。
- 缺點：不穩(wěn)定。
- 應(yīng)用場景：適用于大規(guī)模數(shù)據(jù)排序，對穩(wěn)定性沒有要求。

## 8. 計數(shù)排序（Counting Sort）

計數(shù)排序適用于元素取值范圍比較小的場景，其主要思想是通過統(tǒng)計每個元素出現(xiàn)的次數(shù)來確定元素在最終有序序列中的位置。計數(shù)排序的時間復雜度為O(n+k)，其中k為元素取值范圍。

- 優(yōu)點：效率高，穩(wěn)定。
- 缺點：需要額外的內(nèi)存空間，只能處理非負整數(shù)。
- 應(yīng)用場景：適用于元素取值范圍比較小的場景，如對年齡進行排序等。

## 9. 桶排序（Bucket Sort）

桶排序是一種基于計數(shù)排序的改進算法，適用于元素分布比較均勻的場景。其主要思想是將待排序的元素按照一定規(guī)則放入多個桶中，對每個桶中的元素進行排序，最后依次將所有桶中的元素拼接成一個有序序列。桶排序的時間復雜度為O(n+k)，空間復雜度較高。

- 優(yōu)點：效率高，穩(wěn)定。
- 缺點：需要額外的內(nèi)存空間。
- 應(yīng)用場景：適用于元素分布比較均勻的場景。

## 10. 基數(shù)排序（Radix Sort）

基數(shù)排序是一種非比較排序算法，其主要思想是利用數(shù)字的位數(shù)進行排序。對于待排序的元素，首先按照個位排序，然后按照十位排序，依次類推，直到排完最高位�；鶖�(shù)排序的時間復雜度為O(d(n+k))，其中d為元素的最大位數(shù)，k為元素的取值范圍。

- 優(yōu)點：穩(wěn)定，適用于各種數(shù)據(jù)類型。
- 缺點：需要額外的內(nèi)存空間。
- 應(yīng)用場景：適用于元素位數(shù)相同的場景，如整數(shù)排序等。

總體來說，不同的排序算法有各自不同的特點和適用場景


## 代碼舉例

好的，以下是使用C語言編寫各種排序算法的完整示例代碼，每一行都有注釋說明。請注意，這些示例可能不包含錯誤處理和邊界檢查等必要的細節(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è)當前元素是未排序部分中最小的
        int min_index = i;
        // 遍歷未排序部分的所有元素，找到最小值的下標
        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]; // 將當前元素存儲在臨時變量中
        int j = i - 1; // 已排序部分的最后一個元素的下標
        // 如果已排序部分中的一個元素大于當前元素，則向右移動該元素
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 將當前元素插入到正確的位置
        arr[j + 1] = temp;
    }
}
```

### 希爾排序

```c
void shell_sort(int arr[], int n) {
    // 初始化間隔大小
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 對每個間隔進行插入排序
        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ù)組復制到 L 數(shù)組中
    for (int i = 0; i < len1; i++) {
        L[ i] = arr[left + i];
    }
    // 將右子數(shù)組復制到 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ù)組中元素的下標
    // 比較 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ù)組進行歸并排序
        merge_sort(arr, mid + 1, right); // 對右子數(shù)組進行歸并排序
        merge(arr, left, mid, right); // 合并兩個有序子數(shù)組
    }
}
```

### 快速排序

```c
// 將數(shù)組劃分為兩部分，并返回樞軸的下標
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); // 劃分數(shù)組為兩部分
        quick_sort(arr, low, pivot_index - 1); // 對左子數(shù)組進行快速排序
        quick_sort(arr, pivot_index + 1, high); // 對右子數(shù)組進行快速排序
    }
}
```

這些排序算法都是經(jīng)典的基于比較的排序算法，它們的時間復雜度最好情況下都是 O(n log n)，最壞情況下為 O(n2)。在實際應(yīng)用中，可以根據(jù)具體情況選擇不同的排序算法來優(yōu)化程序性能。

作者: liixaofei5    時間: 2023-7-24 23:41
感謝總結(jié)，收藏以備日后使用



歡迎光臨 (http://www.torrancerestoration.com/bbs/) Powered by Discuz! X3.1