SDUTACM 数据结构实验之排序六：希尔排序

绝地灬酷狼 2022-09-25 10:17 108阅读 0赞

## 题目描述 ##

我们已经学习了各种排序方法，知道在不同的情况下要选择不同的排序算法，以期达到最好的排序效率；对于待排序数据来说，若数据基本有序且记录较少时， 直接插入排序的效率是非常好的，希尔排序就是针对一组基本有序的少量数据记录进行排序的高效算法。你的任务是对于给定的数据进行希尔排序，其中增量dk=n/(2^k)(k=1,2,3……)

## 输入 ##

连续输入多组数据，每组输入数据的第一行给出一个正整数N(N <= 10000)，随后连续给出N个整数表示待排序关键字，数字间以空格分隔。

## 输出 ##

输出dk=n/2和dk=1时的结果。

## 示例输入 ##

10
    10 9 8 7 6 5 4 3 2 1
    10
    -5 9 7 -11 37 -22 99 288 33 66

## 示例输出 ##

5 4 3 2 1 10 9 8 7 6
    1 2 3 4 5 6 7 8 9 10
    -22 9 7 -11 37 -5 99 288 33 66
    -22 -11 -5 7 9 33 37 66 99 288

## 提示 ##

#include<stdio.h>
    int a[1000],n;
    void shell(int dk)
    {
    	int i,j;
    	for(i=dk+1;i<=n;i++)
    		if(a[i]<a[i-dk])
    		{
    			a[0]=a[i];
    			for(j=i-dk;j>0&&a[j]>a[0];j=j-dk)
    				a[j+dk]=a[j];
    			a[j+dk]=a[0];
    		}
    }
    void main()
    {
    	int i,j;
    	while(scanf("%d",&n)!=EOF)
    	{
    		for(i=1;i<=n;i++)
    			scanf("%d",&a[i]);
    		shell(n/2);
    		for(i=1;i<n;i++)
    			printf("%d ",a[i]);
    		printf("%d\n",a[i]);
    		shell(1);
    		for(i=1;i<n;i++)
    			printf("%d ",a[i]);
    		printf("%d\n",a[i]);
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，108人围观）

还没有评论，来说两句吧...

相关阅读

相关 SDUTACM 数据结构实验之排序六：希尔排序

题目描述我们已经学习了各种排序方法，知道在不同的情况下要选择不同的排序算法，以期达到最好的排序效率；对于待排序数据来说，若数据基本有序且记录较少时，直接插入排序的效率

绝地灬酷狼/ 2022年09月25日 10:17/ 0 赞/ 109 阅读

相关数据结构实验之排序六：希尔排序

数据结构实验之排序六：希尔排序 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述我们

我就是我/ 2022年08月18日 13:16/ 0 赞/ 131 阅读

相关数据结构实验之排序六：希尔排序

数据结构实验之排序六：希尔排序 Time Limit: 1000MS Memory limit: 65536K 题目描述我们已经学习了各种排序方法，

柔光的暖阳◎/ 2022年07月17日 01:37/ 0 赞/ 158 阅读

相关数据结构实验之排序六：希尔排序

数据结构实验之排序六：希尔排序 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][]

Myth丶恋晨/ 2022年07月14日 13:18/ 0 赞/ 158 阅读

相关数据结构实验之排序六：希尔排序

hint: 1增量公式数据结构实验之排序六：希尔排序 Time Limit: 1000MS Memory Limit: 65536KB Problem Descr

一时失言乱红尘/ 2022年07月12日 11:39/ 0 赞/ 161 阅读

相关数据结构实验之排序六：希尔排序

数据结构实验之排序六：希尔排序 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem

比眉伴天荒/ 2022年06月03日 08:12/ 0 赞/ 284 阅读

相关【希尔排序】数据结构实验之排序六：希尔排序

Think: 1知识点：希尔排序 2希尔排序基本思想(分组插入)：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中

- 日理万妓/ 2022年06月03日 05:13/ 0 赞/ 259 阅读

相关数据结构实验之排序六：希尔排序

算法内容转载自：[https://blog.csdn.net/weixin\_37818081/article/details/79202115][https_blog.cs

爱被打了一巴掌/ 2022年05月16日 01:44/ 0 赞/ 176 阅读

相关数据结构实验之排序六：希尔排序

数据结构实验之排序六：希尔排序 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][]

灰太狼/ 2022年04月08日 14:54/ 0 赞/ 187 阅读

相关数据结构实验之排序六：希尔排序

Problem Description 我们已经学习了各种排序方法，知道在不同的情况下要选择不同的排序算法，以期达到最好的排序效率；对于待排序数据来说，若数据基本有序且记录较

缺乏、安全感/ 2022年04月08日 09:54/ 0 赞/ 170 阅读