直接插入排序与希尔排序——Java语言描述

发表于 | 分类于 | 阅读次数

之前有被问到有没有想过用Java描述排序算法，很不好意思的回答了没有。因为学数据结构时用的是C。刚好最近在复习，就准备试着用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
54
55
56
57
58
59
import java.util.Arrays;

/*
 * 插入排序：直接插入排序，希尔排序
 * 
 * */

public class StraightInsertion {
	/*
	 * 直接插入排序：每趟将一条待排序的记录，按其关键字值的大小插入到前面的记录序列中的合适位置，直到全部插入完成为止。
	 * 时间复杂度为O(n^2)
	 * 空间复杂度为O(1)
	 * 算法稳定性：直接插入排序是一种稳定的排序算法
	 * */
	public static void InsertSort(int insert[]){
		int temp;
		int i,j;
		for(i=1;i<insert.length;i++){
			temp  = insert[i];
			for(j=i-1;j>=0 && temp<insert[j];j--){
				insert[j+1]=insert[j];
			}
			insert[j+1]=temp;
			System.out.println(Arrays.toString(insert));
		}
	}
	
	/**
	 * 希尔排序：又称缩小增量排序。先取一个小于n的整数d（称为增量），然后把排序表中的n个记录分为d个子表，
	 *       从下标为0的记录开始，间隔为d的记录组成一个子表，在各个子表内进行直接插入排序。在一趟之后，
	 *       间隔为d的记录组成的子表已有序，随着有序性的改善，逐步减小增量d，重复进行上述操作，直到d=1。	 
	 *空间复杂度为O(1)
	 *算法稳定性：希尔排序是一种不稳定的排序算法
	 * */
	
	public static void ShellSort(int shell[]) {
		int temp;
		int i,j,d;
		for(d=shell.length/2;d>0;d /=2){
			for(i=d;i<shell.length;i++){
				temp=shell[i];
				for(j=i-d;j>=0 && temp<shell[j];j -=d){
					shell[j+d]=shell[j];
				}
				shell[j+d]=temp;
				System.out.println(Arrays.toString(shell));
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int insert[]={34,21,67,23,45,56,8,66,70,36};
		int shell[]={67,52,42,98,35,7,26,39,18,84};
		InsertSort(insert);
		ShellSort(shell);
	}

}
测试结果：
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

[21, 34, 67, 23, 45, 56, 8, 66, 70, 36]
[21, 34, 67, 23, 45, 56, 8, 66, 70, 36]
[21, 23, 34, 67, 45, 56, 8, 66, 70, 36]
[21, 23, 34, 45, 67, 56, 8, 66, 70, 36]
[21, 23, 34, 45, 56, 67, 8, 66, 70, 36]
[8, 21, 23, 34, 45, 56, 67, 66, 70, 36]
[8, 21, 23, 34, 45, 56, 66, 67, 70, 36]
[8, 21, 23, 34, 45, 56, 66, 67, 70, 36]
[8, 21, 23, 34, 36, 45, 56, 66, 67, 70]
[7, 52, 42, 98, 35, 67, 26, 39, 18, 84]
[7, 26, 42, 98, 35, 67, 52, 39, 18, 84]
[7, 26, 39, 98, 35, 67, 52, 42, 18, 84]
[7, 26, 39, 18, 35, 67, 52, 42, 98, 84]
[7, 26, 39, 18, 35, 67, 52, 42, 98, 84]
[7, 26, 39, 18, 35, 67, 52, 42, 98, 84]
[7, 18, 39, 26, 35, 67, 52, 42, 98, 84]
[7, 18, 35, 26, 39, 67, 52, 42, 98, 84]
[7, 18, 35, 26, 39, 67, 52, 42, 98, 84]
[7, 18, 35, 26, 39, 67, 52, 42, 98, 84]
[7, 18, 35, 26, 39, 42, 52, 67, 98, 84]
[7, 18, 35, 26, 39, 42, 52, 67, 98, 84]
[7, 18, 35, 26, 39, 42, 52, 67, 98, 84]
[7, 18, 35, 26, 39, 42, 52, 67, 98, 84]
[7, 18, 35, 26, 39, 42, 52, 67, 98, 84]
[7, 18, 26, 35, 39, 42, 52, 67, 98, 84]
[7, 18, 26, 35, 39, 42, 52, 67, 98, 84]
[7, 18, 26, 35, 39, 42, 52, 67, 98, 84]
[7, 18, 26, 35, 39, 42, 52, 67, 98, 84]
[7, 18, 26, 35, 39, 42, 52, 67, 98, 84]
[7, 18, 26, 35, 39, 42, 52, 67, 98, 84]
[7, 18, 26, 35, 39, 42, 52, 67, 84, 98]