插入排序—希尔排序(Shell`s Sort)
希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序
基本思想:
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
操作方法:
1.选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
2.按增量序列个数k,对序列进行k 趟排序;
3.每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
希尔排序的示例:
代码实现:
在希尔排序的理解时,我们倾向于对于每一个分组,逐组进行处理,但在代码实现中,我们可以不用这么按部就班地处理完一组再调转回来处理下一组(这样还得加个for循环去处理分组)比如[5,4,3,2,1,0] ,首次增量设gap=length/2=3,则为3组[5,2] [4,1] [3,0],实现时不用循环按组处理,我们可以从第gap个元素开始,逐个跨组处理。同时,在插入数据时,可以采用元素交换法寻找最终位置,也可以采用数组元素移动法寻觅。希尔排序的代码比较简单,如下:
package sortdemo;
2
3 import java.util.Arrays;
4
5 /**
6 * Created by chengxiao on 2016/11/24.
7 */
8 public class ShellSort {
9 public static void main(String []args){
10 int []arr ={1,4,2,7,9,8,3,6};
11 sort(arr);
12 System.out.println(Arrays.toString(arr));
13 int []arr1 ={1,4,2,7,9,8,3,6};
14 sort1(arr1);
15 System.out.println(Arrays.toString(arr1));
16 }
17
18 /**
19 * 希尔排序 针对有序序列在插入时采用交换法
20 * @param arr
21 */
22 public static void sort(int []arr){
23 //增量gap,并逐步缩小增量
24 for(int gap=arr.length/2;gap>0;gap/=2){
25 //从第gap个元素,逐个对其所在组进行直接插入排序操作
26 for(int i=gap;i<arr.length;i++){
27 int j = i;
28 while(j-gap>=0 && arr[j]<arr[j-gap]){
29 //插入排序采用交换法
30 swap(arr,j,j-gap);
31 j-=gap;
32 }
33 }
34 }
35 }
36
37 /**
38 * 希尔排序 针对有序序列在插入时采用移动法。
39 * @param arr
40 */
41 public static void sort1(int []arr){
42 //增量gap,并逐步缩小增量
43 for(int gap=arr.length/2;gap>0;gap/=2){
44 //从第gap个元素,逐个对其所在组进行直接插入排序操作
45 for(int i=gap;i<arr.length;i++){
46 int j = i;
47 int temp = arr[j];
48 if(arr[j]<arr[j-gap]){
49 while(j-gap>=0 && temp<arr[j-gap]){
50 //移动法
51 arr[j] = arr[j-gap];
52 j-=gap;
53 }
54 arr[j] = temp;
55 }
56 }
57 }
58 }
59 /**
60 * 交换数组元素
61 * @param arr
62 * @param a
63 * @param b
64 */
65 public static void swap(int []arr,int a,int b){
66 arr[a] = arr[a]+arr[b];
67 arr[b] = arr[a]-arr[b];
68 arr[a] = arr[a]-arr[b];
69 }
70 }
总结:
希尔排序时效分析很难,关键码的比较次数与记录移动次数依赖于增量因子序列d的选取,特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法,有取奇数的,也有取质数的,但需要注意:增量因子中除1 外没有公因子,且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。
上一篇: 排序算法之希尔排序
下一篇: 【Java个人笔记】类