本文实例讲述了java排序算法总结之希尔排序。分享给大家供大家参考。具体分析如下：
前言：希尔排序(shell sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因dl．shell于1959年提出而得名。本文主要介绍希尔排序用java是怎样实现的。
希尔排序(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。希尔排序并不稳定，o(1)的额外空间，时间复杂度为o(n*(logn)^2)。最坏的情况下的执行效率和在平均情况下的执行效率相比相差不多。
基本思想：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
代码实现：
我要评论
public class test {
public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 };
// 预设数据数组
public static void main(string args[]) {
int i; // 循环计数变量
int index = 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("");
}
public static void shellsort(int index) {
int i, j, k; // 循环计数变量
int temp; // 暂存变量
boolean change; // 数据是否改变
int datalength; // 分割集合的间隔长度
int pointer; // 进行处理的位置
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程序设计有所帮助。
如对本文有疑问， 点击进行留言回复！！
网友评论