Java代码
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
|
/*希尔排序(Shell Sort)是插入排序的一种。其基本思想是:先取定一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1 * 个组,所有距离为d1的倍数的记录放在同一个组中,在各个组中进行插入排序;然后,取第二个增量d2<d1,重复上述的分组和排序, * 直至所取的增量dt=1(dt<dt-1<...<d2<d1),即所有记录放在同一组中进行直接插入排序为止。 * new int[]{8,5,1,7,9,4,6},开始分割集合的间隔长度为3的情况,[[6][3][0]比较排序后,[4]和[1]比较排序后,[5]和[2]比较排序后, * 分割集合的间隔长度为1,这时[1]和[0]比较排序后,[2][1][0]....,和直接插入排序一样了。*/ public static void shellSort( int [] intArray) { System.out.print( "将要排序的数组为: " ); for ( int k= 0 ;k<intArray.length;k++) System.out.print( " " +intArray[k]+ " " ); System.out.println(); int arrayLength=intArray.length; int j,k; //循环变量 int temp; //暂存变量 boolean isChange; //数据是否改变 int dataLength; //分割集合的间隔长度 int pointer; //进行处理的位置 dataLength=arrayLength/ 2 ; //初始集合间隔长度 while (dataLength!= 0 ){ //数列仍可进行分割 //对各个集合进行处理 for (j=dataLength;j<arrayLength;j++){ isChange= false ; temp=intArray[j]; //暂存,待交换值时用 pointer=j-dataLength; //计算进行处理的位置 //进行集合内数值的比较与交换值 while (temp<intArray[pointer]&&pointer>= 0 &&pointer<arrayLength){ intArray[pointer+dataLength]=intArray[pointer]; //计算下一个欲进行处理的位置 pointer=pointer-dataLength; isChange= true ; System.out.print( "every changing result: " ); for (k= 0 ;k<arrayLength;k++) System.out.print( " " +intArray[k]+ " " ); System.out.println(); if (pointer< 0 ||pointer>arrayLength) break ; } //与最后的数值交换 intArray[pointer+dataLength]=temp; if (isChange){ System.out.print( "Current sorting result: " ); for (k= 0 ;k<arrayLength;k++) System.out.print( " " +intArray[k]+ " " ); System.out.println(); } } System.out.print( "指定分割集合的间隔长度为" +dataLength+ ",对各个集合进行处理后,Current sorting result: " ); for (k= 0 ;k<arrayLength;k++) System.out.print( " " +intArray[k]+ " " ); System.out.println(); dataLength=dataLength/ 2 ; //计算下次分割的间隔长度 } } |
运行后的结果为:
Java代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
将要排序的数组为: 8 5 1 7 9 4 6 every changing result: 8 5 1 8 9 4 6 Current sorting result: 7 5 1 8 9 4 6 every changing result: 7 5 1 8 9 4 8 every changing result: 7 5 1 7 9 4 8 Current sorting result: 6 5 1 7 9 4 8 指定分割集合的间隔长度为 3 ,对各个集合进行处理后,Current sorting result: 6 5 1 7 9 4 8 every changing result: 6 6 1 7 9 4 8 Current sorting result: 5 6 1 7 9 4 8 every changing result: 5 6 6 7 9 4 8 every changing result: 5 5 6 7 9 4 8 Current sorting result: 1 5 6 7 9 4 8 every changing result: 1 5 6 7 9 9 8 every changing result: 1 5 6 7 7 9 8 every changing result: 1 5 6 6 7 9 8 every changing result: 1 5 5 6 7 9 8 Current sorting result: 1 4 5 6 7 9 8 every changing result: 1 4 5 6 7 9 9 Current sorting result: 1 4 5 6 7 8 9 指定分割集合的间隔长度为 1 ,对各个集合进行处理后,Current sorting result: 1 4 5 6 7 8 9 |
当分割的间隔为1时,变成了直接插入排序。
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!