首页 > 算法 > 算法系列之 希尔排序

算法系列之 希尔排序

希尔排序

希尔排序是一种分组插入排序,是插入排序的一种更高效的改进版本.
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
  •      插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率
  •      但插入排序一般来说是低效的, 因为插入排序每次都只能将数据移动一位

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了。

算法实现:

以n=10的一个数组38, 29, 63, 95, 22, 13, 49, 82, 56, 3为例
第一次gap = 10/2 = 5;
Image
1A 1B 2A 2B等为分组标记,相同数字表示同一组,字母表示是同一组的不同元素。
共有5组,分别是(38,13),(29,49),(63,82),(95,56),(22,3) 我们对这5组分别进行插入排序后,这5组变成(13,38),(29,49),(62,82),(56,95),(3,22)
经第一次排序后,数组如下,接着进行第二次 gap = 5/2 = 2
Image
第三次gap = 2/2 = 1
Image
第四次gap = 1/2 = 0 排序完成
Image
下面给出希尔排序的算法实现代码:
void ShellSort1(int a[], int n) 
{
     //分组
     for (int gap = n/2; gap >= 1; gap /=2)
     {
          //分组的起点
          for (int i = 0; i < gap; i++)
          {
               //使用插入排序处理每一个分组     
               for (int j = i + gap; j < n; j += gap)
               {
                    int temp = a[j];
                    for (int k = j - gap; k >= 0; k -= gap)
                    {
                         if (a[k] > temp)
                         {
                              a[k + gap] = a[k]; 
                         }
                         else 
                         {
                              break;
                         }
                    }
                    a[k + gap] = temp;
               }
          }
     }
}
上面的代码可以写得可简洁一点,以第二次为例,是先从1A为起点,然后对1B  1C 1D 1E独个进行插入排序,接着再以2A为起点,然后对2B 2C 2D 2E独个进行插入排序。这样等同于按照顺序对1B  1C 1D 1E 2B 2C 2D 2E独个在组内进行插入排序,这种每次从数组的gap索引开始,并在组内进行排序的算法显然也是正确的。
void ShellSort2(int a[], int n) 
{
     //分组
     for (int gap = n/2; gap >= 1; gap /=2)
     {
          //对于从gap开始的每一个索引,在本组之内进行插入排序     
          for (int j = gap; j < n; j += gap)
          {
               int temp = a[j];
               for (int k = j - gap; k >= 0; k -= gap)
               {
                    if (a[k] > temp)
                    {
                         a[k + gap] = a[k]; 
                    }
                    else 
                    {
                         break;
                    }
               }
               a[k + gap] = temp;
          }
     }
}

(转载本站文章请注明出处 www.helloitworks.com ,请勿用于任何商业用途)

分类: 算法 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.