【C语言】解析C语言实现排序的算法（冒泡排序、插入排序、选择排序、快速排序、归并排序）

妖狐艹你老母 2024-03-22 19:50 72阅读 0赞

> 本博客主要围绕五种常见的排序算法展开讨论，包括选择排序、快速排序、归并排序、冒泡排序和插入排序。针对每种算法，我对其思想、特点、时间复杂度、稳定性以及优缺点进行了详细解释和比较。

#### 文章目录 ####

*  1.冒泡排序
 *   *  1.1 算法思想:
     *  1.2 代码实现:
     *  1.3 解析代码:
     *  1.4 示例输出:
     *  1.5总结:
 *  2. 插入排序
 *   *  2.1 算法思想：
     *  2.2 代码实现：
     *  2.3 解析代码：
     *  2.4 示例输出：
     *  2.5 总结：
 *  3. 选择排序
 *   *  3.1 算法思想：
     *  3.2 代码实现：
     *  3.3 解析代码：
     *  3.4 示例输出：
     *  3.5 总结：
 *  4 快速排序
 *   *  4.1 算法思想：
     *  4.2 代码实现：
     *  4.3 解析代码：
     *  4.4 示例输出：
     *  4.5 总结：
 *  5 归并排序
 *   *  5.1 算法思想：
     *  5.2 代码实现：
     *  5.3 解析代码：
     *  5.4 示例输出：
     *  5.5 总结：
 *  归纳比较

## 1.冒泡排序 ##

冒泡排序算法是一种简单且常用的排序算法。它通过重复地交换相邻的元素，将较大的元素逐渐"浮"到数列的末尾。

### 1.1 算法思想: ###

冒泡排序的核心思想是在每一轮遍历中，比较相邻的两个元素，如果顺序有误则进行交换。通过多轮的遍历，将最大（或最小）的元素逐渐“冒泡”到数组的最后（或最前），从而实现排序。

### 1.2 代码实现: ###

#include <stdio.h>
    
    // 冒泡排序函数
    void bubbleSort(int arr[], int n) {
        
        int i, j;
        for (i = 0; i < n - 1; i++) {
        
            // 每一轮遍历
            for (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;
                }
            }
        }
    }
    
    int main() {
        
        int arr[] = {
        64, 34, 25, 12, 22, 11, 90};
        int n = sizeof(arr) / sizeof(arr[0]);
    
        bubbleSort(arr, n);
    
        printf("排序后的数组：\n");
        for (int i = 0; i < n; i++) {
        
            printf("%d ", arr[i]);
        }
        return 0;
    }

### 1.3 解析代码: ###

1.  首先，我们在头文件中引入了<stdio.h>，以便使用`printf`函数。
2.  接着，在`bubbleSort`函数中，使用两个嵌套的循环进行遍历。外部循环`i`控制遍历的轮数，内部循环`j`用于比较相邻元素并进行交换。
3.  内部循环中，我们通过`arr[j]`和`arr[j + 1]`的比较来判断是否需要交换元素。
4.  如果`arr[j]`大于`arr[j + 1]`，则交换两个元素的值。通过使用一个临时变量`temp`，我们可以完成交换操作。
5.  在`main`函数中，我们定义一个待排序的整数数组`arr`，并计算数组的长度`n`。
6.  使用`bubbleSort`函数对数组进行排序。
7.  最后，我们通过`printf`函数输出排序后的数组。

### 1.4 示例输出: ###

排序后的数组：
    11 12 22 25 34 64 90

### 1.5总结: ###

冒泡排序是一种简单但效率较低的排序算法，在处理小型数据集时比较适用。通过重复交换相邻元素实现排序，冒泡排序的时间复杂度为O(n^2)。

## 2. 插入排序 ##

插入排序是一种简单且直观的排序算法，它通过构建有序序列来逐步插入元素，最终完成整个数组的排序。下面是插入排序的解析、代码和解释：

### 2.1 算法思想： ###

插入排序的核心思想是，将数组分为已排序和未排序两部分。初始时，将第一个元素视为已排序部分，然后逐个遍历未排序部分的元素，将每个元素插入到已排序部分的正确位置。插入过程中，需要不断地向前比较已排序部分的元素，找到插入位置以保持已排序部分的有序性。

### 2.2 代码实现： ###

#include <stdio.h>
    
    void insertionSort(int arr[], int n) {
        
        int i, j, key;
        for (i = 1; i < n; i++) {
        
            key = arr[i];
            j = i - 1;
    
            // 将arr[0...i-1]中大于key的元素向后移动
            while (j >= 0 && arr[j] > key) {
        
                arr[j + 1] = arr[j];
                j = j - 1;
            }
    
            arr[j + 1] = key;
        }
    }
    
    int main() {
        
        int arr[] = {
        12, 11, 13, 5, 6};
        int n = sizeof(arr) / sizeof(arr[0]);
    
        insertionSort(arr, n);
    
        printf("排序后的数组：\n");
        for (int i = 0; i < n; i++) {
        
            printf("%d ", arr[i]);
        }
        return 0;
    }

### 2.3 解析代码： ###

1.  在插入排序的`insertionSort`函数中，我们使用一个循环从第二个元素开始遍历整个数组。
2.  对于每个元素，我们将其赋值给`key`变量，并且使用一个变量`j`来追踪插入位置。
3.  然后，在内部循环中，我们将已排序部分大于`key`的元素向后移动一位，为插入`key`创造空间。
4.  这里使用了一个自减的`while`循环来将元素向后移动，直到找到插入位置。
5.  最后，将`key`插入到`arr[j+1]`的位置，保证已排序部分仍然有序。
6.  在`main`函数中，我们定义了一个待排序的整数数组`arr`，并计算数组的长度`n`。
7.  使用`insertionSort`函数对数组进行排序。
8.  最后，通过`printf`函数输出排序后的数组。

### 2.4 示例输出： ###

排序后的数组：
    5 6 11 12 13

### 2.5 总结： ###

插入排序是一种简单但有效的排序算法，适用于小规模数组或部分有序的情况。它的时间复杂度为O(n^2)，可以稳定地将数组排序。

## 3. 选择排序 ##

选择排序是一种简单直观的排序算法，它每次在未排序的部分中选择最小（或最大）的元素，并将其放置在已排序部分的末尾。下面是选择排序的解析、代码和解释：

### 3.1 算法思想： ###

选择排序的核心思想是将数组分为已排序和未排序两部分。初始状态下，整个数组都是未排序的。每一次循环中，从未排序部分中选择最小（或最大）的元素，然后将其放置到已排序部分的末尾，直到所有元素都被放置到正确的位置上。

### 3.2 代码实现： ###

#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[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
    
    int main() {
        
        int arr[] = {
        64, 25, 12, 22, 11};
        int n = sizeof(arr) / sizeof(arr[0]);
    
        selectionSort(arr, n);
    
        printf("排序后的数组：\n");
        for (int i = 0; i < n; i++) {
        
            printf("%d ", arr[i]);
        }
        return 0;
    }

### 3.3 解析代码： ###

1.  在选择排序的`selectionSort`函数中，通过两层循环实现排序。
2.  外层循环从数组的第一个元素开始，到倒数第二个元素结束。表示已排序部分的范围。
3.  内层循环从外层循环的下一个元素开始，到最后一个元素结束。用于在未排序的部分中找到最小元素的索引。
4.  在内层循环中，通过比较找到未排序部分的最小元素的索引，并将其赋值给`minIndex`。
5.  然后，在外层循环中，将最小元素与未排序部分的第一个元素进行交换。
6.  通过使用一个临时变量`temp`来实现元素交换的过程。
7.  循环继续，直到已排序部分包含所有元素。
8.  在`main`函数中，定义待排序的整数数组`arr`，并计算数组的长度`n`。
9.  使用`selectionSort`函数对数组进行排序。
10. 最后，通过`printf`函数输出排序后的数组。

### 3.4 示例输出： ###

排序后的数组：
    11 12 22 25 64

### 3.5 总结： ###

选择排序是一种简单但效率较低的排序算法，适用于数据量较小的情况。它的时间复杂度为O(n^2)，可以稳定地将数组排序。

## 4 快速排序 ##

快速排序是一种基于分治思想的高效排序算法，通过选择一个基准元素，将数组分成左右两部分，并递归地对这两部分进行排序，最终完成整个数组的排序。下面是快速排序的解析、代码和解释：

### 4.1 算法思想： ###

快速排序的核心思想是选取一个基准元素，将数组分为两个子数组，左边的子数组中的元素都小于等于基准元素，右边的子数组中的元素都大于等于基准元素。然后，对左右两个子数组分别递归地进行快速排序，直到子数组的长度为1或0，即可完成排序。

### 4.2 代码实现： ###

#include <stdio.h>
    
    void swap(int *a, int *b) {
        
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    
    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++;
                swap(&arr[i], &arr[j]);
            }
        }
        // 将基准元素放置到正确的位置
        swap(&arr[i + 1], &arr[high]);
        return (i + 1);
    }
    
    void quickSort(int arr[], int low, int high) {
        
        if (low < high) {
        
            // 划分数组并获取基准元素的位置
            int pivotIndex = partition(arr, low, high);
    
            // 分别对左右两个子数组进行快速排序
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    
    int main() {
        
        int arr[] = {
        10, 7, 8, 9, 1, 5};
        int n = sizeof(arr) / sizeof(arr[0]);
    
        quickSort(arr, 0, n - 1);
    
        printf("排序后的数组：\n");
        for (int i = 0; i < n; i++) {
        
            printf("%d ", arr[i]);
        }
        return 0;
    }

### 4.3 解析代码： ###

1.  借助`swap`函数实现元素交换操作。
2.  在`partition`函数中，选择数组的最后一个元素作为基准`pivot`。
3.  使用变量`i`来追踪小于等于基准的元素位置。
4.  使用循环逐个遍历当前数组，并将小于等于基准的元素交换到左边子数组。
5.  最后，将基准元素放置到正确的位置上，并返回其位置作为划分点。
6.  在`quickSort`函数中，通过递归调用快速排序来分别对左右两个子数组进行排序。
7.  递归基准为子数组长度为1或0的情况，这时子数组已经是有序的。
8.  在`main`函数中，定义待排序的整数数组`arr`，并计算数组的长度`n`。
9.  使用`quickSort`函数对数组进行排序。
10. 最后，通过`printf`函数输出排序后的数组。

### 4.4 示例输出： ###

排序后的数组：
    1 5 7 8 9 10

### 4.5 总结： ###

快速排序是一种高效且常用的排序算法，它的平均时间复杂度为O(nlogn)，在大多数情况下可以快速地将数组排序。

## 5 归并排序 ##

归并排序是一种基于分治思想的排序算法，它将数组递归地分为两个子数组，然后将这两个子数组排序，并将它们合并成一个有序数组。下面是归并排序的解析、代码和解释：

### 5.1 算法思想： ###

归并排序的核心思想是将数组递归地分成两个子数组，直到每个子数组只包含一个元素。然后，通过将两个有序的子数组合并，再逐层返回最终有序的数组。

### 5.2 代码实现： ###

#include <stdio.h>
    
    void merge(int arr[], int left, int mid, int right) {
        
        int i, j, k;
        int n1 = mid - left + 1;   // 左子数组长度
        int n2 = right - mid;      // 右子数组长度
    
        // 创建临时数组用于存储左右子数组
        int L[n1], R[n2];
    
        // 将数据复制到临时数组
        for (i = 0; i < n1; i++)
            L[i] = arr[left + i];
        for (j = 0; j < n2; j++)
            R[j] = arr[mid + 1 + j];
    
        // 将临时数组中的元素按照顺序合并到原数组中
        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++;
        }
    }
    
    void mergeSort(int arr[], int left, int right) {
        
        if (left < right) {
        
            int mid = left + (right - left) / 2;
    
            // 递归地对左右两个子数组进行归并排序
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
    
            // 合并排序后的子数组
            merge(arr, left, mid, right);
        }
    }
    
    int main() {
        
        int arr[] = {
        12, 11, 13, 5, 6, 7};
        int n = sizeof(arr) / sizeof(arr[0]);
    
        mergeSort(arr, 0, n - 1);
    
        printf("排序后的数组：\n");
        for (int i = 0; i < n; i++) {
        
            printf("%d ", arr[i]);
        }
        return 0;
    }

### 5.3 解析代码： ###

1.  定义了一个`merge`函数，用于将两个有序的子数组合并到原始数组中。
2.  在`merge`函数中，使用两个临时数组`L`和`R`来分别存储左子数组和右子数组的元素。
3.  将左子数组和右子数组的元素按照顺序合并到原数组中。
4.  在`mergeSort`函数中，判断左下标`left`是否小于右下标`right`，如果满足条件，则进行以下操作：
5.  计算中间下标`mid`，将数组划分成两个子数组。
6.  分别递归地对左子数组和右子数组进行归并排序。
7.  最后，调用`merge`函数将排序后的子数组合并。
8.  在`main`函数中，定义待排序的整数数组`arr`，并计算数组的长度`n`。
9.  使用`mergeSort`函数对数组进行排序。
10. 最后，通过`printf`函数输出排序后的数组。

### 5.4 示例输出： ###

排序后的数组：
    5 6 7 11 12 13

### 5.5 总结： ###

归并排序是一种高效且稳定的排序算法，它的时间复杂度为O(nlogn)，适用于各种规模的数组。归并排序通过分治的思想，将排序问题划分为小问题，并最终合并结果。

## 归纳比较 ##

下面是对选择排序、快速排序、归并排序、冒泡排序和插入排序进行归纳和比较，包括它们各自的优点和缺点：

<table> 
 <thead> 
  <tr> 
   <th>算法</th> 
   <th>优点</th> 
   <th>缺点</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>冒泡排序</td> 
   <td>简单，容易实现稳定，相同元素的相对顺序不会改变。</td> 
   <td>时间复杂度较高，为O(n^2)，效率较低。不适用于大规模数据排序。</td> 
  </tr> 
  <tr> 
   <td>插入排序</td> 
   <td>对小规模或部分有序的数组具有较好的性能。原地排序，不需要额外的空间。</td> 
   <td>平均时间复杂度为O(n^2)，效率较低。对于大规模数据排序，性能较差。</td> 
  </tr> 
  <tr> 
   <td>选择排序</td> 
   <td>简单、容易实现，对于小数据集，排序性能还可以接受。</td> 
   <td>时间复杂度较高，为O(n^2)，效率较低。不稳定，相同元素可能发生位置交换。</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>平均情况下具有较好的时间复杂度，为O(nlogn)。原地排序，不需要额外的空间。在大多数情况下表现良好，是最常用的排序算法之一。</td> 
   <td>最坏情况下的时间复杂度为O(n^2)。不稳定，相同元素可能发生位置交换。</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>始终具有O(nlogn)的时间复杂度，稳定且高效。技术复杂度低，易于理解和实现。稳定，相同元素的相对顺序不会改变。</td> 
   <td>需要额外的空间来存储临时数组，非原地排序。</td> 
  </tr> 
 </tbody> 
</table>

总结：

*  选择排序和冒泡排序简单易实现，但时间复杂度较高，适用于小规模数据。
 *  快速排序和归并排序具有较好的平均时间复杂度，适用于各种规模的数据。
 *  归并排序是稳定的，快速排序和选择排序是不稳定的。
 *  插入排序对小规模或部分有序的数据具有较好的性能。
 *  冒泡排序和插入排序都是原地排序算法，不需要额外的空间。