本文实例讲述了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),即所有记录放在同一组中进行直接插入排序为止。
代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
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程序设计有所帮助。