数据结构排序C语言代码如何实现？-C语言-盈思创科技

对于每种算法,我都会提供：

（图片来源网络，侵删）

算法思想简介
C 语言完整代码
代码解析
时间/空间复杂度分析

您可以直接将这些代码复制到您的 C 语言编译器（如 GCC, Clang, Visual Studio）中进行编译和运行。

准备工作：一个通用的测试框架

为了方便地测试和比较所有排序算法,我们首先创建一个通用的框架，包括打印数组和交换两个元素的函数。

#include <stdio.h>
#include <stdlib.h> // 用于 rand() 和 srand()
#include <time.h>   // 用于 time()
// 交换两个整数的值
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

冒泡排序

算法思想

重复地遍历要排序的数列,一次比较两个元素，如果它们的顺序错误就把它们交换过来，遍历数列的工作是重复地进行，直到没有再需要交换的元素为止，这意味着该数列已经排序完成，就像水中的气泡一样，大的元素会慢慢“浮”到数列的顶端。

C 语言代码

// 冒泡排序
void bubbleSort(int arr[], int n) {
    int i, j;
    // 外层循环控制排序轮数
    for (i = 0; i < n - 1; i++) {
        // 内层循环进行相邻元素比较和交换
        // 每一轮结束后，最大的元素会冒到末尾，所以内层循环可以减少 i 次
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }
}

代码解析

外层循环 for (i = 0; i < n - 1; i++)：总共需要进行 n-1 轮比较。
内层循环 for (j = 0; j < n - i - 1; j++)：在每一轮中，从数组的第一个元素开始，比较相邻的两个元素。arr[j] 大于 arr[j+1]，就交换它们。
n - i - 1：因为每完成一轮外层循环，数组末尾的 i 个元素就已经是最大的了，无需再比较。

复杂度分析

时间复杂度：
- 最好情况：O(n)，当数组已经有序时，只需一轮遍历即可确定。
- 最坏情况：O(n²)，当数组是逆序时，每次比较都需要交换。
- 平均情况：O(n²)。
空间复杂度：O(1)，是原地排序，只需要一个临时变量用于交换。

选择排序

算法思想

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。

（图片来源网络，侵删）

C 语言代码

// 选择排序
void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    // 一共需要 n-1 轮选择
    for (i = 0; i < n - 1; i++) {
        // 在未排序部分中找到最小元素的索引
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 将找到的最小元素与未排序部分的第一个元素交换
        if (min_idx != i) {
            swap(&arr[min_idx], &arr[i]);
        }
    }
}

代码解析

外层循环 for (i = 0; i < n - 1; i++)：遍历数组，i 代表当前已排序序列的末尾下一个位置。
内层循环 for (j = i + 1; j < n; j++)：从 i+1 的位置开始，在剩余的未排序部分寻找最小值的索引 min_idx。
找到最小值后,如果它不在 i 的位置，就将其与 i 位置的元素交换。

复杂度分析

时间复杂度：无论最好、最坏还是平均情况，都是 O(n²)，因为它总是需要进行 n(n-1)/2 次比较。
空间复杂度：O(1)，是原地排序。

插入排序

算法思想

通过构建有序序列,对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1) 的额外空间的排序）。

C 语言代码

// 插入排序
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;
    }
}

代码解析

外层循环 for (i = 1; i < n; i++)：将数组分为“已排序”和“未排序”两部分。i 指向未排序部分的第一个元素。
key = arr[i]：取出当前要插入的元素。
内层 while 循环：从 j = i - 1 开始，从后向前扫描已排序部分。arr[j] 大于 key，就将 arr[j] 向后移动一位，直到找到 key 应该插入的位置。
arr[j + 1] = key：将 key 插入到找到的位置。

复杂度分析

时间复杂度：
- 最好情况：O(n)，当数组已经有序时，内层 while 循环不执行。
- 最坏情况：O(n²)，当数组是逆序时，每次都需要移动所有已排序元素。
- 平均情况：O(n²)。
空间复杂度：O(1)，是原地排序。

快速排序

算法思想

采用分治法策略,选择一个基准元素，将数组分为两部分，左边部分的所有元素都小于基准，右边部分的所有元素都大于基准，然后递归地对这两个子数组进行快速排序。

C 语言代码

// 快速排序的分区函数
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1);     // i 是小于基准的区域的边界
    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 quickSortRecursive(int arr[], int low, int high) {
    if (low < high) {
        // pi 是分区后基准的索引
        int pi = partition(arr, low, high);
        // 递归地对基准左右两边的子数组进行排序
        quickSortRecursive(arr, low, pi - 1);
        quickSortRecursive(arr, pi + 1, high);
    }
}
// 快速排序的包装函数，方便调用
void quickSort(int arr[], int n) {
    quickSortRecursive(arr, 0, n - 1);
}

代码解析

partition 函数是核心，它选择最后一个元素 arr[high] 作为基准 pivot。
使用一个指针 i 来跟踪所有小于 pivot 的元素的边界，初始时 i = low - 1。
遍历从 low 到 high-1 的元素 arr[j]。arr[j] 小于 pivot，就将 i 向右移动一位，并交换 arr[i] 和 arr[j]，这保证了 i 左边的所有元素都小于 pivot。
遍历结束后,将基准 pivot（arr[high]）与 arr[i+1] 交换，这样基准就位于它最终应该在的位置，并且它左边的元素都小于它，右边的都大于它。
quickSortRecursive 函数处理递归，如果子数组长度大于1，就进行分区，然后递归地对左右两个子数组进行排序。

复杂度分析

时间复杂度：
- 最好情况：O(n log n)，每次分区都能将数组均匀地分成两半。
- 最坏情况：O(n²)，当数组已经有序或逆序，并且每次都选择到最大或最小的元素作为基准时。
- 平均情况：O(n log n)。
空间复杂度：O(log n)，主要是递归调用栈的深度。

归并排序

算法思想

也采用分治法策略,首先将数组分成两半，分别对这两半进行递归地归并排序，然后将两个已排序的子数组合并成一个有序的数组。

C 语言代码

// 合并两个已排序的子数组
// arr[] 是要合并的数组
// left 是第一个子数组的起始索引
// mid 是第一个子数组的结束索引
// right 是第二个子数组的结束索引
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];
    // 将数据复制到临时数组 L[] 和 R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    // 合并临时数组回 arr[left..right]
    i = 0; // L[] 的初始索引
    j = 0; // R[] 的初始索引
    k = left; // 合并后数组的初始索引
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    // 复制 L[] 中剩余的元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    // 复制 R[] 中剩余的元素
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
// 归并排序的递归函数
void mergeSortRecursive(int arr[], int left, int right) {
    if (left < right) {
        // 找到中间点
        int mid = left + (right - left) / 2;
        // 递归地对左右两半进行排序
        mergeSortRecursive(arr, left, mid);
        mergeSortRecursive(arr, mid + 1, right);
        // 合并已排序的两半
        merge(arr, left, mid, right);
    }
}
// 归并排序的包装函数
void mergeSort(int arr[], int n) {
    mergeSortRecursive(arr, 0, n - 1);
}

代码解析

mergeSortRecursive 函数是递归的核心，它找到数组的中间点 mid，然后递归地对左半部分 arr[left...mid] 和右半部分 arr[mid+1...right] 进行排序。
当子数组长度为1时（left == right），递归停止，因为单个元素可以看作是已排序的。
merge 函数负责将两个已排序的子数组合并，它创建两个临时数组 L 和 R 来存储这两个子数组，然后通过比较 L 和 R 中的元素，按顺序将它们放回原始数组 arr 中。

复杂度分析

时间复杂度：无论最好、最坏还是平均情况，都是 O(n log n)，因为它总是将数组对半分，合并操作是线性的。
空间复杂度：O(n)，需要额外的临时数组来存储子数组。

完整测试与主函数

下面是一个完整的主函数,用于生成随机数组并测试上述所有排序算法。

（图片来源网络，侵删）

int main() {
    int n = 10;
    int arr_bubble[n], arr_selection[n], arr_insertion[n], arr_quick[n], arr_merge[n];
    // 生成随机数组并复制到各个数组中
    srand(time(NULL)); // 设置随机种子
    for (int i = 0; i < n; i++) {
        int rand_val = rand() % 100; // 生成 0-99 的随机数
        arr_bubble[i] = rand_val;
        arr_selection[i] = rand_val;
        arr_insertion[i] = rand_val;
        arr_quick[i] = rand_val;
        arr_merge[i] = rand_val;
    }
    printf("原始数组:\n");
    printArray(arr_bubble, n);
    printf("\n");
    // --- 测试冒泡排序 ---
    bubbleSort(arr_bubble, n);
    printf("冒泡排序后:\n");
    printArray(arr_bubble, n);
    printf("\n");
    // --- 测试选择排序 ---
    selectionSort(arr_selection, n);
    printf("选择排序后:\n");
    printArray(arr_selection, n);
    printf("\n");
    // --- 测试插入排序 ---
    insertionSort(arr_insertion, n);
    printf("插入排序后:\n");
    printArray(arr_insertion, n);
    printf("\n");
    // --- 测试快速排序 ---
    quickSort(arr_quick, n);
    printf("快速排序后:\n");
    printArray(arr_quick, n);
    printf("\n");
    // --- 测试归并排序 ---
    mergeSort(arr_merge, n);
    printf("归并排序后:\n");
    printArray(arr_merge, n);
    printf("\n");
    return 0;
}

总结与对比

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性	特点
冒泡排序	O(n²)	O(n²)	O(n)	O(1)	稳定	简单，但效率低，适合小规模数据
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定	交换次数少，但比较次数多
插入排序	O(n²)	O(n²)	O(n)	O(1)	稳定	对于小规模或接近有序的数据效率很高
快速排序	O(n log n)	O(n²)	O(n log n)	O(log n)	不稳定	平均效率最高，应用最广泛
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定	效率稳定，但需要额外空间

如何选择？

简单实现/小数据量：冒泡、选择、插入排序都很简单。
通用高效排序：快速排序 通常是首选，因为它的平均性能最好。
数据量大且需要稳定排序：归并排序 是一个很好的选择，尽管它需要额外空间。
数据接近有序：插入排序 会表现出色。

数据结构排序C语言代码如何实现？

准备工作：一个通用的测试框架

冒泡排序

算法思想

C 语言代码

代码解析

复杂度分析

选择排序

算法思想

C 语言代码

代码解析

复杂度分析

插入排序

算法思想

C 语言代码

代码解析

复杂度分析

快速排序

算法思想

C 语言代码

代码解析

复杂度分析

归并排序

算法思想

C 语言代码

代码解析

复杂度分析

完整测试与主函数

总结与对比

相关文章

目录[+]