[C高手编程] C语言数据结构：排序算法与查找算法

🕗 发布于 2024-10-10 14:46 算法 c语言 数据结构 开发语言 排序算法

在这里插入图片描述

💖💖⚡️⚡️专栏：C高手编程-面试宝典/技术手册/高手进阶⚡️⚡️💖💖
「C高手编程」专栏融合了作者十多年的C语言开发经验，汇集了从基础到进阶的关键知识点，是不可多得的知识宝典。如果你是即将毕业的学生，面临C语言的求职面试，本专栏将帮助你扎实地掌握核心概念，轻松应对笔试与面试；如果你已有两三年的工作经验，专栏中的内容将补充你在实践中可能忽略的新技术和技巧；而对于资深的C语言程序员，这里也将是一本实用的技术备查手册，提供全面的知识回顾与更新。无论处在哪个阶段，「C高手编程」都能助你一臂之力，成为C语言领域的行家里手。

概述

本章深入探讨了C语言中的两种核心算法：排序算法和查找算法。我们将从基本概念入手，逐步深入到复杂算法的实践，包括各种排序算法（如冒泡排序、选择排序、插入排序、快速排序、归并排序等）和查找算法（如顺序查找、二分查找、哈希查找等）。通过本章的学习，读者将能够理解这些算法的工作原理，并能在实际编程中正确地运用它们。

1. 排序算法

1.1 排序算法概述

定义：排序算法是一种用于将一组数据按照特定顺序排列的方法。
详细说明：排序算法在计算机科学中有着广泛的应用，如数据库查询、文件系统索引、搜索引擎等。排序算法的选择取决于数据集的大小、数据类型以及对稳定性的要求等因素。

1.2 冒泡排序

1.2.1 冒泡排序定义

定义：冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把它们交换过来。
详细说明：冒泡排序的时间复杂度为O(n^2)，在最坏的情况下性能较差，但在小数据量的情况下易于理解和实现。

1.2.2 冒泡排序实现

void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 优化：设置一个标志位，如果没有发生交换，则提前退出循环
        int swapped = 0;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                swapped = 1;
            }
        }
        if (swapped == 0)
            break;
    }
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

1.3 选择排序

1.3.1 选择排序定义

定义：选择排序是一种简单的排序算法，它首先找到数组中最小（或最大）元素放到排序序列的起始位置，然后从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
详细说明：选择排序的时间复杂度也为O(n^2)，但通常比冒泡排序更快，因为它减少了不必要的交换次数。

1.3.2 选择排序实现

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_index = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        swap(&arr[min_index], &arr[i]);
    }
}

1.4 插入排序

1.4.1 插入排序定义

定义：插入排序是一种简单的排序算法，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
详细说明：插入排序在小规模数据集上的性能较好，时间复杂度为O(n^2)。对于部分已排序的数据集，插入排序表现得尤其好。

1.4.2 插入排序实现

void insertion_sort(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;
    }
}

1.5 快速排序

1.5.1 快速排序定义

定义：快速排序是一种高效的排序算法，采用分治策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。
详细说明：快速排序平均情况下时间复杂度为O(n log n)，但在最坏的情况下退化为O(n^2)。快速排序通常比其他O(n log n)排序算法快，因为它内部循环可以在小数组上执行得很好。

1.5.2 快速排序实现

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

1.6 归并排序

1.6.1 归并排序定义

定义：归并排序也是一种高效的排序算法，采用分治策略来分割数组，然后将分割后的子数组合并。
详细说明：归并排序的时间复杂度为O(n log n)，并且是稳定的排序算法。归并排序适用于大数据集，特别是在外部排序中。

1.6.2 归并排序实现

void merge_sort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        merge_sort(arr, l, m);
        merge_sort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    int i = 0;
    int j = 0;
    int k = l;
    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++;
    }
}

1.7 排序算法的高级应用

定义：排序算法的高级应用包括自定义比较函数、多关键字排序等。
详细说明：排序算法可以根据特定的需求进行定制，例如支持用户自定义的比较函数。

1.7.1 自定义比较函数

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

void custom_sort(int arr[], int n) {
    qsort(arr, n, sizeof(int), compare);
}

1.7.2 多关键字排序

struct Record {
    int id;
    int score;
};

int compare_records(const void *a, const void *b) {
    struct Record *record_a = (struct Record *)a;
    struct Record *record_b = (struct Record *)b;
    if (record_a->score == record_b->score)
        return (record_a->id - record_b->id);
    return (record_a->score - record_b->score);
}

void sort_records(struct Record records[], int n) {
    qsort(records, n, sizeof(struct Record), compare_records);
}

1.8 排序算法分析

定义：排序算法分析涉及时间复杂度、空间复杂度、稳定性等方面。
详细说明：不同排序算法的时间复杂度、空间复杂度和稳定性不同，因此在选择排序算法时需要考虑这些因素。

1.8.1 时间复杂度分析

冒泡排序: O(n^2)
选择排序: O(n^2)
插入排序: O(n^2)
快速排序: 平均 O(n log n)，最坏 O(n^2)
归并排序: O(n log n)

1.8.2 空间复杂度分析

冒泡排序: O(1)
选择排序: O(1)
插入排序: O(1)
快速排序: O(log n) (递归栈空间)
归并排序: O(n) (辅助数组)

1.8.3 稳定性分析

冒泡排序: 稳定
选择排序: 不稳定
插入排序: 稳定
快速排序: 不稳定
归并排序: 稳定

在这里插入图片描述

2. 查找算法

2.1 查找算法概述

定义：查找算法是在给定的数据集中搜索特定元素的过程。
详细说明：查找算法在数据库查询、搜索引擎等领域有着广泛的应用。不同的查找算法适用于不同类型的数据集。

2.2 顺序查找

2.2.1 顺序查找定义

定义：顺序查找是一种简单的查找算法，它从数据集的第一个元素开始，按顺序比较每个元素直到找到目标元素。
详细说明：顺序查找的时间复杂度为O(n)。

2.2.2 顺序查找实现

int linear_search(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x)
            return i;
    }
    return -1;
}

2.3 二分查找

2.3.1 二分查找定义

定义：二分查找是一种高效的查找算法，它要求数据集是有序的。算法通过将目标值与中间元素进行比较，不断缩小查找范围，直到找到目标元素。
详细说明：二分查找的时间复杂度为O(log n)。

2.3.2 二分查找实现

int binary_search(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binary_search(arr, l, mid - 1, x);
        return binary_search(arr, mid + 1, r, x);
    }
    return -1;
}

2.4 哈希查找

2.4.1 哈希查找定义

定义：哈希查找是一种基于哈希表的高效查找算法，它通过哈希函数将键映射到哈希表的一个位置来访问记录，这使得查找能在常数时间内完成。
详细说明：哈希查找的时间复杂度在理想情况下为O(1)。

2.4.2 哈希查找实现

#define TABLE_SIZE 100
#define hash_function(key) (key % TABLE_SIZE)

struct HashTable {
    int table[TABLE_SIZE];
};

void initialize_hash_table(struct HashTable *table) {
    for (int i = 0; i < TABLE_SIZE; i++)
        table->table[i] = -1;
}

int search_hash_table(struct HashTable *table, int key) {
    int index = hash_function(key);
    if (table->table[index] == key)
        return index;
    return -1;
}

2.5 查找算法的高级应用

定义：查找算法的高级应用包括多关键字查找、模糊查找等。
详细说明：查找算法可以根据特定的需求进行定制，例如支持用户自定义的查找条件。

2.5.1 多关键字查找

struct Record {
    int id;
    int score;
};

struct Record records[] = {
    {1, 90},
    {2, 85},
    {3, 95},
    {4, 88},
    {5, 92}
};

int find_record_by_id(int id) {
    for (int i = 0; i < sizeof(records)/sizeof(records[0]); i++) {
        if (records[i].id == id)
            return i;
    }
    return -1;
}

2.5.2 模糊查找

#include <string.h>

int fuzzy_search(char *arr[], int n, char *pattern) {
    for (int i = 0; i < n; i++) {
        if (strstr(arr[i], pattern))
            return i;
    }
    return -1;
}

2.6 查找算法分析

定义：查找算法分析涉及时间复杂度、空间复杂度、适应性等方面。
详细说明：不同查找算法的时间复杂度、空间复杂度和适应性不同，因此在选择查找算法时需要考虑这些因素。

2.6.1 时间复杂度分析

顺序查找: O(n)
二分查找: O(log n)
哈希查找: 平均 O(1)，最坏 O(n) (冲突严重时)

2.6.2 空间复杂度分析

顺序查找: O(1)
二分查找: O(1)
哈希查找: O(m) (m为哈希表大小)

2.6.3 适应性分析

顺序查找: 适用于无序数据集
二分查找: 适用于有序数据集
哈希查找: 适用于大量数据集，需合理设计哈希函数以减少冲突

结论

本章深入探讨了C语言中的排序算法和查找算法，包括基本概念、实现方法以及高级应用。我们不仅讨论了这些算法的基本原理，还提供了详细的示例代码来帮助读者更好地理解和运用这些概念。

排序算法

冒泡排序
- 定义：通过重复遍历要排序的数列，比较相邻元素并交换。
- 时间复杂度：O(n^2)。
- 适用场景：适合小规模数据集。
选择排序
- 定义：通过查找最小（或最大）元素并放到已排序序列的起始位置。
- 时间复杂度：O(n^2)。
- 适用场景：适合小规模数据集。
插入排序
- 定义：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
- 时间复杂度：O(n^2)。
- 适用场景：适合部分已排序的数据集。
快速排序
- 定义：采用分治策略将序列分为较小和较大的两个子序列。
- 时间复杂度：平均O(n log n)，最坏O(n^2)。
- 适用场景：适用于大规模数据集。
归并排序
- 定义：采用分治策略分割数组，然后合并分割后的子数组。
- 时间复杂度：O(n log n)。
- 适用场景：适用于大数据集。
高级应用
- 自定义比较函数：允许用户自定义比较逻辑。
- 多关键字排序：支持多关键字排序。

查找算法

顺序查找
- 定义：从数据集的第一个元素开始，按顺序比较每个元素直到找到目标元素。
- 时间复杂度：O(n)。
- 适用场景：适用于无序数据集。
二分查找
- 定义：通过将目标值与中间元素进行比较，不断缩小查找范围。
- 时间复杂度：O(log n)。
- 适用场景：适用于有序数据集。
哈希查找
- 定义：通过哈希函数将键映射到哈希表的一个位置来访问记录。
- 时间复杂度：平均O(1)，最坏O(n)。
- 适用场景：适用于大量数据集。
高级应用
- 多关键字查找：支持多关键字查找。
- 模糊查找：支持模式匹配查找。

原文地址：https://blog.csdn.net/suifengme/article/details/141303652

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Java异常
下一篇：你不知道的C语言知识（第六期：字符/字符串/内存库函数）

多路复用——select
基于select机制的多路复用技术
阅读更多2024-10-10
速卖通、敦煌卖家备战双11+黑五前，怎么增加店铺曝光？
当排名不断提高，带来的流量也会增加，更多的买家将看到商品，进而促成订单量的快速增长。可以获得更多的自然搜索推荐机会，进而提高产品的曝光率和转化率，产品的购买率和评价对于转化率和平台排名至关重要。为了吸
阅读更多2024-10-10
安全工具 | 搭建带有 Web 仪表板的Interact.sh
Interactsh 是一个用于检测带外交互的开源工具。它是一种旨在检测导致外部交互的漏洞的工具。本文将主要介绍在子域上设置私有 Interact.sh 服务器以及部署其 Web 应用程序。只需一个
阅读更多2024-10-10
双向数据绑定原理图
在这里插入图片描述](https://i-blog.csdnimg.cn/direct/1930d5bf4f084d97aa62e72ef9d30e4e.pn。通知所有Watcher。用户看到更新后的
阅读更多2024-10-10
windows启微服务端口被占用情况的排查与解决方法
问题如下根据错误信息，问题出现在尝试启动服务器时，遇到了端口已被占用的情况（这意味着尝试绑定的端口19200已经被另一个进程占用了。
阅读更多2024-10-10
LabVIEW提高开发效率技巧----状态保存与恢复
在LabVIEW开发中，保存和恢复程序运行时的状态是一个关键技巧，特别是在涉及需要暂停或恢复操作的应用中。通过使用和函数，开发人员可以将程序当前的状态转换为字符串并保存，再在需要时恢复这些状态，确保程
阅读更多2024-10-10
JavaScript七大常见陷阱深度解析
JavaScript作为Web开发中的核心语言，因其灵活性和动态性而备受青睐。然而，这种灵活性也带来了一些常见的陷阱，稍有不慎便可能引发难以追踪的错误。以下是七个常见的JavaScript陷阱，帮助开
阅读更多2024-10-10
MySQL 多条件查询
在 MySQL 中，多条件查询通常使用WHERE子句来指定多个条件。这些条件可以通过逻辑运算符（如ANDORNOT）进行组合，以实现复杂的查询需求。
阅读更多2024-10-10
Windows10如何关闭自动更新
4. 点击"恢复"选项卡，将"第一次失败"、"第二次失败"、"后续失败"都改为"无操作"，然后点击&
阅读更多2024-10-10
Linux 互斥锁
互斥锁的使用、线程同步和互斥、条件变量的使用 ...
阅读更多2024-10-10