#include<iostream>
#include<malloc.h>
using namespace std;
void shell_sort(int *&s, int len);//希尔排序。 具有不稳定性。 
int main(void)
{
    int len;
    cout<<"请输入长度：";
    cin>>len;cout<<endl;
    int *pArr=(int *)malloc(sizeof(int)*len);
    cout<<"请输入数值：";
    for(int i=0;i<len;i++)
    {
        cin>>pArr[i];
     }
     cout<<"排序前：";
    for(int i=0;i<len;i++)
    {
        cout<<pArr[i]<<" ";
     }
     cout<<endl;cout<<"排序后：";
     shell_sort(pArr, len);
     for(int i=0;i<len;i++)
    {
        cout<<pArr[i]<<" ";
     }
     cout<<endl; 
    return 0;   
} 
void shell_sort(int* &s, int len)
{
    int j;
    int gap;
    for(gap=len/2;gap>0;gap=gap/2)
    {
        for (int i = gap; i < len; i++) //每次增量下，进行几组插入排序
        {
            int  temp = s[i];
            for(j=i-gap;j >= 0 && s[j] > temp; j -= gap)//每一组都进行直接插入排序。 
                s[j + gap] = s[j];
            s[j + gap] = temp;  
        }                                                                                                  
    } 
}