希尔排序 (高级排序)
目录
希尔排序
排序原理
代码展示
希尔排序的时间复杂度分析
今天给大家分享的笔记是关于希尔排序
有点像 插入排序 的升级版~
希尔排序
希尔排序是插入排序的一种，又称"缩小增量排序”，是插入排序算法的一种更高效的改进版本。 前面学习插入排序的时候，我们会发现一个很不友好的事儿，如果已排序的分组元素为{2.5,7,9,10}，未排序的分组元素为(1,8}，那么下一个待插入元素为1，我们需要拿着1从后往前，依次和10,9,7,5,2进行交换位置，才能完成真正的插入，每次交换只能和相邻的元素交换位置。
那如果我们要提高效率，直观的想法就是一次交换，能把1放到更前面的位置，比如一次交换就能把1插到2和5之间，这样一次交换1就向前走了5个位置，可以减少交换的次数，这样的需求如何实现呢?接下来我们来看看希尔排序的原理。
需求∶
排序前:{9,1,2,5,7,4,8,6,3,5}
排序后:{1,2,3,4,5,5,6,7,8,9}
排序原理
1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组;
2.对分好组的每一组数据完成插入排序;
3.减小增长量，最小减为1，重复第二步操作。
增长量h的确定:增长量h的值每一固定的规则，我们这里采用以下规则
int h=1; while(h<数组的长度/2){ h=2h+1; } //循环结束后我们就可以确定h的最大值 h的减小规则为： h=h/2
代码展示
Shell方法
public class Shell { /*对数组a中的元数进行排序*/ public static void sort(Comparable[] a){ //1.根据数组a的长度，确定增长量h的初始值 int h=1; while(h=1){ //排序 //2.1.找到待插入的元素 for (int i = h; i =h; j-=h) { //带插入元素是a[j],比较a[j]和a[j-h]; if(greater(a[j-h],a[j])){ //交换元素 exch(a,j-h,j); }else{ //带插入元素已经找到了合适的位置，结束循环 break; } } } //减小h的值 h=h/2; } } /*比较v元素是否大于w元素*/ private static boolean greater(Comparable v,Comparable w){ return v.compareTo(w)>0; } /*数组元素i和j交换位置*/ private static void exch(Comparable[] a,int i,int j){ Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; }}测试类
import java.util.Arrays;public class ShellTest { public static void main(String[] args) { Integer[] arr ={9,1,2,5,7,4,8,6,3,5}; Shell.sort(arr); System.out.println(Arrays.toString(arr)); }}
希尔排序的时间复杂度分析
在希尔排序中，增长量h并没有固定的规则，有很多论文研究了各种不同的递增序列，但都无法证明某个序列是最好的，对于希尔排序的时间复杂度分析，已经超出了我的学习范围，所以在这里就不做分析了。我们可以使用事后分析法对希尔排序和插入排序做性能比较。
我有一个123.txt文件，里面存放的是从100000到1的逆向数据，我们可以根据这个批量数据完成测试。测试的思想∶在执行排序前前记录一个时间，在排序完成后记录一个时间，两个时间的时间差就是排序的耗时。
希尔排序和插入排序性能比较测试代码:
public class SortCompare { public static void main(String[] args) throws IOException { ArrayList list = new ArrayList(); BufferedReader reader = new BufferedReader(new FileReader("E:\\study\\study\\JAVA\\java数据结构\\Text\\高级排序\\src\\希尔排序\\Text\\123.txt")); String line = null; while((line=reader.readLine())!=null){ //line是字符串，把line转换成Integer储存到集合 int i = Integer.parseInt(line); list.add(i); } reader.close(); //集合转数组 Integer[] a = new Integer[list.size()]; list.toArray(a); //测试性能// DeShell(a);// DeInsertion(a); } public static void DeShell(Integer[] a){ long start = System.currentTimeMillis(); Shell.sort(a); long end = System.currentTimeMillis(); System.out.println("希尔排序执行的时间为："+(end-start)+"毫秒"); } public static void DeInsertion(Integer[] a){ long start = System.currentTimeMillis(); Insertion.sort(a); long end = System.currentTimeMillis(); System.out.println("插入排序执行的时间为："+(end-start)+"毫秒"); }}//插入排序执行的时间为：13416毫秒//希尔排序执行的时间为：15毫秒//由此可见希尔排序完虐插入排序
这里的 Shell 和 Insertion 是已经写好的方法API，具体代码请查看 插入排序 ，希尔排序两文。
那么今天的分享结束啦！
下一篇 归并排序 更精彩！
喜欢记得一键三连哦~
