排序算法之希尔排序及Java实现
程序员文章站
2024-02-23 10:00:04
...
一、排序算法的分类
二、希尔排序的原理
希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。它的主要思想是将整个序列分成多个子序列,之后依次对每个子序列进行直接插入排序,经过多次不同的子序列分割并排序后,整个数组基本有序,之后对数组中的所有元素进行一次直接插入排序。对于倒序的数组,如果采用直接插入排序的话,需要多次移动和插入操作,而采用希尔排序会大大减少移动的次数,加快了处理速度。
三、希尔排序的实现
希尔排序的步长可以自己定义,也可以采用每次折半的方法,比如一共有12个数据,第一次步长为6进行第一轮排序,第二次步长为3进行第二轮排序,第三次步长为1进行最后一轮排序。每一次的排序都是直接排序算法。
public class ShellSort {
public static void sheSort(int[] a){
//开始时步长增量为长度的一半,之后依次减半,直到步长为1时跳出while循环
// 12 3 6 9 23 5 8 10 34 81 37 39
//第一轮
// 12 3 6 9 23 5 8 10 34 81 37 39
// 8 3 6 9 23 5 12 10 34 81 37 39
//第二轮
// 8 3 6 9 23 5 12 10 34 81 37 39
// 8 3 5 9 10 6 12 23 34 81 37 39
//第三轮
// 3 5 6 8 9 10 12 23 34 37 39 81
for(int incremt=a.length/2;incremt>0;incremt=incremt/2){
System.out.println("incremt: " + incremt);
//直接插入排序
for(int i=incremt;i<a.length;i++)
{
int tmp = a[i];
int j = 0;
for(j=i-incremt; j>=0&&tmp<a[j]; j-=incremt){
a[j+incremt] = a[j];
}
a[j + incremt] = tmp;
}
for(int k=0; k<a.length; k++){
System.out.print(a[k] + " ");
}
System.out.println();
}
}
public static void main(String args[]){
int[] test = {12,3,6,9,23,5,8,10,34,81,37,39};
sheSort(test);
System.out.println("测试结果");
for(int i=0; i<test.length; i++){
System.out.print(test[i] + " ");
}
}
}
测试结果
incremt: 6
8 3 6 9 23 5 12 10 34 81 37 39
incremt: 3
8 3 5 9 10 6 12 23 34 81 37 39
incremt: 1
3 5 6 8 9 10 12 23 34 37 39 81
测试结果
3 5 6 8 9 10 12 23 34 37 39 81
上一篇: ejb3 定时器开发