希尔排序学习心得


		    希尔排序是基于插入排序的一种快速排序算法，核心思想是使待排序序列中间隔为h（变化的）的元素都是有序的。
        基本思路如下：假设待排序序列为A，长度为N（方便起见，可以理解为数组）。首先，取一个小于N的整数h1作为第一个增量，这样，序列就被分为h1组，所有距离为h1的数据分在一组中，对各组进行插入排序；然后，再取第二个增量h2（h2<h1），序列便被分为h2组，再次进行插入排序，直到所取增量h = 1，即对整个序列进行直接插入排序。
        综合网上大家意见，h初次取值（即h1）一般为序列长度的一半，然后每次减半，直到增量为1。我查看了一些资料，找到以下这种效率更高但实现又不复杂的取值方法，并在此实现希尔排序(java)：
       void shellSort(int[] a)
      {
           int N = a.length;
           int h = 1;
           while(h<N/3) h = h*3+1;
           while(h>=1)
          {
                  for(int i = h;i<N;i++)
                 {
                          for(int j = i; j>=h&&a[j]<a[j-h] ;j -= h)
                          {
                                     swap(a[j] , a[j-h]);//此处不细写了，交换大家肯定会。
                          }
                 }
               h = h/3;
          }
      }
      在序列不变的前提下，希尔排序的效率取决于h的取值方法。一种更有效率的希尔排序的h的取值方法稍后更新。

补充：综合编程 , 其他综合 ,