希尔排序

希尔排序

希尔排序是希尔（DonaldShell）于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含 的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。 希尔排序按照步长减少排序的次数，按照步长分为不同的组，每组进行比较，然后排序，本质上还是插入排序。 一、交换法 这个交换耗费的时间比较多 具体实现如下：

//希尔排序之交换法 public static void shellsort(int [] arr) { //设置临时变量 int temp=0; int count=0; //循环设置步长 for (int gap=arr.length/2; gap>0 ;gap/=2 ) { //从步长开始到最后 for (int i = gap; i <arr.length ; i++) { //按照步长交换 for (int j = i-gap; j >=0 ; j-=gap) { //如果前一个数大于gap步长的数交换 if (arr[j]>arr[j+gap]) { //临时存储 temp=arr[j]; //交换 arr[j]=arr[j+gap]; arr[j+gap]=temp; } } } } }

二、移动法 这种最接近插入排序，效率比较高 具体实现如下：

//希尔排序的移位法 public static void shellsort2(int [] arr) { //设置步长 for (int gap=arr.length/2; gap>0 ; gap/=2) { //按照步长来分组 for (int i = gap; i <arr.length ; i++) { //设置j的位置 int j=i; //存储起来 int temp=arr[j]; //如果小于前面的交换 if (arr[j]<arr[j-gap]) { //判断是否越界和是否小于前面的交换 while (j-gap>=0&&temp<arr[j-gap]) { //交换 arr[j]=arr[j-gap]; //减掉步长 j-=gap; } //交换 arr[j]=temp; } } } }