概念
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
基本思想
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
算法稳定性
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
java代码实现
package com.wepayweb.weixin.util.paixu;
/***
*
* @author www.vxzsk.com V型知识库
*
*/
public class Shellsort {
final int MAX=20;
int num[]=new int[MAX];
{
System.out.print("排序前生成的随机数组是：");
for(int i=0;i<20;i++){
num[i]=(int)(Math.random()*100);
System.out.print(num[i]+" ");
}
System.out.println();
}
/*--------------------------shell（希尔）排序法----------------------------
Shell首先将间隔设定为n/2，然后跳跃进行插入排序，再来将间隔n/4，跳跃进行排序动作，再来
间隔设定为n/8、n/16，直到间隔为1之后的最后一次排序终止，由于上一次的排序动作都会将
固定间隔内的元素排序好，所以当间隔越来越小时，某些元素位于正确位置的机率越高，因此
最后几次的排序动作将可以大幅减低。
---------------------------------------------------------------------*/
public void shellsort(int number[]) {
int i, j, k, gap, temp;
long start,end;
start=System.nanoTime();
gap = MAX / 2;
while(gap > 0) {
for(k = 0; k < gap; k++) {
for(i = k+gap; i < MAX; i+=gap) {
for(j = i - gap; j >= k; j-=gap) {
if(number[j] > number[j+gap]) {
temp=number[j];
number[j]=number[j+gap];
number[j+gap]=temp;
}else{
break;
}
}
}
}
gap /= 2;
}
end=System.nanoTime();
System.out.println("-----------------shell(希尔)排序法（改进的插入排序法）------------------");
System.out.print("排序后是:");
for(i=0;i<=MAX-1;i++){
System.out.print(number[i]+" ");
}
System.out.println();
System.out.println("排序使用时间："+(end-start)+" ns");
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Shellsort s = new Shellsort();
s.shellsort(s.num.clone()); //希尔排序
}
}执行main方法即可观察效果
此文章本站原创，地址 https://www.vxzsk.com/770.html
转载请注明出处！谢谢！
感觉本站内容不错，读后有收获？小额赞助,鼓励网站分享出更好的教程