本文共 3961 字，大约阅读时间需要 13 分钟。

高级排序之希尔排序

希尔排序可以看作是 插入排序的升级版

在对大量的数据进行排序的时候，希尔排序 要比 一般的插入排序快很多

思想：

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

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

其中 h为

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

代码

• 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;	}}

• 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]	}}

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

对比 分别使用两种排序对 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();				}}

• 测试比较
  读取数据到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) + "毫秒");	}}

可以得到

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

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

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