查找算法与排序算法

查找算法

二分查找 (要求熟练)

// C

// 二分查找法（递归实现）
int binarySearch(int *nums, int target, int left, int right)		// left代表左边界，right代表右边界
{
	if (left > right)	return -1;		// 如果左边大于右边，那么说明找不到，直接返回-1
	int mid = (left + right) / 2;		// 计算出中间位置的下标
	if (nums[mid] == target) return mid;	// 如果刚好相等，就返回下标
	if (nums[mid] > target) return binarySearch(nums, target, left, mid - 1);	// 如果大于，说明肯定不在右边，直接去左边找
	else return binarySearch(nums, target, mid + 1, right);		// 如果小于，说明肯定不在左边，直接去右边找
}

更多内容

七大查找算法 (C语言实现)：https://www.cnblogs.com/maybe2030/p/4715035.html

排序算法

基础排序

排序算法最好情况最坏情况空间复杂度稳定性
冒泡排序O(n)O(n^2)O(1)稳定
插入排序O(n)O(n^2)O(1)稳定
选择排序O(n^2)O(n^2)O(1)不稳定

冒泡排序 (要求熟练)

基本介绍

  • 冒泡排序的核心就是交换，通过不断地进行交换，一点一点将大的元素推向一端，每一轮都会有一个最大的元素排到对应的位置上，最后形成有序。

  • 动画演示：https://visualgo.net/zh/sorting

代码实现

// C

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

// 冒泡排序
void bubbleSort(int* arr, int size)
{
	int temp;
	bool ordered = true;	// 我们先假设传进来的数组是有序的
	for (int i = 0; i < size - 1; i++)
	{
		for (int j = 0; j < size - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])	// 如果没有执行if语句，说明数组确实是本来就有序
			{
				ordered = false;
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
		if (ordered)
		{
			printf("该数组本来就有序！\n");
			return;
		}
	}
}

// 输出数组中的内容
void show(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}


int main()
{
	// int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	int arr[] = { 7, 3, 5, 9, 2, 0, 6, 1, 4, 8 };
	int arrSize = 10;

	show(arr, arrSize);

	// 冒泡排序
	bubbleSort(arr, arrSize);

	show(arr, arrSize);

	getchar();
	return 0;
}

插入排序

基本介绍

  • 我们默认第一个是有序状态，剩余的部分我们会挨着遍历，然后将其插到前面对应的位置上去

  • 每轮排序会从后面依次选择一个元素，与前面已经处于有序的元素，从后往前进行比较，直到遇到一个不大于当前元素的的元素，将当前元素插入到此元素的前面

  • 动画演示：https://visualgo.net/zh/sorting

代码实现

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

// 插入排序
void insertSort(int* arr, int size)
{
	int current, j;
	for (int i = 1; i < size; i++)
	{
		current = arr[i];
		j = i;
		while (j > 0 && arr[j - 1] > current)
		{
			arr[j] = arr[j - 1];	// 找的过程中需要不断进行后移操作，把位置腾出来
			j--;
		}
		arr[j] = current;
	}
}

// 输出数组中的内容
void show(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}


int main()
{
	int arr[] = { 7, 3, 5, 9, 2, 0, 6, 1, 4, 8 };
	int arrSize = 10;

	show(arr, arrSize);

	// 插入排序
	insertSort(arr, arrSize);

	show(arr, arrSize);

	getchar();
	return 0;
}

选择排序

基本介绍

  • 每轮排序会从后面的所有元素中寻找一个最小的元素出来，然后与已经排序好的下一个位置进行交换

  • 动画演示：https://visualgo.net/zh/sorting

代码实现

// C

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

// 选择排序
void selectSort(int* arr, int size)
{
	for (int i = 0; i < size - 1; i++)
	{
		int min = i;	// arr[min]能访问最小元素

		// 内部循环
		for (int j = i + 1; j < size; j++)
		{
			if (arr[min] > arr[j])	min = j;	// 更新下标
		}

		// 经过内部循环后，此时 arr[min] 访问的一定是最小元素
		int temp = arr[i];
		arr[i] = arr[min];
		arr[min] = temp;
	}
}


// 选择排序优化版：双选择排序
// 1. 交换函数
void swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

// 2. 双选择排序
void twoSelectSort(int* arr, int size)
{
	// 设定最开始的范围为[0, size - 1], 每循环一轮后，left++, right--，缩小范围
	int left = 0, right = size - 1;

	// 每循环一轮，就缩小范围
	while (left < right)
	{
		int min = left, max = right;	// 假定当前范围内，最小数的下标为左边界的那一个，最大数的下标为右边界的那一个
		for (int i = left; i <= right; i++)		// 从当前的左边界一直遍历到当前的有边界，遍历过程中，记录最小数和最大数的下标
		{
			if (arr[i] < arr[min])	min = i;	// arr[i] 在不断变化的过程中，如果小于我们最开始假定的 arr[min] 最小值，就马上更新当前最小值的下标 min，从而记录了当前最新的最小值 arr[min]
			if (arr[i] > arr[max])	max = i;	// arr[i] 在不断变化的过程中，如果小于我们最开始假定的 arr[max] 最大值，就马上更新当前最小值的下标 max，从而记录了当前最新的最大值 arr[max]
		}
		// for 循环一轮过后，当前 arr[min] 和 arr[max] 存放的就是，这一轮 [left, right] 范围中的最小值和最大值
		swap(&arr[max], &arr[right]);		// 让当前最大值 arr[max] 和 我们假定的最大值 arr[right] 进行交换
		if (min == right)	min = max;		// 如果上面的要被交换的 arr[right] 刚好是本轮的最小值 arr[min]，那么发生交换后，arr[max] 里面存放的才是我们最开始的 arr[min]，所以我们需要更新 min
		swap(&arr[min], &arr[left]);		// 让当前最小值 arr[min] 和 我们假定的最小值 arr[left] 进行交换
		left++;		// 缩小范围
		right--;	// 缩小范围
	}
}

// 输出数组中的内容
void show(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}


int main()
{
	int arr[] = { 7, 3, 5, 9, 2, 0, 6, 1, 4, 8};
	int arrSize = 10;

	show(arr, arrSize);

	// 选择排序
	// selectSort(arr, arrSize);	// 选择排序
	twoSelectSort(arr, arrSize);	// 双选择排序

	show(arr, arrSize);

	getchar();
	return 0;
}

进阶排序

排序算法最好情况最坏情况空间复杂度稳定性
快速排序O(nlogn)O(n^2)O(nlogn)不稳定
希尔排序O(n^1.3)O(n^2)O(1)不稳定
堆排序O(nlogn)O(nlogn)O(1)不稳定

快速排序 (要求熟练)

基本概念

  • 快速排序是冒泡排序的进阶版本

  • 在冒泡排序中，进行元素的比较和交换是在相邻元素之间进行的，元素每次交换只能移动一个位置，所以比较次数和移动次数较多，效率相对较低

  • 而在快速排序中，元素的比较和交换是从两端向中间进行的，较大的元素一轮就能够交换到后面的位置，而较小的元素一轮就能交换到前面的位置，元素每次移动的距离较远，所以比较次数和移动次数较少，就像它的名字一样，速度更快

代码实现

图1：

在这里插入图片描述

图2：

在这里插入图片描述

代码：

// C

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

// 快速排序
void quickSort(int* arr, int start, int end)
{
	// 结束递归
	if (start >= end)	return;

	// ------------------------ 快速排序算法逻辑主体 ------------------------
	int leftPointer = start, rightPointer = end;	// 定义一对左右指针，方便待会标记
	int reference = arr[leftPointer];				// 选定参考值

	while (leftPointer < rightPointer)		// 两个指针不相遇才能进行循环
	{
		// 从右边开始，一直向左边寻找，直到找到比参考值小的数，将这个数移动到 arr[leftPointer]
		while (leftPointer < rightPointer && arr[rightPointer] >= reference)	rightPointer--;
		arr[leftPointer] = arr[rightPointer];

		// 从左边开始，一直向右边寻找，直到找到比参考值大的数，将这个数移动到 arr[rightPointer]
		while (leftPointer < rightPointer && arr[leftPointer] <= reference)		leftPointer++;
		arr[rightPointer] = arr[leftPointer];
	}

	// 退出循环，说明两个指针相遇，说明此时 leftPointer = rightPointer
	arr[leftPointer] = reference;	// 或者 arr[rightPointer] = reference;	两个都一样

	// 继续递归下去
	quickSort(arr, start, leftPointer - 1);
	quickSort(arr, rightPointer + 1, end);
}


// 输出数组中的内容
void show(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}


int main()
{
	int arr[] = { 7, 3, 5, 9, 2, 0, 6, 1, 4, 8 };
	int arrSize = 10;

	show(arr, arrSize);

	// 快速排序
	quickSort(arr, 0, arrSize - 1);

	show(arr, arrSize);

	getchar();
	return 0;
}

希尔排序

基本介绍

  • 希尔排序又叫缩小增量排序

  • 希尔排序是插入排序的进阶版本

  • 希尔排序对插入排序进行改进，它会对整个数组按照步长进行分组，优先比较距离较远的元素

  • 这个步长是由一个增量序列来定的，这个增量序列十分重要

代码实现

// C

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


// 希尔排序
void shellSort(int arr[], int size) {
	int delta = size / 2;
	while (delta >= 1) {
		// 这里依然是使用之前的插入排序，不过此时需要考虑分组了
		for (int i = delta; i < size; ++i) {		// 我们需要从delta开始，因为前delta个组的第一个元素默认是有序状态
			int j = i, tmp = arr[i];		// 这里依然是把待插入的先抽出来
			while (j >= delta && arr[j - delta] > tmp) {
				// 注意这里比较需要按步长往回走，所以说是j - delta，此时j必须大于等于delta才可以，如果j - delta小于0说明前面没有元素了
				arr[j] = arr[j - delta];
				j -= delta;
			}
			arr[j] = tmp;
		}
		delta /= 2;		// 分组插排完事之后，重新计算步长
	}
}


// 输出数组中的内容
void show(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}


int main()
{
	int arr[] = { 7, 3, 5, 9, 2, 0, 6, 1, 4, 8 };
	int arrSize = 10;

	show(arr, arrSize);

	// 快速排序
	shellSort(arr, arrSize);

	show(arr, arrSize);

	getchar();
	return 0;
}

堆排序

基本认识

  • 堆排序也是选择排序的一种，但是它能够比直接选择排序更快
  • 对于一棵完全二叉树，树中父亲结点都比孩子结点小的我们称为小根堆（小顶堆），树中父亲结点都比孩子结点大则是大根堆
  • 得益于堆是一棵完全二叉树，我们可以很轻松地使用数组来进行表示

在这里插入图片描述

// C

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

// 输出数组中的内容
void show(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}


// 堆
typedef int E;
typedef struct MinHeap {
	E* arr;
	int size;
	int capacity;
} *Heap;


// 初始化堆
bool initHeap(Heap heap) {
	heap->size = 0;
	heap->capacity = 10;
	heap->arr = (E*)malloc(sizeof(E) * heap->capacity);
	return heap->arr != NULL;
}


// 插入元素
bool insert(Heap heap, E element) {
	if (heap->size == heap->capacity) return false;
	int index = ++heap->size;
	while (index > 1 && element < heap->arr[index / 2]) {
		heap->arr[index] = heap->arr[index / 2];
		index /= 2;
	}
	heap->arr[index] = element;
	return true;
}

// 删除元素
E remove(Heap heap) {
	E max = heap->arr[1], e = heap->arr[heap->size--];
	int index = 1;
	while (index * 2 <= heap->size) {
		int child = index * 2;
		if (child < heap->size && heap->arr[child] > heap->arr[child + 1])
			child += 1;
		if (e <= heap->arr[child]) break;
		else heap->arr[index] = heap->arr[child];
		index = child;
	}
	heap->arr[index] = e;
	return max;
}


int main() {
	int arr[] = { 3, 5, 7, 2, 9, 0, 6, 1, 8, 4 };
	int arrSize = 10;

	show(arr, arrSize);

	struct MinHeap heap;    // 创建堆
	initHeap(&heap);		// 初始化堆

	for (int i = 0; i < 10; ++i)
	{
		insert(&heap, arr[i]);		// 直接把乱序的数组元素挨个插入
	}

	for (int i = 0; i < 10; ++i)
	{
		arr[i] = (int)remove(&heap);		// 然后再一个一个拿出来，就是按顺序的了
	}

	show(arr, arrSize);

	getchar();
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/592657.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

esp8266与uno使用软串口通信

esp8266与uno使用软串口通信

esp8266的d6和d5分别与uno的5和6管脚连接&#xff1a; uno程序&#xff1a; //uno #include <SoftwareSerial.h> SoftwareSerial s(5,6);//(RX,TX)void setup(){s.begin(9600);Serial.begin(9600); }void loop(){int data50;if (s.available() > 0) {char c s.read(…
阅读更多...
【错题集-编程题】比那名居的桃子（滑动窗口 / 前缀和）

【错题集-编程题】比那名居的桃子（滑动窗口 / 前缀和）

牛客对应题目链接&#xff1a;比那名居的桃子 (nowcoder.com) 一、分析题目 1、滑动窗口 由题意得&#xff0c;我们是要枚举所有大小为 k 的子数组&#xff0c;并且求出这段⼦数组中快乐值和羞耻度之和。因此&#xff0c;可以利用滑动窗口的思想&#xff0c;用两个变量维护大小…
阅读更多...
【区块链】共识算法简介

【区块链】共识算法简介

共识算法简介 区块链三要素&#xff1a; 去中心化共识算法智能合约 共识算法作为区块链三大核心技术之一&#xff0c;其重要性不言而喻。今天就来简单介绍共识算法的基本知识。 最简单的解释&#xff0c;共识算法就是要让所有节点达成共识&#xff0c;保证少数服从多数&#x…
阅读更多...
从零开始学AI绘画，万字Stable Diffusion终极教程（六）

从零开始学AI绘画，万字Stable Diffusion终极教程（六）

【第6期】知识补充 欢迎来到SD的终极教程&#xff0c;这是我们的第六节课&#xff0c;也是最后一节课 这套课程分为六节课&#xff0c;会系统性的介绍sd的全部功能&#xff0c;让你打下坚实牢靠的基础 1.SD入门 2.关键词 3.Lora模型 4.图生图 5.controlnet 6.知识补充 …
阅读更多...
初识C语言——第九天

初识C语言——第九天

ASCII定义 在 C 语言中&#xff0c;每个字符都对应一个 ASCII 码。ASCII 码是一个字符集&#xff0c;它定义了许多常用的字符对应的数字编码。这些编码可以表示为整数&#xff0c;也可以表示为字符类型。在 C 语言中&#xff0c;字符类型被定义为一个整数类型&#xff0c;它占…
阅读更多...
C/C++开发，opencv-ml库学习，K近邻（KNN）应用

C/C++开发，opencv-ml库学习，K近邻（KNN）应用

目录 一、k近邻算法 1.1 算法简介 1.2 opencv-k近邻算法 二、cv::ml::KNearest应用 2.1 数据集样本准备 2.2 KNearest应用 2.3 程序编译 2.4 main.cpp全代码 一、k近邻算法 1.1 算法简介 K近邻算法&#xff08;K-Nearest Neighbor&#xff0c;KNN&#xff09;基本原理是…
阅读更多...
Vue按照顺序实现多级弹窗（附Demo）

Vue按照顺序实现多级弹窗（附Demo）

目录 前言1. 单个弹窗2. 多级弹窗 前言 强化各个知识点&#xff0c;以实战融合&#xff0c;以下两个Demo从实战提取 1. 单个弹窗 部署按钮框以及确定的方法即可 截图如下所示&#xff1a; 以下Demo整体逻辑如下&#xff1a; 点击“生成周月计划”按钮会触发showWeekPlanDia…
阅读更多...
FLIR LEPTON3.5 热像仪wifi 科研实验测温采集仪

FLIR LEPTON3.5 热像仪wifi 科研实验测温采集仪

点击查看详情!点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情点击查看详情 1、描述 这是一款桌面科研实验测温热成像多功能热像记录仪&#xff0c;小巧轻便…
阅读更多...
STM32微秒级别延时--F407--TIM1

STM32微秒级别延时--F407--TIM1

基本配置&#xff1a; TIM1挂载在APB2总线上&#xff0c;150MHz经过15分频&#xff0c;得到10MHz计数频率&#xff0c;由于disable了自动重装载&#xff0c;所以只需要看下一次计数值是多少即可。 void TIM1_Delay_us(uint16_t us) //使用阻塞方式进行延时&#xff0c;ARR值不…
阅读更多...
记录vue报错问题 in ./node_modules/axios/lib/platform/index.js

记录vue报错问题 in ./node_modules/axios/lib/platform/index.js

今天这个问题困扰了我许久 报错内容如下&#xff1a; 最初一直以为是我没装axios&#xff0c;又重新装了一次&#xff0c;后面才发现是axios版本原因&#xff0c;真的总是被版本的原因困住真的很烦 解决方法如下&#xff1a; 将axios的版本改为1.5.0 1、打开项目的文件夹“…
阅读更多...
Linux命令--查找占磁盘空间最大的文件

Linux命令--查找占磁盘空间最大的文件

原文网址&#xff1a;Linux命令--查找占磁盘空间最大的文件-CSDN博客 简介 本文介绍Linux怎样查找占磁盘空间最大的文件。 1.找到占空间最大的分区 命令 df -h 结果 2.查找分区里最大的文件 法1&#xff1a;直接查找最大的文件 sudo find my_folder -type f -exec du -…
阅读更多...
LangChain-RAG学习之 LangChain框架入门

LangChain-RAG学习之 LangChain框架入门

什么是LangChain LangChain是一个强大的框架&#xff0c;旨在帮助开发人员使用语言模型构建端到端的应用程序。它提供了一套工具、组件和接口&#xff0c;可简化创建由大型语言模型 (LLM) 和聊天模型提供支持的应用程序的过程。LangChain 可以轻松管理与语言模型的交互&#x…
阅读更多...
使用FastGPT+OneAPI在本地使用Llama3

使用FastGPT+OneAPI在本地使用Llama3

FastGPT 是一个基于 LLM 大语言模型的知识库问答系统&#xff0c;提供开箱即用的数据处理、模型调用等能力。同时可以通过 Flow 可视化进行工作流编排&#xff0c;从而实现复杂的问答场景&#xff01;他的重要特点就是工作流编排。 工作流编排&#xff1a;基于 Flow 模块的工作…
阅读更多...
OneNote导出白色背景文件时将笔记墨迹转换颜色

OneNote导出白色背景文件时将笔记墨迹转换颜色

今天用OneNote导出笔记时发现在文件上做的黑色墨迹笔记全部转成了白色。推测是因为onenote会根据背景色自动转换黑色和白色的墨迹&#xff0c;但是其他颜色好像导出的时候不会转换。 于是&#xff0c;我们首先要转换背景&#xff0c;将黑色背景转成白色背景&#xff0c; 然后将…
阅读更多...
国内各种免费AI聊天机器人(ChatGPT)推荐(中)

国内各种免费AI聊天机器人(ChatGPT)推荐(中)

作者主页&#xff1a;点击&#xff01; 国内免费AI推荐(ChatGPT)专栏&#xff1a;点击&#xff01; 创作时间&#xff1a;2024年4月29日15点20分 随着人工智能技术的不断发展&#xff0c;AI聊天机器人已经逐渐融入我们的日常生活。它们可以提供各种服务&#xff0c;例如聊天、…
阅读更多...
【数据结构】链表专题2

【数据结构】链表专题2

前言 本篇博客继续探讨有关链表的专题&#xff0c;这片博客的题&#xff0c;提前打个预防针&#xff0c;有点意思哦&#xff0c;哈哈哈&#xff0c;话不多说&#xff0c;进入正文 &#x1f493; 个人主页&#xff1a;小张同学zkf ⏩ 文章专栏&#xff1a;数据结构 若有问题 评论…
阅读更多...
【C语言】分支和循环（上）

【C语言】分支和循环（上）

【C语言】分支和循环&#xff08;上&#xff09; 1、if语句1.2 else1.3分支中包含多条语句1.4嵌套if1.5悬空else问题 2、关系操作符3、条件操作符4、逻辑操作符&#xff1a;与、或、非&#xff08;取反&#xff09;&#xff08;&&&#xff0c;||&#xff0c;&#xff0…
阅读更多...
小程序引入 Vant Weapp 极简教程

小程序引入 Vant Weapp 极简教程

一切以 Vant Weapp 官方文档 为准 Vant Weapp 官方文档 - 快速入手 1. 安装nodejs 前往官网下载安装即可 nodejs官网 安装好后 在命令行&#xff08;winr&#xff0c;输入cmd&#xff09;输入 node -v若显示版本信息&#xff0c;即为安装成功 2. 在 小程序根目录 命令行/终端…
阅读更多...
mac nvm install node＜version＞ error 404

mac nvm install node＜version＞ error 404

mac m2芯片遇到的问题&#xff0c;估计m系列的应该也有这个问题&#xff0c;在这里记录一下 解决方案&#xff1a; ## 需要先处理一下兼容就OK了arch -x86_64 zsh nvm install returns curl: (22) The requested URL returned error: 404 Issue #2667 nvm-sh/nvm GitHub
阅读更多...
关于YOLO8学习（五）安卓部署ncnn模型--视频检测

关于YOLO8学习（五）安卓部署ncnn模型--视频检测

前文 关于YOLO8学习（一）环境搭建，官方检测模型部署到手机 关于YOLO8学习（二）数据集收集，处理 关于YOLO8学习（三）训练自定义的数据集 关于YOLO8学习（四）模型转换为ncnn 简介 本文将会讲解： （1）使用前文生成的ncnn模型，部署到安卓端，并且实现视频中，人脸的检测…
阅读更多...
最新文章

Copyright @ 2022~2023