C语言的一些基础算法知识

一；位运算思维

2的整数次方的数的二进制中只有一个 1 如 4 ——> 100 8 ——> 1000
2个相同的2进制数做不进位加法，结果为0 10个相同的10进制数做不进位加法，结果为0 k个相同的k进制数做不进位加法，结果为0

两个相同的二进制数相加等于该数左移一位（x10）

如两个3相加： 011+011= 110

二：顺序表关键：连续存储

顺序表就是数组，但是在数组的基础上，它还要求数据是从头开始存储并且是连续存储的，不能跳跃间隔

linbei-pro/SeqList: 用C语言实现的一个动态的顺序表 (github.com)

linbei-pro/DynamicArray: 在C语言中，使用结构体和动态分配内存来模拟动态数组，从而实现类似容器的功能 (github.com)

三：链表

顺序表的缺陷：1.空间不够了就要增容，增容就要付出代价

避免频繁扩容，空间满了基本是扩2倍，也可能出现空间的浪费
顺序表要求数据从开始位置连续存储，那么我们从头部插入或删除数据就要挪动数据，效率不高

所以，针对顺序表的缺陷，就设计出了链表

linbei-pro/List-pro: 用C语言写的一个双向带头循环链表，并实现尾插，尾删，头插，头删等功能 (github.com)

四：排序

1.插入排序

直接插入排序：类似于一摞牌，一张一张摸，并排序

希尔排序：希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。优点：大量元素越来越有序，速度越来越快。

linbei-pro/InsertSort: 用C语言写的一个直接插入排序 (github.com)

2. 分治

快速排序：重点在于划分区域

linbei-pro/quickSort: 用C语言写的一个快速排序的程序 (github.com)

归并排序：重点在于合并

linbei-pro/mergesort: 归并排序 (github.com)

3.堆排序

堆排序：二叉堆是完全二叉树或者是近似完全二叉树（每个根都有左子树和右子树）

二叉堆满足两个性质：

1 .父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

2.每个节点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

linbei-pro/heapsort: 堆排序 (github.com)

4.计数排序

计数排序：是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)(其中k是整数的范围)，快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法。

  但计数排序有两个问题：

  1，如果序列中有负数 ？

  2，如何数据跨度很大 ？

优化：为了解决上述的负数问题和空间浪费问题，这里我们采用相对映射的方法。具体思路就是，找到序列的最大值和最小值，则开辟的空间数range=max-min+1。关键的一步来了，我们在映射时，将每个数据减去序列的最小值，将这个值做为新数组的下标。在还原时，只需要加上这个最小值，就能还原出原来的值，同时还解决了负数问题。

linbei-pro/countsort: 优化过后的计数排序 (github.com)

5.基数排序

1.按照个位，十位，百位，千位.......将数据匹配到二维数组对应行中

2.然后按从0到9从小到大的顺序收集二维数组中每一行的数据

3.依次实现从个位数有序，十位数有序，百位数有序......，从而达到序列整体有序

linbei-pro/radixsort: 基于桶排序的基数排序 (github.com)

6.桶排序

   什么意思：桶排序是一种排序算法，它将待排序元素分散到多个桶中，然后对每个桶内的元素进行排序，最后按照桶的顺序将所有元素合并成最终的有序序列。这种排序算法通常适用于元素分布均匀的情况。

   怎么把所有元素放入桶中： value/(max+1)*n     （n个桶）

         vaule/(max+1) 结果一定是0~1之间，再乘上一个n，结果一定小于n

         如此算出value应该在哪个桶，得出得是桶的下标

linbei-pro/bucketSort: 用C语言实现的桶排序算法 (github.com)

五：dfs

基本概念

深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。