希尔排序的原理，图解，java代码实现

希尔排序

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

排序原理

排序原理：

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

举例排序过程

对{9,1,2,5,7,4,8,6,3,5}进行排序。如下图

代码实现

成员方法：

public static boolean greater( int a,int b) 判断a是否大于b，返回true/falsepublic static void exch(int[] a,int i,int j) 交换数组的索引i处和索引j处的值public static void sort(int[] a) 对数组a进行希尔排序 首先确定增长量h当h>=1的时候就继续排序，循环所有的待排序的数字。内嵌循环则从所有i处往前每次已h递减遍历元素，所有j处的值小于所有j-h处的值，则交换位置，否则，说明不需要交换位置，结束循环。每趟排序结束后，h=h/2 import java.util.Arrays; public class SortShell { public static void main(String[] args) { int[] array=new int[]{9,1,2,5,7,4,8,6,3,5}; sort(array); System.out.println(Arrays.toString(array)); } /** * 比较两个数之间的大小 * @param a * @param b * @return */ public static boolean greater( int a,int b){ return a>b; } /** * 交换两个数的位置 * @param a * @param i * @param j */ public static void exch(int[] a,int i,int j){ int temp=a[i]; a[i]=a[j]; a[j]=temp; } /** * 希尔排序 * @param a */ public static void sort(int[] a){ //确定增长量 int h=1; while(h<(a.length/2)){ h=h*2+1; } //希尔排序 while(h>=1){ //排序 //找到待插入的元素a[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); }else{ break; } } } h=h/2; } } }