数据结构与算法——排序(C语言实现)

news/2024/5/26 19:21:45/文章来源:https://blog.csdn.net/weixin_74967884/article/details/136577457

请添加图片描述

✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌟🌟 追风赶月莫停留 🌟🌟
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀
🌟🌟 平芜尽处是春山🌟🌟
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅

🍋排序

  • 🍑插入排序
    • 🍍直接插入排序
    • 🍍希尔排序
  • 🍑选择排序
    • 🍍选择排序
    • 🍍堆排序
  • 🍑交换排序
    • 🍍冒泡排序
    • 🍍快速排序
      • 🍌快排(经典写法)
      • 🍌快排(挖坑法)
      • 🍌快排(双指针法)
      • 🍌快排优化
  • 🍑归并排序
    • 🍍归并排序(递归)
    • 🍍归并排序(非递归)

🍑插入排序

🍍直接插入排序

#include<stdio.h>
/// 直接插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 2; i++){int end = i;int cur = a[end + 1];while (cur >= 0){if (cur < a[end]){a[end + 1] = a[end];}else{break;}end--;}a[end + 1] = cur;}
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);InsertSort(a, size);for (int i = 0; i < size; i++){printf("%d ", a[i]);}return 0;
}

0到end有序,把end+1序列插入到前序序列
控制[end + 1]序列有序

直接插入排序有点类似尾插,都是从后面开始往前比较,和我们平常打扑克洗牌类似。

🍍希尔排序

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//保证了gap最小为1for (int i = 0; i < n - gap; i = i + gap){int end = i;int cur = a[end + gap];while (end >= 0){if (cur < a[end]){a[end + gap] = a[end];}else{break;}end = end - gap;}a[end + gap] = cur;}}
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);ShellSort(a, size);for (int i = 0; i < size; i++){printf("%d ", a[i]);}return 0;
}

在这里插入图片描述

该排序就是:预排序加直接插入排序

gap的作用就是分成多少组,一组一组的排

预排序的作用就是让大的数更快的到后面去,而小的数更快的到前面来
在这里gap等于1的时候就是直接插入排序

🍑选择排序

🍍选择排序

void Swap(int* a1, int* a2)
{int cur = *a1;*a1 = *a2;*a2 = cur;
}
void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int max = begin;int min = begin;for (int i = begin+1; i <= end; i++){if (a[i] < a[min]){min = i;}if (a[i] > a[max]){max = i;}}Swap(&a[begin], &a[min]);if (max == begin)//特殊情况{max = min;}Swap(&a[max], &a[end]);begin++;end--;}
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);SelectSort(a, size);Print(a, size);return 0;
}

在这里插入图片描述

图里就简单列出了三步,帮大家理清程序的逻辑。

选择排序就是从一堆数里选出最大和最小,然后最大的放在最右边,最小的放在最左边,然后在有效的数据长度里不断执行这一步就可以了。

然而还有一种特殊情况:

在这里插入图片描述
在图中,最大的数恰好是在begin位置上,我们程序上是先把最小的放到最左边,此时a[min]和a[begin]就会互换位置,如下:

在这里插入图片描述

此时max上的数已经不是最大的了,接下来再把最大的数放在最右边,就出错了,所以在这里我们就需要加一个判断:

if (max == begin)//特殊情况{max = min;}

大家可能还有疑问,我们这里的执行顺序是先把最小的数放在最左边,然后把最大的数放在最右边。

有的人肯定就会问如果先执行把最大的数放在最右边,再执行把最小的数放在最左边,这样是不是就不会出现这种特殊情况了。

但我想说的是,如果此时最小的数恰好在end上呢,两种都是特殊的情况,而且类似。

🍍堆排序

此处排序请看上篇博客:堆和二叉树的动态实现(C语言实现),这篇博客详细的介绍了堆排序。

🍑交换排序

🍍冒泡排序

void Swap(int* a1, int* a2)
{int cur = *a1;*a1 = *a2;*a2 = cur;
}void BuddleSort(int* a, int n)
{for (int i = 0; i < n; i++){for (int j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);}}}
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);BuddleSort(a, size);for (int i = 0; i < size; i++){printf("%d ", a[i]);}return 0;
}

冒泡排序大家应该熟悉,这个排序就是两个两个的比较,从第一个一直比到后面。这个冒泡排序是最基础的排序。

🍍快速排序

🍌快排(经典写法)

void Swap(int* a1, int* a2)
{int cur = *a1;*a1 = *a2;*a2 = cur;
}
int PartSort1(int* a, int left, int right)//单趟
{int key = left;while (left < right){while (left < right && a[right] >= a[key]){right--;}while (left < right && a[left] <= a[key]){left++;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[key]);return left;
}void QuickSort1(int* a, int left, int right)
{if (left >= right)return;int key = PartSort1(a, left, right);QuickSort1(a, left, key - 1);QuickSort1(a, key + 1, right);
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);QuickSort1(a, 0, size - 1);Print(a, size);return 0;
}

在这里插入图片描述
上图中就是单趟的走法。

在单趟走法中有几个坑:
(1)第一个坑就是在第一个while循环中有left<right了有的人就认为在while程序内部就会一直维持left<right,其实是错的。在单趟的走法中,无论是right往右走,还是left往左走,都有可能left>right发生。
(2)第二个坑就是在判断条件a[key]>=a[right]或者a[key]<=a[left]中,等号可不可以去掉。在这里可以肯定的是这个等号是不可以去掉的,去掉的话会陷入无限循环中。

在这个排序中,我们还是利用了二叉树的知识点,先从左子树排序,然后再是右子树,当然基础都是利用了递归。

如果有需要了解二叉树的知识可以查看这篇博客:堆和二叉树的动态实现(C语言实现),这篇博客详细的介绍了堆排序。

🍌快排(挖坑法)

int PartSort2(int* a, int left, int right)
{int key = a[left];int hold = left;while (left < right){//找小while (left < right && a[right] >= key){right--;}a[hold] = a[right];hold = right;//找大while (left < right && a[left] <= key){left++;}a[hold] = a[left];hold = left;}a[hold] = key;return hold;
}void QuickSort2(int* a, int left, int right)
{if (left >= right)return;int key = PartSort2(a, left, right);QuickSort2(a, left, key - 1);QuickSort2(a, key + 1, right);
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);QuickSort1(a, 0, size - 1);Print(a, size);return 0;
}

在这里插入图片描述
快排(挖坑法)这是比较好理解。其中需要注意的和上面的差不多。

🍌快排(双指针法)

void Swap(int* a1, int* a2)
{int cur = *a1;*a1 = *a2;*a2 = cur;
}
int PartSort3(int* a, int left, int right)
{int key = left;int cur = left + 1;int old = left;while (cur <= right){if (a[cur] <= a[key]){old++;Swap(&a[old], &a[cur]);}cur++;}Swap(&a[key], &a[old]);return old;
}void QuickSort3(int* a, int left, int right)
{if (left >= right)return;int key = PartSort3(a, left, right);QuickSort3(a, left, key - 1);QuickSort3(a, key + 1, right);
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);QuickSort3(a, 0, size - 1);Print(a, size);return 0;
}

在这里插入图片描述
这个双指针写法,明显比上面的两种都好理解,代码也简单些。这个想法还是如果a[cur]比key大,就光cur++。如果a[cur]比key小,就先old++,再把a[cur]赋给a[old],然后cur++。整体的思路就是这些。

🍌快排优化

上面我们介绍了三种快排的写法,其中我们在取key值的时候都是取left,left一开始都是代表最左边的数据,而在现实,left代表的值的大小不一定是在中间,如果left代表的值是较小的或者是较大的那么可能对于快排相较于其它排序来说,此种情况就是快排最坏的情况,可能比堆排或则希尔排序等来说还要慢。

所以在取key值的时候加了一个三数取中的程序:

// 三数取中
int GetMiddle(int* a, int left, int right)
{int mid = (left + right) / 2;// left mid rightif (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right])  // mid是最大值{return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]) // mid是最小{return left;}else{return right;}}
}

这个程序就是简单的取一个中间数的大小,这样快排就不会出现上面所讲的那种情况。

🍑归并排序

🍍归并排序(递归)

void _MergeSort(int* a, int *tem, int left, int right)
{//递归if (right <= left)return;int mid = (left + right) / 2;_MergeSort(a, tem, left, mid);_MergeSort(a, tem, mid+1, right);//归并,拷贝到tem中int left1 = left, right1 = mid;int left2 = mid + 1, right2 = right;int sum = left;while (left1 <= right1 && left2 <= right2){if (a[left1] < a[left2]){tem[sum++] = a[left1++];}else{tem[sum++] = a[left2++];}}while (left1 <= right1){tem[sum++] = a[left1++];}while (left2 <= right2){tem[sum++] = a[left2++];}memcpy(a + left, tem + left, (right - left + 1) * sizeof(int));}void MergeSort(int* a, int n)
{int* tem = (int*)malloc(sizeof(int) * n);if (tem == NULL){perror("malloc  fail");return;}_MergeSort(a, tem, 0, n - 1);free(tem);
}int main()
{int a[] = { 2,66,34,5,123,34,345,456 };int size = sizeof(a) / sizeof(a[0]);MergeSort(a, size);Print(a, size);return 0;
}

该种排序是利用递归实现的。

在这里插入图片描述
具体的流程如上面图中所示。大概就是分为六步,完成后在把数组拷贝回原来数组就可以了

🍍归并排序(非递归)

void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void MergeSortNort(int* a, int n)
{int* cur = (int*)malloc(n * sizeof(int));if (cur == NULL){perror("malloc  fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i = i + 2 * gap){int left1 = i, right1 = i + gap - 1;int left2 = i + gap, right2 = i + 2 * gap - 1;int sum = i;while (left1 <= right1 && left2 <= right2){if (a[left1] < a[left2]){cur[sum++] = a[left1++];}else{cur[sum++] = a[left2++];}}while (left1 <= right1){cur[sum++] = a[left1++];}while (left2 <= right2){cur[sum++] = a[left2++];}memcpy(a + i, cur + i, (2 * gap) * sizeof(int));}//printf("\n");gap = gap * 2;}}int main()
{int a[] = { 2,66,34,5,123,34,345,456, };int size = sizeof(a) / sizeof(a[0]);MergeSortNort(a, size);Print(a, size);return 0;
}

在这里插入图片描述

程序的逻辑就是图中一步一步的来,和递归的执行过程有些部分是相似的,就是在这里,空间的区分可能难以让人理解,大家可以代数进去尝试,多凭自己的想法写几遍,大致过程也就心里有数了。

大家在图中也看到了,最后gap取的是偶数,所以这个程序的前提条件就是数据只能是偶数次的数据,而一旦是奇数程序就会报错。接下来有一个修正版,大家可以先把偶数版的理解了,再去看奇数版的会轻松很多。

如果数据个数是偶数:
在这里插入图片描述

这里区间一切正常,也成功排序。

如果数据个数是奇数:

在这里插入图片描述

从图中可知,标的有箭头的区间划分中,都超出范围了,所以我们有必要修正

归并排序优化:

void Print(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void MergeSortNort(int* a, int n)
{int* cur = (int*)malloc(n * sizeof(int));if (cur == NULL){perror("malloc  fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i = i + 2 * gap){int left1 = i, right1 = i + gap - 1;int left2 = i + gap, right2 = i + 2 * gap - 1;printf("[%d  %d]  [%d  %d]\n", left1, right1, left2, right2);//如果第二组不存在,这一组就不用归并if (left2 >= n){break;}//如果第二组右边见越界了,就修正一下if (right2 >= n){right2 = n - 1;}int sum = i;while (left1 <= right1 && left2 <= right2){if (a[left1] < a[left2]){cur[sum++] = a[left1++];}else{cur[sum++] = a[left2++];}}while (left1 <= right1){cur[sum++] = a[left1++];}while (left2 <= right2){cur[sum++] = a[left2++];}memcpy(a + i, cur + i, (right2 - i + 1) * sizeof(int));}gap = gap * 2;}}int main()
{int a[] = { 2,66,34,5,123,34,345,456, 3};int size = sizeof(a) / sizeof(a[0]);MergeSortNort(a, size);Print(a, size);return 0;
}

修正后的程序,主要增加了2个判断和修改了范围。

两个判断:在这里插入图片描述
第一个判断是防止第二组区间不存在,就直接结束,如:

在这里插入图片描述

当然有的人就会问,在这个图中第一个区间的right2不是也超了吗,为什么不要判断right1呢?

大家可以试着想一想,如果right2超过了区间范围,left2是不是有可能也超过了范围。而left2超出范围了,right1是不是一定超出了范围。这就是一个谁先谁后的问题。大家可以仔细想一想,可以代数进去尝试一下。而且你判断了left2超出区间了,程序就已经跳出循环了。

第二个判断:

在这里插入图片描述

就是right2超出了区间范围,而left2没有超出,只需要把right2修正到有效范围就可以了,如上图所示,只需要把15修正成8,就可以了。

今天排序的知识点就得差不多了,本人水平有限,可以知识点尚未完全覆盖,请大家多多指教,谢谢!!!!!!!

请添加图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

探索Java高并发编程之道:理论与实践

&#x1f482; 个人网站:【 海拥】【神级代码资源网站】【办公神器】&#x1f91f; 基于Web端打造的&#xff1a;&#x1f449;轻量化工具创作平台&#x1f485; 想寻找共同学习交流的小伙伴&#xff0c;请点击【全栈技术交流群】 简介 随着互联网和信息技术的快速发展&#x…

使用Nginx进行负载均衡

什么是负载均衡 Nginx是一个高性能的开源反向代理服务器&#xff0c;也可以用作负载均衡器。通过Nginx的负载均衡功能&#xff0c;可以将流量分发到多台后端服务器上&#xff0c;实现负载均衡&#xff0c;提高系统的性能、可用性和稳定性。 如下图所示&#xff1a; Nginx负…

【JavaScript 漫游】【036】CORS 通信总结

文章简介 CORS 是一个 W3C 标准&#xff0c;全称是“跨域资源共享”&#xff08;Cross-origin resource sharing&#xff09;。它允许浏览器向跨域的服务器&#xff0c;发出 XMLHttpRequest 请求&#xff0c;从而克服了 AJAX 只能同源使用的限制。 本篇文章为【JavaScript 漫…

拼图小游戏制作教程:用HTML5和JavaScript打造经典游戏

&#x1f31f; 前言 欢迎来到我的技术小宇宙&#xff01;&#x1f30c; 这里不仅是我记录技术点滴的后花园&#xff0c;也是我分享学习心得和项目经验的乐园。&#x1f4da; 无论你是技术小白还是资深大牛&#xff0c;这里总有一些内容能触动你的好奇心。&#x1f50d; &#x…

mysql中的非空间数据导入sqlserver中空间化

以下操作都在Navicat Premium 15软件中操作 1、mysql导出数据 以导出csv为例 不修改导出路径的话默认就是在桌面 设置编码UTF-8 这边还是默认,最好不要修改,如果文本识别符号为空,导入的时候可能字段会错乱 开始即可 2、导入sqlserver数据库中

通过Maven创建Web工程

通过Maven创建Web工程 方式一方式二 方式一 1.先创建一个Maven工程 2.把该Maven模块的pom文件里添加一个war 3.选中该Maven模块 点击项目架构 4.手动添加一个Web架构 方式二 1.也是new一个模块 但是直接配置好Web 2.这里就是我IDEA对Maven的设置 3.第一次创建 可能…

第六篇【传奇开心果系列】Python的自动化办公库技术点案例示例:大学生数据全方位分析挖掘经典案例

传奇开心果博文系列 系列博文目录Python的自动化办公库技术点案例示例系列 博文目录前言一、Pandas库全方位分析挖掘大学生数据能力介绍二、大学生学生成绩数据分析数据挖掘示例代码三、大学生选课数据分析数据挖掘示例代码四、大学生活动参与数据分析数据挖掘示例代码五、大学…

我用Coze给自己的服务号加了一个多功能的GPT服务机器人

我用Coze给自己的服务号加了一个多功能的GPT服务机器人&#xff0c;可以查新闻&#xff0c;交互式回答问题&#xff0c;查快递&#xff0c;画图画&#xff0c;联网回答问题 可以查快递 试用&#xff1a;搜索觉醒AI

Excel判断CD两列在EF两列的列表中是否存在

需求 需要将CD两列的ID和NAME组合起来&#xff0c;查询EF两列的ID和NAME组合起来的列表中是否存在&#xff1f; 比如&#xff0c;判断第二行的“123456ABC”在EF的第二行到第四行中是否存在&#xff0c;若存在则显示Y&#xff0c;不存在则显示N 实现的计算公式 IF(ISNUMBER…

软考72-上午题-【面向对象技术2-UML】-UML中的图3

一、状态图 1-1、状态图的定义 状态图&#xff0c;展现了一个状态机&#xff0c;由&#xff1a;状态、转换、事件和活动组成&#xff0c;是系统的动态视图。 活动(动作) 可以在状态内执行也可以在状态转换(迁移) 时执行。 状态图强调&#xff1a;行为的事件顺序。 1-2、状态图…

4G安卓核心板T310_紫光展锐平台方案

紫光展锐T310应用 DynamlQ架构 12nm 制程工艺&#xff0c;采用 1*Cortex-A753*Cortex-A55处理器&#xff0c;搭载Android11.0操作系统&#xff0c;主频最高达2.0GHz.此外&#xff0c;DynamlQ融入了AI神经网络技术&#xff0c;新增机器学习指令&#xff0c;让其在运算方面的机器…

BigDL-LLM 安装指南——在iGPU集成显卡下使用BigDL-LLM大模型库加速LLM

文章目录 iGPU是什么&#xff1f;一、环境准备1.1 Visual Studio 2022 Community 安装1.2 安装或更新最新版本的GPU驱动程序1.3 安装英特尔oneAPI工具包2024.0版本1.4 安装Anaconda 二、BigDL -LLM 安装2.1 创建虚拟环境2.2 激活虚拟环境2.3 安装bigdl-llm[xpu] 三、运行环境配…

centos命令history设置记录10000行

今天在操作服务器的时候&#xff0c;用history查看操作记录的时候&#xff0c;发现只能查看10条&#xff0c;这样不行啊&#xff0c;我想查看所有人对服务器操作的命令。 [rootbogon ~]# history解决办法&#xff1a; #1、找到/etc/profile文件中的histsize 把10改成10000 […

Netty架构详解

文章目录 概述整体结构Netty的核心组件逻辑架构BootStrap & ServerBootStrapChannelPipelineFuture、回调和 ChannelHandler选择器、事件和 EventLoopChannelHandler的各种ChannelInitializer类图 Protocol Support 协议支持层Transport Service 传输服务层Core 核心层模块…

打卡学习kubernetes——kubernetes架构原理

接上一篇的内容&#xff0c;除了核心组件&#xff0c;还有一些推荐的Add-ons&#xff1a; kube-dns 负责为整个集群提供DNS服务Ingress Controller 为服务提供外网入口Heapster 提供资源监控&#xff08;没用过这个&#xff0c;但是用过grafana&#xff0c;很方便&#xf…

【网络安全】手机不幸被远程监控,该如何破解,如何预防?

手机如果不幸被远程监控了&#xff0c;用三招就可以轻松破解&#xff0c;再用三招可以防范于未然。 三招可破解可解除手机被远程监控 1、恢复出厂设置 这一招是手机解决软件故障和系统故障的终极大招。只要点了恢复出厂设置&#xff0c;你手机里后装的各种APP全部将灰飞烟灭…

Ae 从入门到精通之三:合成与图层

图层 Layer是构建合成的基本单位。 一个图层上可以有一个或多个画面元素&#xff0c;多个图层在时间、空间上有组织地排列&#xff0c;从而创造丰富多彩的画面效果。 Ae 中的图层类似于 Ps 中的图层或 Pr 中的轨道。 合成 Composition是放置图层的“容器”。 每个合成都对应一个…

如何使用“Docker registry创建本地仓库,在服务器之间进行文件push和pull”?

1.1、在服务器1&#xff0c;运行registry docker run -d -p 5000:5000 -v ${PWD}/registry:/var/lib/registry --restart always --name registry registry:2.7.11.2、编辑/etc/docker/daemon.json 文件&#xff0c; 192.168.xxx.xxx 换成你自己 registry 服务的地址 sudo na…

vue 自定义组件绑定model+弹出选择支持上下按键选择

参考地址v-modelhttps://v2.cn.vuejs.org/v2/guide/components-custom-events.html#%E8%87%AA%E5%AE%9A%E4%B9%89%E7%BB%84%E4%BB%B6%E7%9A%84-v-model 原文代码 Vue.component(base-checkbox, {model: {prop: checked,event: change},props: {checked: Boolean},template: `…

通过日志恢复sql server数据库

在SQL Server中&#xff0c;通过日志恢复数据库是一个精细的过程&#xff0c;主要用于在数据库出现错误、数据丢失或需要回滚到特定时间点时恢复数据。以下是一般步骤概述&#xff1a; 设置恢复模式&#xff1a; 首先&#xff0c;数据库必须配置为“完整恢复模式”或“大容量…