算法初识---希尔排序

一、算法内容

        希尔排序是插入排序的优化版本，具体做法是:

        1)选定一个增长量h，按照增长量对数据进行分组。

        2)对分好组的每一组数据再进行插入排序。

        3)减小增长量h，最小减为1，重复2)步骤，即继续对分组数据进行插入排序。

二、代码实现

#include <iostream>

using namespace std;

int main()

{  int arr[8]={1,5,9,3,2,4,7,10};

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

   cout<<arr[i]<<' ';

cout<<endl;

  int h=1;

  while(h<8/2)//求增长量h的方法

  {

   h=2*h+1;

  }

  int temp;

   while(h>=1)

   {  for(int i=h;i<8;i+=h)

     {

      for(int j=i-h;j>=0;j-=h)

      {

       if(arr[j]<arr[j-h])

       {  temp=arr[j];

          arr[j]=arr[j-h];

          arr[j-h]=temp;

    }

  else

    break;

   }

  }

    h/=2;   //h减小的原则

}

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

   cout<<arr[i]<<' ';

 return 0;

}