c语言十大经典算法(c语言经典算法100例pdf) 收藏 0

11种常用排序算法的C语言代码实现

以下是常用的11种排序算法的C语言代码实现，附带有代码注释和讲解：

1.冒泡排序

冒泡排序是一种基础的排序算法。它的基本思想是重复地遍历数组，比较相邻的两个元素，如果它们的顺序不对，就交换它们的位置，直到数组排序完成。

2.插入排序

插入排序也是一种基础的排序算法。它的基本思想是将一个元素插入到已经排好序的数组中，一次将一个元素插入到正确的位置。这个算法在处理小型数据集时非常高效。

3.选择排序

选择排序也是一种基础的排序算法。它的基本思想是从未排序的数组中选择最小的元素，将其放在已排序的数组的末尾。这个算法在处理小型数据集时非常高效。

4.快速排序

快速排序是一种高效的排序算法，它的基本思想是选取一个元素作为分区点，将数组分为左右两部分，左部分的元素都小于等于分区点，右部分的元素都大于等于分区点。然后递归地对左右两部分进行快速排序。

5.归并排序

归并排序是一种稳定的排序算法，它的基本思想是将一个数组分成两个子数组，递归地对子数组进行排序，然后将两个子数组合并为一个有序数组。归并排序通常比快速排序慢，但是它能够处理大型数据集。

6.堆排序

堆排序是一种高效的排序算法，它的基本思想是将一个数组看成一个完全二叉树，然后将这个完全二叉树转换成一个堆，递归进行调整，最终得到一个有序数组。堆排序的时间复杂度为O(n log n)，空间复杂度为O(1)。

7.计数排序

计数排序是一种稳定的排序算法，它的基本思想是统计每个元素出现的次数，然后按照元素的大小顺序将它们放回原数组。计数排序的时间复杂度为O(n+k)，其中k是元素的范围，空间复杂度为O(n+k)。

8.桶排序

桶排序是一种稳定的排序算法，它的基本思想是将一个区间划分为若干个桶，然后将元素放入相应的桶中，对每个桶进行排序，最后将桶中的元素按照顺序合并为一个有序数组。

9.基数排序

基数排序是一种稳定的排序算法，它的基本思想是将整数按照位数进行分解，从低位到高位依次进行排序，最终得到一个有序数组。基数排序的时间复杂度为O(d(n+k))，其中d是位数，k是基数，空间复杂度为O(n+k)。

10.摇摆排序

摇摆排序是一种特殊的排序算法，它的基本思想是将数组元素按照摇摆的方式排列，即将相邻的元素交换，使得它们满足一定的条件。摇摆排序的时间复杂度为O(n)，空间复杂度为O(1)。

11.希尔排序

希尔排序是一种改进的插入排序算法，它的基本思想是将数组元素按照一定的间隔分组，对每组进行插入排序，然后逐步缩小间隔，最终得到一个有序数组。希尔排序的时间复杂度为O(n log n)，空间复杂度为O(1)。

硬核！C语言八大排序算法，附动图和详细代码解释

如果说各种编程语言是程序员的招式，那么数据结构和算法就相当于程序员的内功。

想写出精炼、优秀的代码，不通过不断的锤炼，是很难做到的。

排序算法作为数据结构的重要部分，系统地学习一下是很有必要的。

1、排序的概念

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

排序分为内部排序和外部排序。

若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。

反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

2、排序分类

八大排序算法均属于内部排序。如果按照策略来分类，大致可分为：交换排序、插入排序、选择排序、归并排序和基数排序。如下图所示：

3、算法分析1.插入排序

*直接插入排序

*希尔排序

2.选择排序

*简单选择排序

*堆排序

3.交换排序

*冒泡排序

*快速排序

4.归并排序

5.基数排序

不稳定排序：简单选择排序，快速排序，希尔排序，堆排序

稳定排序：冒泡排序，直接插入排序，归并排序，奇数排序

1、插入排序

将第一个和第二个元素排好序，然后将第3个元素插入到已经排好序的元素中，依次类推（插入排序最好的情况就是数组已经有序了）

2、希尔排序

因为插入排序每次只能操作一个元素，效率低。元素个数N，取奇数k=N/2，将下标差值为k的数分为一组（一组元素个数看总元素个数决定），在组内构成有序序列，再取k=k/2，将下标差值为k的数分为一组，构成有序序列，直到k=1，然后再进行直接插入排序。

3、简单选择排序

选出最小的数和第一个数交换，再在剩余的数中又选择最小的和第二个数交换，依次类推

4、堆排序

以升序排序为例，利用小根堆的性质（堆顶元素最小）不断输出最小元素，直到堆中没有元素

1.构建小根堆

2.输出堆顶元素

3.将堆低元素放一个到堆顶，再重新构造成小根堆，再输出堆顶元素，以此类推

5、冒泡排序

改进1：如果某次冒泡不存在数据交换，则说明已经排序好了，可以直接退出排序

改进2：头尾进行冒泡，每次把最大的沉底，最小的浮上去，两边往中间靠1

6、快速排序

选择一个基准元素，比基准元素小的放基准元素的前面，比基准元素大的放基准元素的后面，这种动作叫分区，每次分区都把一个数列分成了两部分，每次分区都使得一个数字有序，然后将基准元素前面部分和后面部分继续分区，一直分区直到分区的区间中只有一个元素的时候，一个元素的序列肯定是有序的嘛，所以最后一个升序的序列就完成啦。

7、归并排序

将一个无序的数列一直一分为二，直到分到序列中只有一个数的时候，这个序列肯定是有序的，因为只有一个数，然后将两个只含有一个数字的序列合并为含有两个数字的有序序列，这样一直进行下去，最后就变成了一个大的有序数列

8、基数排序

找到最大的数，开个比最大的数大一点的数组，遍历每个元素，某个元素为k，则a[k]++,最好遍历数组a，a[k]等于多少就输出多少个k。只能处理整型数

下面针对不同排序进行一一讲解。

一、直接插入排序（Insertion Sort)

算法思想：

直接插入排序的核心思想就是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过 因此，从上面的描述中我们可以发现，直接插入排序可以用两个循环完成：

第一层循环：遍历待比较的所有数组元素

第二层循环：将本轮选择的元素(selected)与已经排好序的元素(ordered)相比较。如果：selected > ordered，那么将二者交换。

算法代码：

二、希尔排序（Shell\’ s Sort）

算法思想:

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

算法步骤：

1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

2.按增量序列个数k，对序列进行k 趟排序；

3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

算法代码:

三、简单选择排序（Selection Sort）

算法思想：

简单选择排序的实现思想：比较+交换

1. 从待排序序列中，找到关键字最小的元素；

2. 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；

3. 从余下的 N – 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。因此我们可以发现，简单选择排序也是通过两层循环实现。第一层循环：依次遍历序列当中的每一个元素 第二层循环：将遍历得到的当前元素依次与余下的元素进行比较，符合最小元素的条件，则交换。

算法代码：

四、堆排序（Heap Sort）

算法思想：

堆的概念

堆：本质是一种数组对象。特别重要的一点性质：任意的叶子节点小于（或大于）它所有的父节点。对此，又分为大顶堆和小顶堆：

大顶堆要求节点的元素都要大于其孩子。

小顶堆要求节点元素都小于其左右孩子。

两者对左右孩子的大小关系不做任何要求。

利用堆排序，就是基于大顶堆或者小顶堆的一种排序方法。下面，我们通过大顶堆来实现。

基本思想：堆排序可以按照以下步骤来完成：

1.首先将序列构建称为大顶堆；（这样满足了大顶堆那条性质：位于根节点的元素一定是当前序列的最大值）

2. 取出当前大顶堆的根节点，将其与序列末尾元素进行交换；（此时：序列末尾的元素为已排序的最大值；由于交换了元素，当前位于根节点的堆并不一定满足大顶堆的性质）

3. 对交换后的n-1个序列元素进行调整，使其满足大顶堆的性质；

4. 重复2.3步骤，直至堆中只有1个元素为止

下面是基于大顶堆的堆排序算法代码：

五、冒泡排序（Bubble Sort）

算法思想：

冒泡遍历所有的数据，每次对相邻元素进行两两比较，如果顺序和预先规定的顺序不一致，则进行位置交换；这样一次遍历会将最大或最小的数据上浮到顶端，之后再重复同样的操作，直到所有的数据有序。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。

算法代码：

六、快速排序（Quick Sort）

算法思想：

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n logn)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤：

1. 从数列中挑出一个元素，称为 “基准”（pivot）。

2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

算法代码：

七、归并排序（Merge Sort）

算法思想：

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法步骤：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

4. 重复步骤3直到某一指针达到序列尾；

5. 将另一序列剩下的所有元素直接复制到合并序列尾。

算法代码：

八、基数排序(Radix Sort)

算法思想：

基数排序：通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。

分配：我们将L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中 。

收集：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列L 。

对新形成的序列L重复执行分配和收集元素中的十位、百位…直到分配完该序列中的最高位，则排序结束。

算法代码：

一、冒泡排序

冒泡排序算法的运作如下：

● 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

● 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

● 针对所有的元素重复以上的步骤，除了最后一个。

● 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

以上节选自维基百科

代码实现：

二、选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

以上节选自维基百科

代码实现：

三、插入排序

步骤如下:

● 从第一个元素开始，该元素可以认为已经被排序

● 取出下一个元素，在已经排序的元素序列中从后向前扫描

● 如果该元素（已排序）大于新元素，将该元素移到下一位置

● 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

● 将新元素插入到该位置后

重复步骤2~5

以上节选自维基百科

代码实现:

四、希尔排序

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

以上节选自维基百科

代码实现：

五、归并排序

原理如下（假设序列共有{displaystyle n}个元素）：

● 将序列每相邻两个数字进行归并操作，形成{displaystyle ceil(n/2)}个序列，排序后每个序列包含两/一个元素

● 若此时序列数不是1个则将上述序列再次归并，形成{displaystyle ceil(n/4)}个序列，每个序列包含四/三个元素

● 重复步骤2，直到所有元素排序完毕，即序列数为1

以上节选自维基百科

代码如下：

六、快速排序从数列中挑出一个元素，称为“基准”（pivot），

● 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。

● 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

● 递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

以上节选自维基百科

代码如下：

七、堆排序

若以升序排序说明，把数组转换成最大堆积(Max-Heap Heap)，这是一种满足最大堆积性质(Max-Heap Property)的二叉树：对于除了根之外的每个节点i, A[parent(i)] ≥ A[i]。

重复从最大堆积取出数值最大的结点(把根结点和最后一个结点交换，把交换后的最后一个结点移出堆)，并让残余的堆积维持最大堆积性质。

八、计数排序以上节选自维基百科

代码如下：

总结

各种排序的稳定性，时间复杂度和空间复杂度总结：

我们比较时间复杂度函数的情况：

时间复杂度函数O(n)的增长情况

所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。

时间复杂度来说：

(1)平方阶(O(n2))排序

各类简单排序:直接插入、直接选择和冒泡排序；

(2)线性对数阶(O(nlog2n))排序

快速排序、堆排序和归并排序；

(3)O(n1+§))排序,§是介于0和1之间的常数。

希尔排序

(4)线性阶(O(n))排序

基数排序，此外还有桶、箱排序。说明：

当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；

而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；

原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

稳定性：

排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。

稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较；

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

选择排序算法准则：

每种排序算法都各有优缺点。因此，在实用时需根据不同情况适当选用，甚至可以将多种方法结合起来使用。

选择排序算法的依据

影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法时还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下四点：

1．待排序的记录数目n的大小；

2．记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；

3．关键字的结构及其分布情况；

4．对排序稳定性的要求。

设待排序元素的个数为n.

1）当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

堆排序 ： 如果内存空间允许且要求稳定性的，

归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。

2） 当n较大，内存空间允许，且要求稳定性 =》归并排序

3）当n较小，可采用直接插入或直接选择排序。

直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。

直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序

4）一般不使用或不直接使用传统的冒泡排序。

5）基数排序

它是一种稳定的排序算法，但有一定的局限性：

1、关键字可分解。

2、记录的关键字位数较少，如果密集更好

3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。

总结

以上所述是小编给大家介绍的必须知道的C语言 八大排序算法，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对脚本之家网站的支持！

☞2019女性开发者报告：3成16岁就会编程、JS/Python成女性掌握最多语言

☞为了让自己快乐，我在36岁辞职了

9个常用数据结构与算法的C语言代码实现

动态数组是一种可以自动调整大小的数组，具有可变长度。在C语言中，可以使用指针和内存动态分配函数（如malloc和realloc）实现动态数组。

以下是一个简单的动态数组实现示例代码：

以上代码中，动态数组通过结构体实现，其中arr指向实际存储元素的数组，size表示当前数组中的元素个数，capacity表示数组最多可以容纳的元素个数。init函数用于初始化动态数组，append函数用于在数组末尾添加元素，如果数组容量不足，则动态扩展数组容量。print函数用于打印数组中的元素。在程序结束前，需要释放动态分配的内存。

链表是一种常见的数据结构，它由一组节点组成，每个节点包含一个值和一个指向下一个节点的指针。在C语言中，可以通过定义结构体来实现链表。

以下是一个简单的链表实现示例代码：

以上代码中，链表通过定义结构体来实现，其中data表示节点存储的值，next表示指向下一个节点的指针。insert函数用于在链表头部插入节点，print函数用于打印链表中的元素。在程序结束前，需要释放动态分配的内存

栈是一种后进先出（LIFO）的数据结构，它可以通过数组或链表实现。在C语言中，可以使用数组实现栈。

以下是一个简单的栈实现示例代码：

以上代码中，栈通过结构体实现，其中arr表示存储栈元素的数组，top表示栈顶元素的下标。init函数用于初始化栈，push函数用于将元素入栈，如果栈已满则报错，pop函数用于将栈顶元素出栈，如果栈为空则报错，peek函数用于查看栈顶元素，但不将其出栈。在程序结束前，不需要显式释放内存。

队列是一种先进先出（FIFO）的数据结构，它也可以通过数组或链表实现。在C语言中，可以使用数组实现队列。

以下是一个简单的队列实现示例代码：

以上代码中，队列通过结构体实现，其中arr表示存储队列元素的数组，front和rear分别表示队列头和队列尾元素的下标。init函数用于初始化队列，enqueue函数用于将元素入队，如果队列已满则报错，dequeue函数用于将队头元素出队，如果队列为空则报错，peek函数用于查看队头元素，但不将其出队。在程序结束前，不需要显式释放内存。

二叉树是一种树形结构，其中每个节点最多有两个子节点，分别为左子节点和右子节点。在C语言中，可以使用结构体和指针实现二叉树。

以下是一个简单的二叉树实现示例代码：

以上代码中，二叉树通过结构体实现，其中value表示节点的值，left和right分别表示左子节点和右子节点。create_node函数用于创建新节点，并返回指向该节点的指针。inorder_traversal函数用于中序遍历二叉树，即先遍历左子树，再遍历根节点，最后遍历右子树。在程序结束前，需要显式释放二叉树中所有节点的内存。

快速排序是一种常用的排序算法，其基本思想是通过选定一个基准元素，将待排序序列划分为两个子序列，其中一个子序列的所有元素均小于等于基准元素，另一个子序列的所有元素均大于等于基准元素，然后对两个子序列分别进行递归排序，最终将整个序列排序。

以下是一个简单的快速排序实现示例代码：

以上代码中，快速排序通过递归实现，其中partition函数用于选取基准元素，并将序列划分为两个子序列。具体地，选择最右边的元素为基准元素，使用i和j两个指针扫描整个序列，若arr[j]小于基准元素，则将其与arr[i+1]交换，并将i加1，最终将基准元素交换到i+1处。quick_sort函数用于递归排序子序列，直到整个序列有序。在程序结束前，不需要显式释放内存。

广度优先搜索是一种图遍历算法，其基本思想是从图中某个顶点开始，依次访问其所有邻居节点，然后再访问邻居节点的所有邻居节点，直到图中所有节点都被访问为止。在C语言中，可以使用队列实现广度优先搜索。

以下是一个简单的广度优先搜索实现示例代码：

以上是一个使用邻接表实现的BFS示例代码，其中使用了一个队列结构体，用于存储需要进行扩展的节点。首先将起始节点加入队列中，并标记为已访问过，然后不断从队列中取出一个节点，将其相连的未访问过的邻居节点加入队列，直到队列为空为止。这样遍历的过程就是一个层层扩展的过程，因此BFS也被称为“宽度优先搜索”。

上面的代码实现了一个简单的BFS算法，它可以接受从标准输入读入的图的描述，以及起始节点，然后打印出从起始节点开始的BFS遍历结果。其中，节点使用0~n-1的整数表示，图的描述使用每行两个整数u和v表示一条无向边。

二叉查找树是一种基于二分查找的数据结构，它具有以下性质：

• 左子树上所有节点的值均小于它的根节点的值
• 右子树上所有节点的值均大于它的根节点的值
• 左右子树都是二叉查找树

以下是一个简单的二叉查找树实现示例代码：

以上代码中，二叉查找树使用递归实现。insert函数用于向二叉查找树中插入一个节点，若当前节点为空，则将新节点插入；否则，根据当前节点的值和待插入节点的值大小关系，递归调用insert函数。inorder_traversal函数用于中序遍历二叉查找树，即先遍历左子树，然后访问根节点，最后遍历右子树。在程序结束前，需要显式释放内存。

哈希表是一种基于哈希函数实现的数据结构，它具有快速查找和插入的特点。在C语言中，可以使用数组和链表来实现哈希表。

以下是一个简单的哈希表实现示例代码：

以上代码中，哈希表使用链表解决哈希冲突，每个链表节点包含一个键值对。hash函数用于计算键值对应的哈希值，insert函数用于向哈希表中插入一个键值对，若当前位置为空，则直接插入；否则，将新节点插入到链表末尾。search函数用于在哈希表中查找指定键值的值，若存在则返回其值，否则返回-1。

这些常用的C语言数据结构、算法和功能代码示例，涵盖了常见的数据结构和算法，能够满足许多实际应用的需求。需要注意的是，在实际使用时，需要根据具体情况进行优化和改进，以适应不同的应用场景。

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com