排序4_希尔排序（插入排序升级版）、10万个数据下和插入排序效率对比_希尔排序对一个10万随机整数数组进行排序。

高级排序之希尔排序

---

希尔排序可以看作是 插入排序的升级版。在对大量的数据进行排序的时候，希尔排序 要比 一般的插入排序快很多。思想

• 将待排序的元素分组 ，对于每组 进行 插入排序
• 组越分越大，对应着组内的元素越来越多，直到最后变成一个组的插入排序，排序结束

关键就是 分组的规则，引入 h ,将 从a[0] - a[h-1] 作为 每个组的第一个元素。其中 h为

//初始化增长量h,为分的组数量
		while(h<a.length / 2) {
			h = 2 * h + 1;
		}
1
2
3
4

代码

• Shell

package xiaosi.bili.four;

public class Shell {

	
	public static void sort(Comparable[] a) {
		
		int h = 1;
		//初始化增长量h,为分的组数量
		while(h<a.length / 2) {
			h = 2 * h + 1;
		}
		
		//h为1为最后一轮执行，意味着已经 合成了一组 完成了排序
		while(h >= 1) {
			//找到待插入的元素，除了h个组的第一个元素，后面的元素全部是待插入的元素
			for(int i = h;i<a.length;i++) {
				
				//待插入的元素 找自己的组，然后插入
				for(int j = i;j>=h;j -= h) {
					//当前组元素插入排序
					if(greater(a[j-h], a[j])) {
						exch(a, j-h , j);
					}
				}
			}
			
			//更新分组
			h /= 2;
		}
	}
	
	//比大小
	public static boolean greater(Comparable num1,Comparable num2) {
		return (num1.compareTo(num2)>0);
	}
	//交换
	public static void exch(Comparable[] a,int i,int j) {
		Comparable temp;
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

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

• TestShellSort

package xiaosi.bili.four;

import java.util.Arrays;

public class TestShell {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Integer[] a = {1,5,9,78,5,26,6,56,5,3,66,12,34};
		Shell.sort(a);
		System.out.println(Arrays.toString(a));//[1, 3, 5, 5, 5, 6, 9, 12, 26, 34, 56, 66, 78]


	}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

选择排序、插入排序和希尔排序大量数据效率对比

对比 分别使用两种排序对 100000 - 1 进行排序

• IO读取数据，添加至List<Integer> list
• list转化为Array数组，调用排序方法
• 计时器计算时间

先IO创建txt文件

package xiaosi.bili.four;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;

public class IOWriteTxt {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		File f = new File("d://a.txt");
		f.createNewFile();
		
		FileWriter fw = new FileWriter(f,true);
		BufferedWriter bw = new BufferedWriter(fw);
		try {
			for(int i = 100000;i>0;i--) {
				bw.write(String.valueOf(i));
				bw.newLine();
			}
		} catch (Exception e) {
			// TODO: handle exception
			System.out.println("....");
			System.out.println("出错了。。。");
		}
			bw.close();
			fw.close();
			
	}

}

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

• 测试比较
  读取数据到list,然后转化为数组，记时比较

package xiaosi.bili.four;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

import xiaosi.bili.three.Inseration;
import xiaosi.bili.two.Selection;

public class SortCompare {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		ArrayList<Integer> list = new ArrayList<>();
		
		
		//加载资源txt资源文件
		BufferedReader reader = new BufferedReader(new InputStreamReader(SortCompare.class.getResourceAsStream("reserve_arr.txt")));
		String line = null;
		while((line = reader.readLine()) != null) {
			//将line字符串转化为Integer
			int i = Integer.parseInt(line);
			list.add(i);
		}
		reader.close();
		System.out.println("待排序的序列长度为：" + list.size());//待排序的序列长度为：100000
		//把ArrayList转化为数组
		Integer[] a = new Integer[list.size()];
		list.toArray(a);
		
		//测试
		//testSelection(a);//选择排序执行的时间为：10807毫秒
		testShell(a);//希尔排序执行的时间为：26毫秒


		//testInseation(a);//插入排序执行的时间为：29373毫秒
	}

	/**
	 * 测试希尔排序
	 * @param a
	 */
	public static void testShell(Integer[] a) {
		Long start = System.currentTimeMillis();
		Shell.sort(a);
		Long end = System.currentTimeMillis();
		System.out.println("希尔排序执行的时间为：" + (end - start) + "毫秒");
	}
	
	/**
	 * 测试 选择排序
	 * 
	 */
	public static void testSelection(Integer[] a) {
		Long start = System.currentTimeMillis();
		Selection.sort(a);
		Long end = System.currentTimeMillis();
		System.out.println("选择排序执行的时间为：" + (end - start) + "毫秒");
	}
	/**
	 * 测试 插入排序
	 */
	public static void testInseation(Integer[] a) {
		Long start = System.currentTimeMillis();
		Inseration.sort(a);
		Long end = System.currentTimeMillis();
		System.out.println("插入排序执行的时间为：" + (end - start) + "毫秒");
	}
}

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
60
61
62
63
64
65
66
67
68
69
70
71

可以得到

• testSelection(a);//选择排序执行的时间为：10807毫秒
• testShell(a);//希尔排序执行的时间为：26毫秒
• testInseation(a);//插入排序执行的时间为：29373毫秒

可以得出 对于大量数据的排序（最坏的情况），希尔排序 约要 比 一般的插入排序 快1000倍

对于少量数据两种方法差别不大