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

算法思路∶

希尔排序是把记录按照下标的一定增量分组，对每组使用直接插入排序算法排序﹔随着增量逐渐减少，每组包含的元素越来越多，肖增量减至1时，整个元素恰被分成一组，算法便终止。

例如原始序列:{29,38,65,87,78,23,27,72,55,48}
第1趟:增量为5(长度len/2)，即:
image.png
下标为0的元素和下标为5的元素一组( 29,23 ) ,
下标为1的元素和下标为6的元素一组( 38,27 )，
下标为2的元素和下标为7的元素一组( 65,72 )，
下标为3的元素和下标为8的元素一组( 87,55 ) ,
下标为4的元素和下标为9的元素一组( 78,48 ) ,
每个组内进行插入排序，得到序列:{23,27,65,55,48,29,38,72,87,78}

第2趟:增量为2(原增量/2)，即:5/2
image.png
下标0,2,4,6,8的元素为一组(23,65,48,38,87 )
下标1,2,5,7,9的元素为一组(27,55,29,72,78 )
每个组内进行插入排序﹐得到序列:image.png

第3趟:增量为1(原增量/2)，即(23,27,38,29,48,55,65,72,87,78}为一组进行插入排序。最终得到有序序列。

代码实现

  1. public class ShellSort {
  2.     public static void main(String[] args){
  3.         int[] arr = {8,9,1,7,2,3,5,4,6,0};
  4.         shellSort(arr);
  5.         Syatem.out.println(Arrays.toString(arr));
  7.     }
  9.     public static void swap (int[] arr, int i, int j )
  10.     {
  11.         int temp = arr[i];
  12.         arr[i] = arr[j];
  13.         arr[j] = temp;
  14.     }
  16.     public static void shellSort(int[] arr)
  17.     {
  18.         for(int gap=arr.length/2;gap>0;gap/=2)
  19.         {
  20.             for(int i=gap;i<arr.length;i++)
  21.             {
  22.                 for(int j=i;j>=gap;j-=gap)
  23.                 {
  24.                     if(arr[j]<arr[j-gap])
  25.                     {
  26.                         //交换
  27.                         swap(arr,j,j-gap);
  28.                     }else{
  29.                         break;
  30.                     }
  31.                 }
  32.             }
  33.         }
  34.     }
  35. }

算法稳定性∶

如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的;插入排序具有稳定性。

我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的算法。

时间复杂度∶

O(nlog2^n)- O(n2)