希尔排序如何使用c++语言实现

1、shell sort是一种递减增量的排序算法，该算法是如何操作的。

下面我们大小为9的数组进行演示：54、26、93、17、31、44、55、20

2、令数据间隔为3，将该数组分成三个子数组，如下图所示，为下图中灰色的部分。

3、对每一个子数组都进行插入排序操作，将排序好的子数组合并到一个数组当中。这个时候，你会发现，每个数字都会务必接近他应该存在的位置。

4、这是间隔为3的子数组排序后的结果，发现该排序后的数列非常离露接近我们需要的递减或者递增序列。下一捧罩步只需要，缩小间隔进行重复性操作即可

5、改变间隔，使间隔变成4这个时候子数组反而有4组。这个说明希尔排肺联凤序（shell sort）是一个不稳定的排序。

6、这是一个改进后的shell sort代码

#include <iostream>

using namespace std;

void shellsort(int arr[],int n)

{

      for(int gap=n/2;gap>0;gap/=2)

      {

            //do a gapped insertion sort for this gap size

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

            {

                  int temp=arr[i];

                  int j;

                  for (j=i;j>=gap&&arr[j-gap]>temp;j=j-gap)

                        arr[j]=arr[j-gap];

                  arr[j]=temp;

            }

      }

}

void printarray(int arr[],int n)

{

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

            cout<<arr[i]<<" ";

}

int main()

{

    int a[]={12, 34, 54, 2, 3,16,28,1,46};

    int n=sizeof(a)/sizeof(int);

    shellsort(a,n);

    printarray(a,n);

    return 0;

}