希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数gap,把待排序文件中所有数据分成几个组,所有距离为gap的数据分在同一组内,并对每一组内的数据进行排序。然后gap减减,重复上述分组和排序的工作。当到达gap=1时,所有数据在同一组内排好序(gap==1时就是上次讲的插入排序)。

希尔排序举例:

#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{assert(arr);for (int i = 0;i < n;i++){printf("%d ", arr[i]);}printf("\n");
}
// 希尔排序
// 时间复杂度 O(N^1.3-N^2)
// gap越大,前面大的数据可以越快排到后面,后面小的数可以越快拍到前面,gap越大,越不接近有序
// gap越小越接近有序,如果gap==1其实就是直接插入排序,就有序了
void ShellSort(int* arr, int n)
{assert(arr);int gap = n;// gap>1相当于预排序,让数组接近有序// gap==1就相当于直接插入排序,保证有序while (gap > 1){gap = gap / 3 + 1; // +1是保证了最后一次gap一定是1// 注意结束条件,防止造成越界访问(画图)for (int i = 0;i < n - gap;i++)  // 多趟并排{// 单趟排序int end = i;               // 当end==0时就是单趟排序,排间距为gap的那一趟int temp = arr[end + gap];  // 将新的排序数值存起来,方便每次比较大小while (end >= 0)   {if (temp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = temp;  // 跳出循环后temp放到end+gap位置}// 打印每一个gap时的排序状态Printarry(arr, n);}}void TestShellSort() 
{int arr[] = { 3,1,4,2,8,4,9,6,0,7 };Printarry(arr, sizeof(arr) / sizeof(arr[0]));ShellSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}int main()
{TestShellSort();return 0;
}

选择排序

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置(末尾位置),直到全部待排序的 数据元素排完 。

直接选择排序:

在元素集合arr[i]--arr[n-1]中选择最大(小)的数据 若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换 在剩余的array[i]--array[n-2](array[i+1]--array[n-1])集合中,重复上述步骤,直到集合剩余1个元素。

举例:利用双指方法,begin指向首元素,end指向末尾元素,找到最大值时maxi和end位置数据互换,最小值mini位置和begin位置数据互换。

当begin和maxi重叠时,mini位置的数据和begin位置的数据互换后要将mini的值给到maxi,在将maxi位置的数据和end位置的数据互换。

#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{assert(arr);for (int i = 0;i < n;i++){printf("%d ", arr[i]);}printf("\n");
}
// 选择排序
// 空间复杂度为O(1)
// 时间复杂度为 O(N^2),最好的情况是接近有序比较n次即可,最坏的是不完全有序接近无顺序
void SelectSort(int* arr, int n)
{assert(arr);int begin = 0;int end = n - 1;//int mini = 0;//int maxi = 0;while (begin < end){int mini = 0;int maxi = 0;maxi = mini = begin;// 在[begin,end]之间选出最大值和最小值for (int i = begin + 1;i <= end;++i){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}Swap(&arr[begin], &arr[mini]);// 如果maxi与begin位置重叠的话要修正maxi的位置if (begin == maxi)maxi = mini;Swap(&arr[end], &arr[maxi]);--end;++begin;}
}void TestSelectSort()
{int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };SelectSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}
int main()
{TestShellSort();return 0;
}

计数排序

首先找到待排序数组的最大值和最小值,然后开辟一个空间temp数组,大小为最大值减去最小值加1;然后遍历数组,将数据出现的次数放到temp数组相对位置中;然后再遍历temp数组取出对应数据出现的次数,将该数据依次覆盖回原数组中。

注意:这个排序缺点就是浪费空间比如,待排序数组最小值为100,最大值为1000;那么要开辟0-1000个空间的数组,才能存放比如100出现10次,那么temp数组中下标100位置就存放10,这样就很浪费空间。我们在这里开辟900个空间的数组,将100出现的次数放到相对位置中,相对位置为:100-min。覆盖回原数组的时候再加上min即可。相对减少空间浪费。

举例子:

#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{assert(arr);for (int i = 0;i < n;i++){printf("%d ", arr[i]);}printf("\n");
}
// 计数排序
// 时间复杂度O(N+range)
// 空间复杂度O(range)
void CountSort(int* arr, int n)
{// 找出最大最小值int min = arr[0];int max = arr[0];for (int i = 1;i < n;i++){if (arr[i] > max)max = arr[i];if (arr[i] < min)min = arr[i];}// 创建计数的空间int range = max - min + 1;int* countArr = (int*)malloc(sizeof(int) * range);memset(countArr, 0, sizeof(int) * range); // 将数组元素置为0// 遍历数组将相同的数值出现的次数放到相对位置处:arr[i] - minfor (int i = 0;i < n;i++){countArr[arr[i] - min]++;}// 遍历countArr数组将某个数出现的次数,依次将这个数放回到原数组int index = 0;for (int i = 0;i < range;i++){while (countArr[i]--)  // 控制数据出现的次数{arr[index++] = i + min;}}
}void TestCountSort()
{int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };CountSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}
int main()
{TestCountSort();return 0;
}

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

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

相关文章

Solid Edge多项目并行,浮动许可如何高效调度?

在制造企业的数字化设计体系中&#xff0c;Solid Edge 作为主流 CAD 工具&#xff0c;因其灵活的建模能力、同步技术和强大的装配设计功能&#xff0c;广泛应用于机械设备、零部件制造等行业的研发场景。随着企业设计任务复杂化&#xff0c;多项目并行成为常态&#xff0c;Soli…

Flink cdc 使用总结

Flink 与 Flink CDC 版本兼容对照表Flink 版本支持的 Flink CDC 版本关键说明Flink 1.11.xFlink CDC 1.2.x早期版本&#xff0c;需注意 Flink 1.11.0 的 Bug&#xff08;如 Upsert 写入问题&#xff09;&#xff0c;建议使用 1.11.1 及以上。Flink 1.12.xFlink CDC 2.0.x&#…

企业培训笔记:axios 发送 ajax 请求

文章目录axios 简介一&#xff0c;Vue工程中安装axios二&#xff0c;编写app.vue三&#xff0c;编写HomeView.vue四&#xff0c;Idea打开后台项目五&#xff0c;创建HelloController六&#xff0c;配置web访问端口七&#xff0c;运行项目&#xff0c;查看效果&#xff08;一&am…

Maven下载与配置对Java项目的理解

目录 一、背景 二、JAVA项目与Maven的关系 2.1标准java项目 2.2 maven 2.2.1 下载maven 1、下载 2、配置环境 2.2.2 setting.xml 1、配置settings.xml 2、IDEA配置maven 一、背景 在java项目中&#xff0c;新手小白很有可能看不懂整体的目录结构&#xff0c;以及每个…

Mars3d的走廊只能在一个平面的无法折叠的解决方案

问题场景&#xff1a;1. Mars3d的CorridorEntity只能在一个平面修改高度值&#xff0c;无法根据坐标点位制作有高度值的走廊效果&#xff0c;想要做大蜀山盘山走廊的效果实现不了。解决方案&#xff1a;1.使用原生cesium实现对应的走廊的截面形状、走廊的坐标点&#xff0c;包括…

LeetCode 每日一题 2025/7/7-2025/7/13

记录了初步解题思路 以及本地实现代码&#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录7/7 1353. 最多可以参加的会议数目7/8 1751. 最多可以参加的会议数目 II7/9 3439. 重新安排会议得到最多空余时间 I7/10 3440. 重新安排会议得到最多空余时间 II7/11 3169. …

Bash常见条件语句和循环语句

以下是 Bash 中常用的条件语句和循环语句分类及语法说明&#xff0c;附带典型用例&#xff1a;一、条件语句 1. if 语句 作用&#xff1a;根据条件执行不同代码块 语法&#xff1a; if [ 条件 ]; then# 条件为真时执行 elif [ 其他条件 ]; then# 其他条件为真时执行 else# 所有…

uni-app 选择国家区号

uni-app选择国家区号组件 hy-countryPicker 我们在做登录注册功能的时候&#xff0c;可能会遇到选择区号来使用不同国家手机号来登录或者注册的功能。这里我就介绍下我这个uni-app中使用的选择区号的组件&#xff0c;包含不同国家国旗图标。 效果图 别的不说&#xff0c;先来…

客户端主机宕机,服务端如何处理 TCP 连接?详解

文章目录一、客户端主机宕机后迅速重启1、服务端有数据发送2、服务端开启「保活」机制3、服务端既没有数据发送&#xff0c;也没有开启「保活」机制二、客户端主机宕机后一直没有重启1、服务端有数据发送2、服务端开启「保活」机制3、服务端既没有数据发送&#xff0c;也没有开…

《大数据技术原理与应用》实验报告五 熟悉 Hive 的基本操作

目 录 一、实验目的 二、实验环境 三、数据集 四、实验内容与完成情况 4.1 创建一个内部表 stocks&#xff0c;字段分隔符为英文逗号&#xff0c;表结构下所示。 4.2 创建一个外部分区表 dividends&#xff08;分区字段为 exchange 和symbol&#xff09;&#xff0c;字段…

【橘子分布式】Thrift RPC(编程篇)

一、简介 之前我们研究了一下thrift的一些知识&#xff0c;我们知道他是一个rpc框架&#xff0c;他作为rpc自然是提供了客户端到服务端的访问以及两端数据传输的消息序列化&#xff0c;消息的协议解析和传输&#xff0c;所以我们今天就来了解一下他是如何实现这些功能&#xff…

清理C盘--办法

c盘经常爆红1、命令行2、属性3、临时文件

Java-71 深入浅出 RPC Dubbo 上手 父工程配置编写 附详细POM与代码

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; AI炼丹日志-29 - 字节跳动 DeerFlow 深度研究框斜体样式架 私有…

创客匠人:创始人 IP 打造的内核,藏在有效的精神成长里

当创始人 IP 成为企业增长的重要引擎&#xff0c;许多人急于寻找 “爆款公式”&#xff0c;却忽略了一个更本质的问题&#xff1a;IP 的生命力&#xff0c;终究源于创始人的精神成长。创客匠人在深耕知识付费赛道的过程中&#xff0c;见证了无数案例&#xff1a;那些能持续实现…

GPT和MBR分区

GPT&#xff08;GUID分区表&#xff09;和MBR&#xff08;主引导记录&#xff09;是两种不同的磁盘分区表格式&#xff0c;用于定义硬盘上分区的布局、位置及启动信息&#xff0c;二者在设计、功能和适用场景上有显著差异。以下从多个维度详细对比&#xff1a; 一、核心定义与起…

c#进阶之数据结构(字符串篇)----String

1、String介绍首先我们得明白&#xff0c;string和String代表的实际上是同一个类型&#xff0c;string是C#中的关键字&#xff0c;代表String类型&#xff0c;因此我们直接来学习String类型。从官方的底层实现代码可以看出&#xff0c;当前String类型实际上就是一个Char类型的聚…

快速排序递归和非递归方法的简单介绍

基本思想为&#xff1a;任取待排序元素序列中 的某元素作为基准值&#xff0c;按照该排序码将待排序集合分割成两子序列&#xff0c;左子序列中所有元素均小于基准值&#xff0c;右 子序列中所有元素均大于基准值&#xff0c;然后最左右子序列重复该过程&#xff0c;直到所有元…

从零开始的云计算生活——第三十二天,四面楚歌,HAProxy负载均衡

目录 一.HAProxy简介 二.HAProxy特点和优点&#xff1a; 三.HAProxy保持会话的三种解决方法 四.HAProxy的balance 8种负载均衡算法 1&#xff09;RR&#xff08;Round Robin&#xff09; 2&#xff09;LC&#xff08;Least Connections&#xff09; 3&#xff09;SH&am…

策略模式及优化

策略模式&#xff08;Strategy Pattern&#xff09;是一种行为设计模式&#xff0c;其核心思想是将算法的定义与使用分离&#xff0c;使算法可以独立于客户端进行变化。它通过定义一系列算法&#xff0c;将每个算法封装到独立的类中&#xff0c;并使它们可以互相替换&#xff0…

微信小程序开发-桌面端和移动端UI表现不一致问题记录

桌面端和移动端UI表现不一致零、引擎说明一、样式不同1、text 单行&#xff1a;1.1 空格开发者工具不展示&#xff0c;手机/PC端正常1.2 正常展示省略号&#xff0c;需要2、点击按钮z-index: -1。webview - 桌面端不行&#xff0c; skyline - 移动端可以&#xff1b;3、其他说明…