Java排序算法总结之希尔排序
作者:一羽清宁 时间:2022-07-16 13:19:11
本文实例讲述了Java排序算法总结之希尔排序。分享给大家供大家参考。具体分析如下:
前言:希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。本文主要介绍希尔排序用Java是怎样实现的。
希尔排序(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。希尔排序并不稳定,O(1)的额外空间,时间复杂度为O(N*(logN)^2)。最坏的情况下的执行效率和在平均情况下的执行效率相比相差不多。
基本思想:
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
代码实现:
public class Test {
public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 };
// 预设数据数组
public static void main(String args[]) {
int i; // 循环计数变量
int Index = a.length;// 数据索引变量
System.out.print("排序前: ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a);
System.out.println("");
ShellSort(Index - 1); // 选择排序
// 排序后结果
System.out.print("排序后: ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a);
System.out.println("");
}
public static void ShellSort(int Index) {
int i, j, k; // 循环计数变量
int Temp; // 暂存变量
boolean Change; // 数据是否改变
int DataLength; // 分割集合的间隔长度
int Pointer; // 进行处理的位置
DataLength = (int) Index / 2; // 初始集合间隔长度
while (DataLength != 0) // 数列仍可进行分割
{
// 对各个集合进行处理
for (j = DataLength; j < Index; j++) {
Change = false;
Temp = a[j]; // 暂存Data[j]的值,待交换值时用
Pointer = j - DataLength; // 计算进行处理的位置
// 进行集合内数值的比较与交换值
while(Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index){
a[Pointer + DataLength] = a[Pointer];
// 计算下一个欲进行处理的位置
Pointer = Pointer - DataLength;
Change = true;
if (Pointer < 0 || Pointer > Index)
break;
}
// 与最后的数值交换
a[Pointer + DataLength] = Temp;
if (Change) {
// 打印目前排序结果
System.out.print("排序中: ");
for (k = 0; k < Index; k++)
System.out.printf("%3s ", a[k]);
System.out.println("");
}
}
DataLength = DataLength / 2; // 计算下次分割的间隔长度
}
}
}
希尔排序几乎没有最坏情况,无论是正序、逆序、乱序,所用时间都不是很多,附加储存是O(1),的确非常不错。在没搞清楚快速排序、堆排序之前,它的确是个很好的选择。希望能给你带来帮助。
希望本文所述对大家的java程序设计有所帮助。
标签:Java,希尔排序
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Java Comparable及Comparator接口区别详解
2023-07-03 08:19:50
![](https://img.aspxhome.com/file/2023/5/57425_0s.png)
基于Java利用static实现单例模式
2021-12-20 06:07:32
深入分析Java内存区域的使用详解
2023-09-25 23:21:29
Java创建线程的七种方法总结(全网最全面)
2023-11-03 14:27:26
![](https://img.aspxhome.com/file/2023/8/58698_0s.png)
Java一个简单的红包生成算法
2023-12-12 10:56:50
java中的Arrays这个工具类你真的会用吗(一文秒懂)
2021-11-28 06:25:11
java生成图片验证码功能
2023-06-27 00:31:55
![](https://img.aspxhome.com/file/2023/4/60994_0s.png)
C++ Cmake的构建静态库和动态库详解
2023-06-28 08:28:15
![](https://img.aspxhome.com/file/2023/7/68777_0s.png)
Java中用enum结合testng实现数据驱动的方法示例
2021-08-04 07:44:21
![](https://img.aspxhome.com/file/2023/9/65179_0s.png)
Android开发之android_gps定位服务简单实现
2023-07-31 20:02:25
![](https://img.aspxhome.com/file/2023/3/83553_0s.gif)
java中初始化MediaRecorder的实现方法
2023-11-29 03:54:52
springMVC自定义注解,用AOP来实现日志记录的方法
2023-11-29 13:58:53
Java在web页面上的编码解码处理及中文URL乱码解决
2023-08-25 11:10:19
![](https://img.aspxhome.com/file/2023/6/58206_0s.gif)
Java实现图片拼接
2023-02-28 23:01:27
Java动态 代理和AOP应用示例
2023-11-26 07:45:02
![](https://img.aspxhome.com/file/2023/0/60270_0s.png)
java中的HashMap多层嵌套
2023-11-27 07:34:52
![](https://img.aspxhome.com/file/2023/4/60344_0s.jpg)
Java ConcurrentHashMap的源码分析详解
2023-05-02 02:16:21
![](https://img.aspxhome.com/file/2023/1/62121_0s.png)
SpringBoot 创建web项目并部署到外部Tomcat
2023-09-15 18:25:04
Spring-boot 2.3.x源码基于Gradle编译过程详解
2022-04-07 15:41:36
![](https://img.aspxhome.com/file/2023/2/66032_0s.png)
java实现倒序读取文件功能示例分享
2023-07-12 09:23:54