[C语言]排序的大乱炖——喵喵的成长记

宝子，你不点个赞吗？不评个论吗？不收个藏吗？

最后的最后，关注我，关注我，关注我，你会看到更多有趣的博客哦！！！

喵喵喵，你对我真的很重要。

前言

小喵喵课堂开课来，今天我们学习七个常见的排序，哦哦耶！！！

喵喵今天也要加油哦！

来吧，不乱叫，上导图：

目录

前言

八大经典排序的概述

直接插入排序

希尔排序

选择排序

堆排序

冒泡排序

快速排序(快排）

归并排序

总结

┗|｀O′|┛ 嗷~~，怎么能忘了基数排序呢？补上补上：

八大经典排序的概述

八大排序算法是指常见的八种经典排序算法，它们分别是冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序和基数排序。

  1. 冒泡排序：比较相邻的元素，如果顺序错误就交换它们，重复这个过程直到整个数组有序。
  2. 选择排序：每次从待排序的数组中选择最小（或最大）的元素放在已排序数组的末尾，直到整个数组有序。
  3. 插入排序：遍历数组，将当前元素插入已排好序的子数组中的适当位置，直到整个数组有序。
  4. 希尔排序：通过设置间隔将数组分组，对每个分组进行插入排序，逐渐减小间隔，直到间隔为1时进行最后一次插入排序。
  5. 归并排序：采用分治的思想，将待排序数组划分为较小的子数组，然后递归地对子数组进行排序，并将排好序的子数组合并成更大的有序数组。
  6. 快速排序：选取一个基准元素，将数组划分为左右两部分，左边部分都比基准元素小，右边部分都比基准元素大，在递归地对左右两部分进行快速排序。
  7. 堆排序：将待排序数组构建成一个大顶堆，然后将堆顶元素与最后一个元素交换并重新调整堆，重复这个过程直到整个数组有序。
  8. 基数排序：根据元素的每个位上的值进行排序，先按低位排序，再按高位排序，直到所有位都排序完成。

直接插入排序

直接插入的排序规则，如图所示：

将end和tmp代入进去思考，一来的3，就算起始点，排好了位置，作为end,然后tmp是44，44>3，tmp>end,所以不交换位置，算排好了，end+1，tmp+1。那么第二次比较，end是44，tmp是38，end>tmp，交换位置，38排在44前面。那么第三次比较，5比44小，比38小，排在38前面。以此类推，循环排好数组。

void InSert(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int tmp = a[i];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

希尔排序

希尔排序是直接插入排序的升级版，先对数组进行有规律的分组，分成多个组，然后每个小组进行直接插入排序。每个小组排完后，再进行一次直接插入排序，就要轻松地多，能够快速排好，大大提高了排序的效率。

分成绿，蓝，红三组，分别进行直接插入排序。

void InsertSort(int* a, int n) 
{
	int gap = 3;
	for (j=0;j<gap;j++)
	{
		for (int i = j; i < n-gap; i+=gap)
		{
			int end = i;
			int tmp = a[i+gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end-=gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
	

}
void InsertSort(int* a, int n) 
{
	int gap = n;

	int j = 0;
	while (gap > 1)
	{
		gap = gap / 2;
		for (j = 0; j < gap; j++)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				int end = i;
				int tmp = a[i + gap];
				while (end >= 0)
				{
					if (tmp < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}
	}

}

选择排序

选择排序，很直观就是要选择，我们先选择3作为有序数组，然后从3后面的数组中选出最小的数，并于3进行比较，谁小谁站在前面。2比3小，2与3交换位置。依次往后推，拍成有序数组。

喵，很难评，这是简单版的一个点移动，而我们一般上的是困难版的两个点，喵，不好理解，喵喵，也是搞了好久，才明白滴，喵。那么让我们开始吧！猫猫队，冲冲冲！

两个点的移动（建议结合代码，自己也跟着走一走，感觉不就来了嘛！）：

//这是两个点的移动
void SelectSort(int* a, int n)
{
	int left = 0, right = n - 1;
	while (left < right)
	{
		int mini = left, maxi = left;
		for (int i = left + 1; i <= right; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}

			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}

		Swap(&a[left], &a[mini]);
		// 如果left和maxi重叠，交换后修正一下
		if (left == maxi)
		{
			maxi = mini;
		}

		Swap(&a[right], &a[maxi]);

		++left;
		--right;
	}
}

堆排序

就是以层序的方式从下往上，从大到小的排。升序建大堆，降序建小堆。

// 左右子树都是大堆/小堆
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 选出左右孩子中大的那一个
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	// 建堆 -- 向下调整建堆 -- O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	// 自己先实现 -- O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);

		--end;
	}
}

冒泡排序

冒泡排序，好理解，教学意义重大。简单的来说就是从一端开始，两两交换，把小的换在前面去就OK了！

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		bool exchange = false;
		for (int i = 1; i < n - j; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = true;
			}
		}

		if (exchange == false)
		{
			break;
		}
	}
}

快速排序(快排）

快排有很多种方法，比如hoare法，挖坑法，前后指针法：

1.hoare法：

无言，如图所示

int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
int PartSort1(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
		Swap(&a[midi], &a[left]);

	int keyi = left;
	while (left < right)
	{
		// 右边找小
		while (left < right && a[right] >= a[keyi])
			--right;

		// 左边找大
		while (left < right && a[left] <= a[keyi])
			++left;

		Swap(&a[left], &a[right]);
	}

	Swap(&a[keyi], &a[left]);
	keyi = left;

	return keyi;
}

挖坑法：

int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
int PartSort2(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
		Swap(&a[midi], &a[left]);

	// 21:10继续
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		// 右边找小
		while (left < right && a[right] >= key)
			--right;

		a[hole] = a[right];
		hole = right;

		// 左边找大
		while (left < right && a[left] <= key)
			++left;

		a[hole] = a[left];
		hole = left;
	}

	a[hole] = key;

	return hole;
}

前后指针法：

int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
int PartSort3(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
		Swap(&a[midi], &a[left]);

	int keyi = left;

	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[cur], &a[prev]);

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;

	return keyi;
}

归并排序（递归）：

int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
int PartSort3(int* a, int left, int right)
{
	// 三数取中
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
		Swap(&a[midi], &a[left]);

	int keyi = left;

	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
			Swap(&a[cur], &a[prev]);

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;

	return keyi;
}
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = PartSort3(a, left, right);
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi + 1, right);
}

总结

疯了，疯了，怎么才能讲清楚啊，白话文一大堆，还是图来说清楚，没看清楚的啾咪，留言喵喵鸭，你的明白，就是我的成长，酸Q喵。

宝子，你不点个赞吗？不评个论吗？不收个藏吗？

最后的最后，关注我，关注我，关注我，你会看到更多有趣的博客哦！！！

喵喵喵，你对我真的很重要。

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

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

相关文章

Python：实现日历功能

Python：实现日历功能

背景 日常生活中&#xff0c;每天都要用到日历&#xff0c;日历成为我们生活中的必需品&#xff0c;那么如何制作日历呢&#xff0c;其实方法有很多&#xff0c;可以直接在excel中制作&#xff0c;也可以手画等等。 学习过编程的朋友&#xff0c;能否想到用Python编写一…
阅读更多...
Docker从入门到实战

Docker从入门到实战

Docker基本概念 1、解决的问题 1、统一标准 应用构建 ○ Java、C、JavaScript ○ 打成软件包 ○ .exe ○ docker build … 镜像应用分享 ○ 所有软件的镜像放到一个指定地方 docker hub ○ 安卓&#xff0c;应用市场应用运行 ○ 统一标准的 镜像 ○ docker run 容器化技术 …
阅读更多...
STM32：TTL串口调试

STM32：TTL串口调试

一.TTL串口概要 TTL只需要两个线就可以完成两个设备之间的双向通信&#xff0c;一个发送电平的I/O称之为TX&#xff0c;与另一个设备的接收I/O口RX相互连接。两设备之间还需要连接地线(GND)&#xff0c;这样两设备就有相同的0V参考电势。 二.TTL串口调试 实现电脑通过STM32发送…
阅读更多...
current file is not included in a workspace moduleg 存在多个 main函数的 Go项目 无法成功导包

current file is not included in a workspace moduleg 存在多个 main函数的 Go项目 无法成功导包

报错缘由 学习 hystria, 尝试自测案例,使用了 go get “github.com/afex/hystrix-go/hystrix” 进行导入包&#xff0c; 导入成功后&#xff0c;在代码里利用 import 导入&#xff0c;但遇到了以下报错 could not import github.com/afex/hystrix-go/hystrix (current file i…
阅读更多...
【前端性能】性能优化手段-高频面试题

【前端性能】性能优化手段-高频面试题

持续更新.............................最近更新2023/10/24 1. 讲一下png8、png16、png32的区别&#xff0c;并简单讲讲 png 的压缩原理 PNG8、PNG16、PNG32 是 PNG 图像格式的不同变种&#xff0c;它们主要区别在于颜色深度和透明度支持的不同。 区别 PNG8&#xff1a; PN…
阅读更多...
指定顺序输出

指定顺序输出

系列文章目录 进阶的卡莎C++_睡觉觉觉得的博客-CSDN博客数1的个数_睡觉觉觉得的博客-CSDN博客双精度浮点数的输入输出_睡觉觉觉得的博客-CSDN博客足球联赛积分_睡觉觉觉得的博客-CSDN博客大减价(一级)_睡觉觉觉得的博客-CSDN博客小写字母的判断_睡觉觉觉得的博客-CSDN博客纸币(…
阅读更多...
Django 注册及创建订单商品

Django 注册及创建订单商品

注册功能的实现 user/views from rest_framework.generics import GenericAPIView from rest_framework.views import APIViewfrom apps.user.models import User from apps.user.serializers import UserSerializer from utils import ResponseMessage from utils.jwt_auth …
阅读更多...
C++前缀和算法的应用：从仓库到码头运输箱子原理、源码、测试用例

C++前缀和算法的应用：从仓库到码头运输箱子原理、源码、测试用例

本文涉及的基础知识点 C算法&#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 双指针 单调双向队列 题目 你有一辆货运卡车&#xff0c;你需要用这一辆车把一些箱子从仓库运送到码头。这辆卡车每次运输有 箱子数目的限制 和 总重量的限制 。 给你…
阅读更多...
JAVA基础（JAVA SE）学习笔记（八）面向对象编程（高级）

JAVA基础（JAVA SE）学习笔记（八）面向对象编程（高级）

前言 1. 学习视频&#xff1a; 尚硅谷Java零基础全套视频教程(宋红康2023版&#xff0c;java入门自学必备)_哔哩哔哩_bilibili 2023最新Java学习路线 - 哔哩哔哩 第二阶段&#xff1a;Java面向对象编程 6.面向对象编程&#xff08;基础&#xff09; 7.面向对象编程&…
阅读更多...
【干货】FMEA的实施流程——SunFMEA

【干货】FMEA的实施流程——SunFMEA

DFMEA和PFMEA的实施流程基本一致&#xff0c;都是先定义过程/功能、故障模式分析、故障原因分析、预防/探测措施的制定、风险风险&#xff0c;最后到制定补偿措施&#xff0c;具体如下图&#xff1a; FMEA实施流程——SunFMEA 一、定义过程/功能 FMEA工作的第一步&#xff0c;…
阅读更多...
IDEA配置HTML和Thymeleaf热部署开发

IDEA配置HTML和Thymeleaf热部署开发

IDEA配置HTML和Thymeleaf热部署开发 1.项目配置2. IDEA配置3. 使用 需求&#xff1a;现在我们在开发不分离项目的时候&#xff08;SpringBootThmeleaf&#xff09;经常会改动了类或者静态html文件就需要重启一下服务器&#xff0c; 这样不仅时间开销很大&#xff0c;而且经常重…
阅读更多...
APP 专项测试之兼容性测试

APP 专项测试之兼容性测试

1、APP 兼容性测试认识 随着 APP 应用范围越来越广&#xff0c;用户群体越来越大&#xff0c;终端设备的型号也越来越多&#xff0c;移动终端碎片化加剧&#xff0c;使得 APP 兼容性测试成为测试质量保障必须要考虑的环节。 APP 兼容性测试通常会考虑&#xff1a;操作系统、厂…
阅读更多...
IOS屏幕旋转监听

IOS屏幕旋转监听

IOS屏幕旋转 1.设计窗口,添加三个按钮 2.添加事件连接 3.按钮点击事件实现 先添加三个IBAction 实现IBAction 使用旋转立刻生效 -(IBAction)btnFixPortrait:(id)sender{//访问应用程序委托成员_app.mask UIInterfaceOrientationMaskPortrait;//设置窗口旋转属性[self setN…
阅读更多...
【Lua语法】字符串

【Lua语法】字符串

Lua语言中的字符串是不可变值。不能像在C语言中那样直接改变某个字符串中的某个字符&#xff0c;但是可以通过创建一个新字符串的方式来达到修改的目的 print(add2(1 , 2 ,15,3))a "no one"b string.gsub(a , "no" , "on1111")print(a) print…
阅读更多...
VisualStudio[WPF/.NET]基于CommunityToolkit.Mvvm架构开发

VisualStudio[WPF/.NET]基于CommunityToolkit.Mvvm架构开发

一、创建 "WPF应用程序" 新项目 项目模板选择如下&#xff1a; 暂时随机填一个目标框架&#xff0c;待会改&#xff1a; 二、修改“目标框架” 双击“解决方案资源管理器”中<项目>CU-APP, 打开<项目工程文件>CU-APP.csproj, 修改目标框架TargetFramew…
阅读更多...
关于 LLM 和知识图谱、图数据库，大家都关注哪些问题呢？

关于 LLM 和知识图谱、图数据库，大家都关注哪些问题呢？

自 LLM 系列文章《知识图谱驱动的大语言模型 Llama Index》、《Text2Cypher&#xff1a;大语言模型驱动的图查询生成》、《Graph RAG: 知识图谱结合 LLM 的检索增强》陆续和大家见面&#xff0c;以及《夜谈 LLM》主题直播同大家交流一番 LLM 和知识图谱、图数据库之后&#xff…
阅读更多...
Shiro框架详解

Shiro框架详解

权限管理 权限管理&#xff0c;一般指根据系统设置的安全策略或者安全规则&#xff0c;用户可以访问而且只能访问自己被授权的资源。 权限管理包括用户身份认证和授权两部分&#xff0c;简称认证授权。对于需要访问控制的资源用户首先经过身份认证&#xff0c;认证通过后用户…
阅读更多...
NFS性能瓶颈分析

NFS性能瓶颈分析

前言 atop – run it with -d option or press d to toggle the disk stats view. iostat – try it with the -xm 2 options for extended statistics, in megabytes, and in two-second intervals. iotop – top-like I/O monitor. Try it with the -oPa options to show the…
阅读更多...
vue 数据劫持代理原理

vue 数据劫持代理原理

function lianxi(){// vue 数据劫持代理let data {username:curry,age:33}//模拟组件的实例let _this {}//利用Object.defineProperty()for( let item in data){//console.log(item,data[item])Object.defineProperty(_this,item,{//get:用来获取扩展属性值的,当获取该属性值…
阅读更多...
个人创业新机遇，零成本开启真人手办定制项目

个人创业新机遇，零成本开启真人手办定制项目

桌上的日历变薄&#xff0c;2023年已经接近尾声&#xff0c;浅观这一年&#xff0c;您是否发现大家日常关注的重点有明显的变化&#xff0c;诸多社会事件和宏观数字的背后&#xff0c;潜藏着对经济的“不托底”&#xff0c;而当我们真正开始关注起用个人经济积累去对冲未来的不…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站