【排序算法系列 4】 高级排序——希尔排序（插入排序的改进）

【排序算法系列 1】冒泡排序 【排序算法系列 2】选择排序 【排序算法系列 3】 插入排序 【排序算法系列 4】 高级排序——希尔排序（插入排序的改进） 【排序算法系列 5】 高级排序——归并排序 【排序算法系列 6】 高级排序——归并排序（由冒泡排序改进） 【排序算法系列 7】堆排序

---

简介

希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。

需求

排序前：{9,1,2,5,7,4,8,6,3,5}排序后：{1,2,3,4,5,5,6,7,8,9}

希尔排序原理

选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；对分好组的每一组数据完成插入排序；减小增长量，最小减为1，重复第二步操作。

增长量h的确定

增长量h的值每一固定的规则，我们这里采用以下规则：N是数组的长度 int h=1 while(h<N/2){ h=2h+1； } //循环结束后我们就可以确定h的最大值； //h的减小规则为： h=h/2

希尔排序API设计

类名Shell构造方法Shell()：创建Shell对象成员方法 11.public static void sort(Comparable[] a)：对数组内的元素进行排序成员方法 22.private static boolean greater(Comparable v,Comparable w):判断v是否大于w成员方法 33.private static void exch(Comparable[] a,int i,int j)：交换a数组中，索引i和索引j处的值

希尔排序的代码实现

public class Shell { //对数组a中的元素进行排序 public static void sort(Comparable[] a){ //1.根据数组a的长度，确定增长量h的初始值； int h = 1; while(h<a.length/2){ h=2*h+1; } //2.希尔排序 while(h>=1){ //排序 //2.1.找到待插入的元素 for (int i=h;i<a.length;i++){ //2.2把待插入的元素插入到有序数列中 for (int j=i;j>=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; } }

希尔排序的时间复杂度: O(n^(1.3~2))