C学习笔记基础算法整理 (10.9 - )（正学习，持续更新中）

标签：temp 10.9 random len 学习 int 算法排序

本文涵盖了适合初学者学习的基础、经典算法。包括：递归递推、排序、搜索/查找、枚举、图/树遍历、动态规划等。推荐了解 C语言各部分基本知识 后进行学习。

学习使用算法，可以：

了解针对某类问题的通用解决方案
提高逻辑思维能力
将复杂的任务分解为简单的步骤
精简代码，避免造使山...
提高程序执行的效率，减少资源消耗

参考的学习资源：

[1] B站各视频

[2] FittenCode Chat

[3] C 语言教程 | 菜鸟教程 (runoob.com)

一、递归递推

递归和递推是解决规律性问题的两种常用方法。下面是对这两者的简单说明和用法

递归

递归是指定义一个函数时，在函数内部调用自身的过程。使用递归，即是将复杂问题分解成更易处理的子问题、并最终可以简化成一个可以直接解决的最基本情况。使用递归应该知道最基本情况的结果，以避免无限循环。

如下是一个通过递归方法计算斐波那契数列的函数：

可以把递归的过程表示成这样：f(20) = f(19)+f(18) = [f(18)+f(17)] + [f(17)+f(16)] = ...

#define Target 20

long long f(int target) {
	if (target == 1 || target == 2) {
		return 1;
	} else {
		return f(target - 1) + f(target - 2);
	}
}

递推

递推是指通过已有的已知条件，逐步推导出未知结果的方法。这种方法通常采用循环或公式来一步一步算出下一个结果，此时算出的结果就成为已知条件，并用来进一步向后推导，直到得到目标结果。递推不涉及函数的自我调用。

如下同样是计算斐波那契数列的函数，使用了递推原理：

#define Target 60

long long g(int target) {
	long long temp[Target + 1] = { 0 };
	temp[1] = 1;
	temp[2] = 1;

	for (int i = 3; i <= Target; i++) {
		temp[i] = temp[i - 1] + temp[i - 2];
	}
	return temp[target];
}

分别使用递归和递推计算斐波那契：

递归：

改为递推：

可以发现，在计算靠后的数时，使用递归出现了明显的延迟，而用递推就能秒出结果。这是因为递归的每次计算都会重新计算之前的数据，徒增不必要的计算量，使效率低下。所以在解决子问题较多的问题时，尽量不要使用递归。

二、排序算法

1.冒泡排序

冒泡排序应该是最简单的排序方法之一

其原理是：重复遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们互换位置。此算法的名字由来是因为小的元素会经由位置互换逐渐“浮”到数列的顶端（最前端）。

例程、注释及结果：

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define length 5

void bubbleSort(int random[], int len) {
	while (len > 1) {
		for (int i = 1; i < len; i++) {         //进行“一轮”数组遍历
			if (random[i - 1] > random[i]) {    //每当前值大于后值时
				int temp = random[i];           //就进行两值的位置互换
				random[i] = random[i - 1];
				random[i - 1] = temp;
			}
		}
	len--; //每遍历完一轮，最大数就会被移到末端完成排序
	}      //所以每轮完成后就不用再看移到末端的那个数，len减一
}

int main() {
//初始化随机数组
	int random[length];
	srand( (unsigned int)time(NULL) );
	for (int i = 0; i < length; i++) {
		random[i] = rand() % 100 + 1;
	}
//显示原数列
	printf("Original numbers: ");
	for (int i = 0; i < length; i++) {
		printf("%d ", random[i]);
	}
	printf("\n\n");
//冒泡排序
	bubbleSort(random, length);
//显示排序后结果
	printf("Sorted numbers: ");
	for (int i = 0; i < length; i++) {
		printf("%d ", random[i]);
	}
	printf("\n");

	return 0;
}

这是算法执行过程：

可以发现，这组随机数在第一轮排序后，顺序就已经确定了。所以之后剩的三轮排序都是没有用的。为了使算法在数组顺序确定后就结束运行，我们可以进行如下的优化：

void bubbleSort(int random[], int len) {
	int Chk = 1;                              //向函数中加入检测数
	while (len > 1 && Chk) {
		Chk = 0;                              //当一轮没有发生if数据交换时，检测数为0
		for (int i = 1; i < len; i++) {
			if (random[i - 1] > random[i]) {
				Chk = 1;                      //若此轮中发生数据交换，则检测数为1
				int temp = random[i];
				random[i] = random[i - 1];
				random[i - 1] = temp;
			}
		}
	len--;
	}        //结束一轮后，while()条件中的检测数若为0，则说明数组已排序完毕，直接退出循环
}

2.选择排序

选择排序是另一种简单排序方法

其基本思想是：在数列中标记最小元素，每轮结束后就和第i位交换，待一轮完i++后，再从剩余未排序元素中继续寻找并标记最小元素，之后再与i交换。以此类推，直到所有元素均排序完毕。

void selectSort(int random[], int len) {
	for (int i = 0; i < len; i++) {
		int minMark = i;                        //这是标记
		for (int j = i + 1; j < len; j++) {
			if (random[j] < random[minMark]) {  //一轮中，当找到一个更小的值时
				minMark = j;                    //就把标记放到此处
			}
		}
		int temp = random[i];                   //一轮完成后再进行交换操作
		random[i] = random[minMark];
		random[minMark] = temp;
	}
}

执行过程如下：

第一轮

第二、三、四轮（图里忘记改文字了...）：

3.插入排序

可以发现，刚才选择排序的操作似乎有些繁复。第二轮中将25和43交换后，第三轮又马上将43换回了前面。如何能避免这种反复横跳呢？答案是使用插入排序。

顾名思义，插入排序的原理是：对于未排序元素，在前面已排序的序列中从后向前扫描，找到正确的大小位置并插入。以此类推，直到所有元素均插入到正确的位置。

void insertSort(int random[], int len) {
	for (int i = 1; i < len; i++) {
		int j = i;
		int temp = random[i];
		while (j >= 1 && random[j - 1] > temp) {
			random[j] = random[j - 1];
			j--;
		}
		random[j] = temp;
	}
}

可以发现，所谓“插入”实际上是把较大数移动到后边的操作。

4.希尔排序

希尔排序，也称递减增量排序，是插入排序的一种更高效的优化版本。

什么叫“递减增量”？前面的插入排序是每次将相邻的两个数据进行比较，而希尔排序则是将待排序序列按照增量的间距划分为多个子序列，对每个子序列进行插入排序。第一轮跨度比较大，每轮排序完后将跨度减小（通常是减小二分之一），再重复排序步骤，直到最后跨度减为一，再进行一次排序即可完成对整个数组的排序。

例如：

有数组8，9，1，7，2，3，5，1，6，0，初始增量值（gap）为数组长度的一半5。

将第一、第五、第九...个数划为一个子序列（并不是明面上的划分出来，而是在for循环执行的顺序中，由于gap的存在使得同样间隔的数成为一组。这些组中的数会进行比较），第二、第六...，第三、第七...等等是另外几个子序列。然后对它们执行插入排序。

完成这一轮for后，gap就可以减小了。通常的做法是让gap / 2（即希尔序列），以此类推，直到最后一次gap等于1时，程序退化为普通的插入排序，随即完成数组的排序。

以下是代码实现：

void shellSort(int random[], int len) {
	int gap = len / 2;
	while (gap >= 1) {
        //对子序列进行插入排序
		for (int i = gap; i < len; i++) {
			int temp = random[i];
			int j = i;
			while ( j >= gap && random[j - gap] > temp ) {
				random[j] = random[j - gap];
				j -= gap;
			}
			random[j] = temp;
		}
		gap /= 2; //迭代
	}
}

希尔排序在处理大规模数据的排序时，因相较于前几种排序方法遍历次数更少，性能出色。

5.归并排序

归并排序的原理是先对数组进行递归处理，使其变为由单个数组成的数组（此时可看作有序），再将有序的子序列合并（merge）成一个排序序列，即“归并”。

（本人认为归并算法更适合将几个有序数列合并为一个有序数列，对于无序数列的排序，可能使用其他排序方法更高效。）

下为归并函数：

void merge(int arr[], int temp[], int left, int mid, int right) { //合并两个有序子数组
	//标记两个子序列的最初索引
	int i = left, j = mid + 1;
	int k = left; //临时数组的索引

	//将两个子序列合并到临时数组中
	while (i <= mid && j <= right) {
		if (arr[i] < arr[j]) { //如果左边的元素小于右边元素
			temp[k] = arr[i];
			i++;
			k++;
		} else {
			temp[k] = arr[j];
			j++;
			k++;
		}
	}

	//将剩余的元素复制到临时数组
	while (i <= mid) {
		temp[k] = arr[i];
		i++;
		k++;
	}
	while (j <= right) {
		temp[k] = arr[j];
		j++;
		k++;
	}

	//将临时数组中的元素复制回原数组
	for (i = left; i <= right; i++) {
		arr[i] = temp[i];
	}

}

void mergeSort(int arr[], int temp[], int left, int right) { //主归并函数
	if (left < right) {
		int mid = (left + right) / 2;
		mergeSort(arr, temp, left, mid); //对左边的子序列进行递归操作
		mergeSort(arr, temp, mid + 1, right); //对右边的子序列进行递归
		merge(arr, temp, left, mid, right); //合并两个子序列
	}
}

归并排序自始至终保持稳定的性能，即使在最坏情况下，其效率也不会降低，适合处理大数据量。

6.计数排序

7.基数排序

8.快速排序

9.堆排序

三、搜索算法

1.线性搜索

线性搜索（也称顺序搜索），是一种在数据结构中查找特定值的搜索算法，非常简单且适用性广。

它的原理是按顺序检查数据结构中的每个元素，直到找到所需的值或搜索完所有元素为止。

步骤：

从数据结构的第一个元素开始，将每个元素与目标值进行比较
如果当前元素与目标值匹配，则返回该元素的位置
如果当前元素不匹配，则移动到下一个元素
如果搜索到数据结构的末尾仍未找到目标值，则返回未找到的提示或特定值

以下是两个例子：

int linearSearch(int arr[], int length, int target) {
    for (int i = 0; i < length; i++) {
        if (arr[i] == target) {
            return i; //找到目标，返回索引
        }
    }
    return -1; //未找到，返回-1
}

#include <string.h>
int strSearch(char arr[20], int length, char target[]) {
    for (int i = 0; i < length; i++) {
        if (strcmp(arr[i], target) == 0) {
            return i; //找到目标字符串，返回索引
        }
    }
    return -1; //未找到返回-1
}

2.二分搜索

二分搜索是一种在有序数组中查找特定元素的搜索算法。

其原理是通过反复将搜索区间一分为二来缩小搜索范围，直到找到所需的元素或搜索区间为空。这样的做法通常比线性搜索更快，但前提是数组有序。如果想对无序数组进行二分搜索，则会引入额外的排序操作。

int binarySearch(int arr[], int n, int target) {
    int low = 0; //设置数组最前端索引
    int high = n - 1; //数组最末端索引

    while (low <= high) {                 //当搜索区间大于1时
        int mid = low + (high - low) / 2; //计算中间位
        if (arr[mid] == target) {
            return mid;                   //找到目标值，则返回索引
        } else if (arr[mid] < target) {
            low = mid + 1;                //在后半部分继续搜索
        } else {
            high = mid - 1;               //在前半部分继续
        }
    }

    return -1; //未找到则返回-1
}

二分搜索还有两个分支版本：斐波那契搜索和插值搜索。它们通过改变中间值的选择方式来减少分割的次数。但由于它们都有附加限制条件，并且在某些情况的效率甚至不如普通二分搜索，故不提及。

3.（补充）图和链表

4.深度优先搜索

5.广度优先搜索

四、其他算法

1.枚举算法

枚举算法，又称为穷举法或暴力算法，是一种简单直接的算法。

它的基本思想是遍历所有可能的候选解，逐一检查每一个候选解是否符合问题的解的要求。

如这道简单例题：

给定一个大于1的自然数n，判断其是否为素数。

枚举的思路就是遍历从2到n-1的所有整数，检查n能否被这些整数整除，从而判断是否为素数。

2.贪心算法

3.分治算法

4.动态规划

标签：temp,10.9,random,len,学习,int,算法,排序
From： https://blog.csdn.net/m0_59778421/article/details/142815865

C学习笔记基础算法整理 (10.9 - )（正学习，持续更新中）

目录

一、递归递推

递归

递推

二、排序算法

1.冒泡排序

2.选择排序

3.插入排序

4.希尔排序

5.归并排序

6.计数排序

7.基数排序

8.快速排序

9.堆排序

三、搜索算法

1.线性搜索

2.二分搜索

3.（补充）图和链表

4.深度优先搜索

5.广度优先搜索

四、其他算法

1.枚举算法

2.贪心算法

3.分治算法

4.动态规划

相关文章

赞助商

阅读排行

C学习笔记 基础算法整理 (10.9 - )（正学习，持续更新中）

目录

一、递归递推

递归

递推

二、排序算法

1.冒泡排序

2.选择排序

3.插入排序

4.希尔排序

5.归并排序

6.计数排序

7.基数排序

8.快速排序

9.堆排序

三、搜索算法

1.线性搜索

2.二分搜索

3.（补充）图和链表

4.深度优先搜索

5.广度优先搜索

四、其他算法

1.枚举算法

2.贪心算法

3.分治算法

4.动态规划

相关文章

赞助商

阅读排行

C学习笔记基础算法整理 (10.9 - )（正学习，持续更新中）