首页 / 算法 / 排序算法之插入排序-希尔排序
排序算法之插入排序-希尔排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法之插入排序-希尔排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1632字,纯文字阅读大概需要3分钟。
内容图文
![排序算法之插入排序-希尔排序](/upload/InfoBanner/zyjiaocheng/593/9c29233642e34c8e9bd0b5860360f8ed.jpg)
希尔排序(Shell Sort)
1959年Shell发明,第一个突破O(n2)的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
直接插入排序有个缺点:当有个很小的数字在后面时,排序的效果很低。
此时使用希尔排序来解决这个问题:
希尔排序的原理:
数组元素 2,5,3,7,1,8,3,9,0
1、数组共9个元素,先除以2,商为4,4表示步长。
2、每一个元素和步长为4的元素组成一组来进行排序
2 1 0 为一组
5 8 一组
3 3 一组
7 9 一组
对每一组进行直接插入排序之后 数组元素顺序为
0,5,3,7,1,8,3,9,2
3、在对步长4除以2 ,取得新的步长2
每一个元素和步长为2的元素组成一组来进行排序
0 3 1 3 2 一组
5 7 8 9 一组
对每一组进行排序之后 数组元素顺序为 0 5 1 7 2 8 3 9 3
3、在对步长2除以2 ,取得新的步长1
当步长为1 时,如上
直到步长为0
图片来自网络,侵删
public class ShellSort {
public static void main(String[] args) {
int[] arr = {2,5,3,7,1,8,3,9,0};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void shellSort(int[] arr) {
System.out.println(Arrays.toString(arr));
int k=1;
//循环到步长为0时结束循环
for(int d=arr.length/2;d>0;d/=2)
{
//双重循环取得所有元素,循环步长到length次
for(int i=d;i<arr.length;i++)
{//j=i-d为最左边的元素,j=j-d判断本组是否还有其他元素
for(int j = i-d;j>=0;j-=d)//i=8时j=4,中间元素和最右元素进行比较,完成之后j-=d,j=0,最左元素和中间元素比较
{
if(arr[j]>arr[j+d])
{
int temp =arr[j];
arr[j]=arr[j+d];
arr[j+d]=temp;
}
}
}
System.out.println("第"+k+"次排序的结果"+Arrays.toString(arr));
k++;
}
}
}
[2, 5, 3, 7, 1, 8, 3, 9, 0]
第1次排序的结果[0, 5, 3, 7, 1, 8, 3, 9, 2]
第2次排序的结果[0, 5, 1, 7, 2, 8, 3, 9, 3]
第3次排序的结果[0, 1, 2, 3, 3, 5, 7, 8, 9]
[0, 1, 2, 3, 3, 5, 7, 8, 9]
内容总结
以上是互联网集市为您收集整理的排序算法之插入排序-希尔排序全部内容,希望文章能够帮你解决排序算法之插入排序-希尔排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。