排序算法review<2>--Shell 排序

shell排序方法也是一种插入排序算法，于1959年由D.L.Shell提出，其基本方法是：首先将带排序文件分为d1（d1<n）组，将所有彼此之间间隔为d和d的倍数的记录放在一组中，然后在组内进行排序，然后重新去正整数d2<d1，将原带排序序列分为d2组，重复上述分组和排序过程.......直到选取的整数dk=1，即所有带排序的序列元素都在一组中为止。每组中排序采用插入排序。每趟排序di在不断缩小，最后为1。每个di都有不同的选择，只要满足n>d1>d2.......>dk=1，在排序过程中，不同的di的选取对应不同的排序速度。比较常见的选择方法：d1=n，di+1=di/2.......或者di+1=di/3。

eg：原序列的初始状态为 44 35 49 72 26 13 54 61 28 ；[ n=9 ]，现在取d1 = n/2 = 4；

第一趟，索引为0,4,8的元素，即44 26 28 一组；索引为1,5的元素，即35 13一组；索引为2,6的元素，即49 54一组；索引为3,7的元素，即72 61一组。组内排序，结果：

26 13 49 61 28 35 54 72 44；

第二趟，d2=d1/2=2；故索引为0,2,4,6,8的元素一组；索引为1,3,5,7的元素一组；组内排序，结果：

26 13 28 35 44 61 49 72 54；

第三趟，d3=d2/2=1；该趟结束后排序结束。所有元素在同一组中，任意前后两个元素之间排序，结果：

13 26 28 35 44 49 54 61 72；

算法：

#include<stdlib.h>

#include<iostream>

using namespace std;

template <class T>

void shell_sort(T *array,int n)

{

     int d = (int)(n/2);//将原纪录分为d个组

     while(d>=1)

     {

         int i,j;

         for(i = d ; i < n ; i ++)//组内排序

         {

              T temp = array[i];

              for(j = i - d ; j >= 0 && temp < array[j] ; j-=d)

              {

                 array[j+d] = array[j];

              }

              array[j+d] = temp;

          }

          d /= 2;//d在逐渐缩小，知道为1

     } 

}

int main(void)

{

      int n;

      int array[100];

      while(cin>>n)

      {

         for(int i = 0;i < n ; i++)

         cin>>array[i];

         shell_sort(array,n);

         for(int i = 0;i < n ; i ++)

         cout<<array[i]<<endl;

      }

}

shell排序的时间复杂度比直接插入排序要好，其时间复杂度和di的选取有关系。其平均比较次数和移动次数在n^1.3左右。为不稳定的排序方法。

巴特西

排序算法review<2>--Shell 排序

最新文章

热门文章