006-排序算法-希尔排序
2023-09-14 09:08:46 时间
一、概述
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
排序方法 | 时间复杂度(平均) | 时间复杂度 (最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 使用场景 |
---|---|---|---|---|---|---|
希尔排序 | O(N*(logN)2) | O(n2) | O(nlogn) | O(n) | 不稳定 | 中等数据规模 |
1.1、算法说明
首先它把较大的数据集合分割成若干个小组(逻辑上分组),然后对每一个小组分别进行插入排序,此时,插入排序所作用的数据量比较小(每一个小组),插入的效率比较高
可以看出,他是按下标相隔距离为4分的组,也就是说把下标相差4的分到一组,比如这个例子中a[0]与a[4]是一组、a[1]与a[5]是一组...,这里的差值(距离)被称为增量
每个分组进行插入排序后,各个分组就变成了有序的了(整体不一定有序)
此时,整个数组变的部分有序了(有序程度可能不是很高)
然后缩小增量为上个增量的一半:2,继续划分分组,此时,每个分组元素个数多了,但是,数组变的部分有序了,插入排序效率同样比高
同理对每个分组进行排序(插入排序),使其每个分组各自有序
最后设置增量为上一个增量的一半:1,则整个数组被分为一组,此时,整个数组已经接近有序了,插入排序效率高
1.2、代码实现
public static void shellSort(int[] a) { //希尔排序 int d = a.length; while (true) { d = d / 2; for (int x = 0; x < d; x++) { for (int i = x + d; i < a.length; i = i + d) { int temp = a[i]; int j; for (j = i - d; j >= 0 && a[j] > temp; j = j - d) { a[j + d] = a[j]; } a[j + d] = temp; } } if (d == 1) { break; } } }
代码地址:地址 中的algorithm-001-sort中 ShellSort
参看地址:https://blog.csdn.net/qq_39207948/article/details/80006224
https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F/3229428?fr=aladdin
相关文章
- 【排序算法】插入排序
- 统计一个二进制字符串中1的个数的算法
- 梳排序算法
- 选择排序算法
- Java实现 蓝桥杯 算法提高 成绩排序2
- Java实现 蓝桥杯 算法提高 成绩排序2
- Java实现 蓝桥杯 算法提高 道路和航路
- Java实现 蓝桥杯VIP 算法提高 棋盘多项式
- Java实现 蓝桥杯VIP 算法提高 身份证排序
- Java实现 蓝桥杯VIP 算法训练 学做菜
- Java实现 蓝桥杯VIP 算法训练 阶乘末尾
- Python排序搜索基本算法之归并排序实例分析
- (算法)堆与堆排序
- 程序员的算法趣题Q21--异或杨辉三角形
- 归并排序算法
- 各种Java实现的常用排序算法
- 排序算法 - 冒泡排序
- DL之RNN:人工智能为你写诗——基于TF利用RNN算法实现【机器为你写诗】、训练&测试过程全记录
- Java实现7种常见密码算法
- 智能优化算法应用:基于GWO优化的最小交叉熵图像多阈值分割 - 附代码
- 智能优化算法:供需优化算法-附代码
- 具有自适应边界与最优引导的莱维飞行蚁狮优化算法-附代码
- 【华为OD机试Python实现】HJ67 24点游戏算法(中等)
- 程序员小灰-算法集锦 漫画算法
- soft-NMS算法理解
- 三白话经典算法系列 Shell排序实现
- Defense-GAN——防御对抗样本,本质上就是在用类似编码解码器(论文用了GAN)来进行表征学习,使得算法模型更健壮
- shingling算法——提取特征,m个hash函数做指纹计算,针对特征hash后变成m维向量,最后利用union-find算法计算相似性
- Java中的六种经典比较排序算法:代码实现全解析
- 数据结构和算法 十七、排序算法
- 数据结构和算法 回文算法
- 八大排序算法