欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java排序算法 希尔排序

程序员文章站 2024-02-23 08:01:22
...

希尔排序(ShellSort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。本文主要介绍希尔排序用Java是怎样实现的。

AD:

希尔排序(缩小增量法)属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。希尔排序并不稳定,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];  
// 计算下一个欲进行处理的位置  
PointerPointer = 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("");  
}   
}  
DataLengthDataLength = DataLength / 2; // 计算下次分割的间隔长度  
}  
}   
} 


希尔排序几乎没有最坏情况,无论是正序、逆序、乱序,所用时间都不是很多,附加储存是O(1),的确非常不错。在没搞清楚快速排序、堆排序之前,它的确是个很好的选择。希望能给你带来帮助。


转载于:https://www.cnblogs.com/xiaowangba/archive/2012/08/02/6314531.html