希尔排序
*尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。
*排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后取d2<d1,
*重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止。
*
*希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,
*速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。
*所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,
*不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,
*最后其稳定性就会被打乱,所以shell排序是不稳定的。
package com.algorithm; /** * 希尔排序 * @author lenovo *尔排序属于插入类排序,是将整个有序序列分割成若干小的子序列分别进行插入排序。 *排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后取d2<d1, *重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止。 * *希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少, *速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。 *所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的, *不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动, *最后其稳定性就会被打乱,所以shell排序是不稳定的。 */ public class ShellSort { /** * 排序方法 */ public static void sort(long[] attr){ //初始化一个间隔 int h=1; //计算最大间隔 while (h<attr.length/3) { h=h*3+1; } while(h>0){ //进行插入排序 long temp=0; for (int i = h; i < attr.length; i++) { temp =attr[i]; int j=i; while (j>h-1&&attr[j-h]>=temp) { attr[j]=attr[j-h]; j =j-h; } attr[j]=temp; } //减小间隔 h=(h-1)/3; } } public static void main(String[] args) { long[] attr = new long[5]; attr[0]=34; attr[1]=23; attr[2]=2; attr[3]=55; attr[4]=1; System.out.print("{"); for (int i = 0; i < attr.length; i++) { System.out.print(attr[i]+" "); } System.out.println("}\n"); sort(attr); System.out.print("{"); for (int i = 0; i < attr.length; i++) { System.out.print(attr[i]+" "); } System.out.println("}\n"); } }
相关推荐
希尔排序也是一种插入排序方法,实际上是一种分组插入方法。
希尔排序
问题:现有一段程序S,可以对任意n个数进行排序。如果现在需要对n^2个数进行排序,最少需要调用S多少次?只允许调用S,不可以做别的操作。我们用希尔排序来做解决这个
希尔排序
主要为大家详细介绍了Java经典排序算法之希尔排序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组,...
本文实例为大家分享了C++实现希尔排序的具体代码,供大家参考,具体内容如下 一、思路: 希尔排序:又称缩小增量排序,是一种改进的插入排序算法,是不稳定的。 设排序元素序列有n个元素,首先取一个整数gap using ...
按下标的一定增量分组,对每组使用直接插入算法排序;随着增量 * 逐渐减少,每组包含的关键字越来越多,当增量减至1时,整个文件恰 * 好被分成一组,算法便终止。 * 8,9,1,7,2,3,5,4,6,0 * //初始增量 gap=...
希尔排序PPT讲解资料和一些其他的区域赛题目的相关资料,供大家下载研究