Java排序算法总结之希尔排序
本文实例讲述了Java排序算法总结之希尔排序。分享给大家供大家参考。具体分析如下：
前言：希尔排序(ShellSort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。本文主要介绍希尔排序用Java是怎样实现的。
希尔排序(缩小增量法)属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。希尔排序并不稳定，O(1)的额外空间，时间复杂度为O(N*(logN)^2)。最坏的情况下的执行效率和在平均情况下的执行效率相比相差不多。
基本思想：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
代码实现：
publicclassTest{
publicstaticint[]a={10,32,1,9,5,7,12,0,4,3};
//预设数据数组
publicstaticvoidmain(Stringargs[]){
inti;//循环计数变量
intIndex=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("");
}
publicstaticvoidShellSort(intIndex){
inti,j,k;//循环计数变量
intTemp;//暂存变量
booleanChange;//数据是否改变
intDataLength;//分割集合的间隔长度
intPointer;//进行处理的位置
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程序设计有所帮助。