希尔排序的一些小知识
程序员文章站
2024-02-26 09:39:40
...
希尔排序
一种间隔排序算法,大致就是从粗间隔到细间隔的排序过程
思路:
- 先看下面几幅图
- 都是有个细线的间隔,从粗到细为1的间隔
起始的h间隔(最粗间隔)
while(h<a.length/2) {
h=2*h+1;//3,,7
}
控制着间隔排序,每个间隔上划分为组来排序
for (int j = i; j >=h; j-=h) {
//待插入的元素是a[j],比较a[j]和a[j-h]
if(greater(a[j-h],a[j])) {
循环结束h=h/2;控制间隔的减小
代码
- 工具类两个一个排序一个交换数组
import java.util.Arrays;
public class Shell {
/*对数组a中的元素进行排序
* */
public static void sort(Comparable[] a) {
//1.根据数组a的长度确定增长量
int h=1;
while(h<a.length/2) {
h=2*h+1;//3,,7
}
//2.希尔排序
while(h>=1) {
//继续排序
//2.1.找到待插入的元素
for (int i = h; i < a.length; i++) {
//2.2把待插入的元素插入到有序数列中
for (int j = i; j >=h; j-=h) {
//待插入的元素是a[j],比较a[j]和a[j-h]
if(greater(a[j-h],a[j])) {
//交换元素
exch(a, j-h, j);
}else {
break;
}
}
}
//减小h的值
h=h/2;
}
}
// 比较a元素是否大于b元素
private static boolean greater(Comparable a,Comparable b) {
return a.compareTo(b)>0;
}
//数组元素i和j交换位置
private static void exch(Comparable[] a,int i,int j) {
Comparable temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
总结:
- 他是由划分组来排序,先排宏观上的,然后到最后细微每个相比较
- 而且最小间隔的时候排序会发现好多已经排好了,节约了大量时间
- 比插入排序效率提升了非常多