每日学点新东西~感觉希尔排序是对插入排序的一种改进~

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<windows.h>
#define MAX 255
int R[MAX]={0};
void ShellPass(int d,int n)
{
    /*希尔排序中的一趟排序,d为当前增量*/

    int i=0;
    int j=0;

    for (i=d+1;i<=n;++i)
        if (R[i]<R[i-d])
        {
            R[0]=R[i];
            j=i-d;
            /*R[0]只是暂存单元,不是哨兵*/

            do
            {
                /*查找R[i]的插入位置*/
                R[j+d]=R[j];
                /*后移记录*/
                j=j-d;
            }while (j>0&&R[0]<R[j]);

            R[j+d]=R[0];
            /*插入R[i]到正确的位置上*/
        }
}
void Shell_Sort(int n)
{
    int increment=n;
    /*增量初值,不妨设n>0*/
    do
    {
        increment=increment/3+1;
        /*求下一增量*/
        ShellPass(increment,n);
        /*一趟增量为increment的Shell插入排序*/
    }while (increment>1);
}
int main()
{
    int i=0;
    int n=0;
    /*clrscr()*/
    system("cls");

    puts("Please input total element number of the sequence:");
    scanf("%d",&n);

    if (n<1||n>MAX)
    {
        printf("n must more than 0 and less than %d.\n",MAX);
        exit(0);
    }

    puts("Please input the elements one by one:");
    for (i=1;i<=n;++i)
        scanf("%d",&R[i]);

    puts("The sequence you input is:");

    for (i=1;i<=n;++i)
        printf("%4d",R[i]);

    Shell_Sort(n);
    puts("\nThe sequence after shell_sort is:");

    for (i=1;i<=n;++i)
        printf("%4d",R[i]);

    puts("\n");

    return 0;
}

[此贴子已经被作者于2017-2-16 14:03编辑过]

这个是九九另外找资料的~和一楼的比对一下~

#include<stdio.h>
#include<math.h> 
#define MAXNUM 10 
void shellSort(int array[],int n,int t);
void shellInsert(int array[],int n,int dk);
int main()
{    
    //t为排序趟数    
    int array[MAXNUM],i; 
    
    for(i=0;i<MAXNUM;i++)        
        scanf("%d",&array[i]);   
    
    shellSort(array,MAXNUM,(int)(log(MAXNUM+1)/log(2)));

    //排序趟数应为log2(n+1)的整数部分 
    
    for(i=0;i<MAXNUM;i++)        
        printf("%d ",array[i]);    
     printf("\n");

     return 0;

} //根据当前增量进行插入排序
void shellInsert(int array[],int n,int dk)
{    
    int i,j,temp;    
    for(i=dk;i<n;i++)
    {        
        //分别向每组的有序区域插入   
        temp=array[i];       
        for(j=i-dk;(j>=i%dk)&&array[j]>temp;j-=dk)//比较与记录后移同时进行
            array[j+dk]=array[j];   
        
         if(j!=i-dk)            
            array[j+dk]=temp;//插入    
    }
} //计算Hibbard增量
int dkHibbard(int t,int k)
{    
    return (int)(pow(2,t-k+1)-1);

} //希尔排序
void shellSort(int array[],int n,int t)
{      
    int i;    
    for(i=1;i<=t;i++)       
        shellInsert(array,n,dkHibbard(t,i));
}

PS:1楼提供的代码没有希尔步长的计算公式(用i/3+1来代替)~~感觉这个较为系统~

[此贴子已经被作者于2017-2-16 14:29编辑过]

再自己敲一遍熟悉一下~
PS:感觉参考代码没有什么可以挑剔的地方就没有改了~

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
void creat(int** a,int* n)
{
    printf("请输入案例:");
    scanf("%d",n);
    if (*n<1||(*a=(int* )malloc(*n*sizeof(int)))==NULL)
        exit(0);

    memset(*a,0,*n*sizeof(int));
}
void input(int a[],int n)
{
    int i=0;

    printf("请输入%d个数据:\n",n);
    for (;i!=n;++i)
        scanf("%d",&a[i]);
}
void print(int a[],int n)
{
    int i=0;

    printf("输出结果如下:\n");
    for (;i!=n;++i)
        printf("%-4d",a[i]);

    printf("\n");
}
void shell_Insert(int a[],int n,int step)
{
    int i=0;
    int j=0;

    for (i=step;i<n;++i)
    {
        int key=a[i];
        for (j=i-step;(j>=i%step)&&a[j]>key;j-=step)
            a[j+step]=a[j];

        if (j!=i-step)
            a[j+step]=key;
    }
}
int dkHibbard(int t,int k)
{
    return (int )(pow(2,t-k+1)-1);
}
void shell_Sort(int a[],int n,int t)
{
    int i=0;

    for (i=1;i<t+1;++i)
        shell_Insert(a,n,dkHibbard(t,i));
}
int main()
{
    int *a=NULL;
    int n=0;

    creat(&a,&n);

    input(a,n);

    shell_Sort(a,n,(int )(log(n+1)/log(2)));

    print(a,n);

    free(a);

    return 0;
}

[此贴子已经被作者于2017-2-17 10:14编辑过]

，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，，我也考虑去看看希尔，不知道为什么想到哈希，虽然这两个我都不知道

看了下希尔排序的思路，还是不太明白为什么要这样做，说是让间距从<n开始，逐渐递减到1,那和直接取１又有什么区别就不懂了

今天九九外出~没怎么看贴~
希尔排序是基于插入排序~是对插入排序的一种改进~通过步长的设定来减少移动平均次数~原理是数据从一开始的无序时~希尔步长大~移动的数据的间隔较远~可以减少移动次数~后来希尔步长慢慢减少~但通过前面的移动数据~使数据趋向于有序了~固减少了移动次数~

[此贴子已经被作者于2017-2-18 23:10编辑过]

这个现在对橙子还深了点以后有机会再慢慢理解~