希尔排序问题利用随机函数产生N个随机整数(10个以上)

利用随机函数产生N个随机整数(10个以上)，对这些数由小到大排序
要求:至少采用3次缩小增量，采用希尔排序

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void shellSort(int *a, int len)
{
    int i, j, k, tmp, gap,cnt=1;  // gap 为步长
    for (gap = len / 2; gap > 0; gap /= 2) {  // 步长初始化为数组长度的一半，每次遍历后步长减半,
        for (i = 0; i < gap; ++i) { // 变量 i 为每次分组的第一个元素下标
            for (j = i + gap; j < len; j += gap) { //对步长为gap的元素进行直插排序，当gap为1时，就是直插排序
                tmp = a[j];  // 备份a[j]的值
                k = j - gap;  // j初始化为i的前一个元素（与i相差gap长度）
                while (k >= 0 && a[k] > tmp) {
                    a[k + gap] = a[k]; // 将在a[i]前且比tmp的值大的元素向后移动一位
                    k -= gap;
                }
                a[k + gap] = tmp;
            }
        }
        printf("第%d次增量 ",cnt++);
         for(i=0;i<=10;i++)
            printf("%d ",a[i]);
            printf("%d\n");
    }
}
 
int main()
{
    int i,j,x,a[11];//产生随机数
    srand((unsigned)time(NULL));//保证每次生成的随机数不一样
    for(i=0;i<=10;i++)
    {
        a[i]=rand()%(1000-99)+99;//随机数的范围（a,b)
    printf("%d ",a[i]);
    }
    printf("\n");
    shellSort(a,11);
    printf("最终结果");
        for(i=0;i<=10;i++)
            printf("%d ",a[i]);
 
}
 

参考下

#include<stdio.h>
#include<time.h>
#include<stdlib.h>

//希尔排序
void Shellsort(int data[],int n) {
    int i,j,temp,incre;
    for (incre=n/2; incre>=1; incre/=2) {  // 增量初始化为数组长度的一半,每次遍历后增量减半
        for (i=incre; i<n; i++) {   //分组：增量为incre的为一组，对组内进行插入排序,当incre为1时,就是直插排序;
                                    //i++使每个数都参与组内排序
            temp=data[i];  //备份data[i]的值
            for (j=i-incre; j>=0 && data[j]>temp; j-=incre) {   //组内比较 ，j-=incre使其与组内每个数都进行比较
                data[j + incre] = data[j];  //将在data[i]前且比temp大的元素在组内后移,单次来看就是交换位置
            }
            data[j + incre] = temp;
        }
    }
}

int main(){
    int i, N = 30; //随机数个数
    int data[30];
    srand(time(NULL));
    for(i=0;i<N;i++){
        data[i]=rand()%1000;
        printf("%d ", data[i]);
    }
    printf("\n");
    Shellsort(data,N);      //希尔排序
    for(i=0;i<N;i++){
        printf("%d ", data[i]);
    }
    return 0;
}

#include<stdio.h>
void ShellSort(int*a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        //gap/=2;//取一个中间值
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; i++)
        {
            int end = i;
            int ret = a[end + gap];
            while (end >= 0)
            {
                if (a[end] > ret)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                    break;
            }
            a[end + gap] = ret;
        }
    }
}
int main()
{
    int num;
   scanf("%d",&num);
    srand((unsigned int)time(NULL));
    int*n=(int*)malloc(sizeof(int)*num);
    int i;
    for (i = 0; i < num; i++)
    {
        n[i] = rand();
        printf("%d ", n[i]);
    }
    printf("\n");
    ShellSort(n,num);
    for (i = 0; i < num; i++)
    {
        printf("%d ", n[i]);
    }
    return 0;
}