Time limit: 10000MS Memory limit: 32768K
请用希尔排序对给定的数组进行从小到大排序后输出。
输入分两行,第一行一个整数n(1<=n<=3000000),第二行n个数,每个数都是32位整数型,两个数之间有1个空格隔开。
输出也分两行,第一行一个整数n,第二行是排序后的n个数,两个数之间有1个空格隔开。
Sample Input
5
5 4 3 2 1
Sample Output
5
1 2 3 4 5
用cin、cout会超时
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int const ic_limit = 3000002;
int iArr[ic_limit];
void vInput(int iN);
void vShellSort(int iN);
void vOutput(int iN);
int main()
{
int iN;
while(scanf("%d",&iN) != EOF)
{
memset(iArr,0,sizeof(iArr));
vInput(iN);
vShellSort(iN);
vOutput(iN);
}
return 0;
}
void vInput(int iN)
{
for(int i=1; i<=iN; i++)
{
scanf("%d",&iArr[i]);
}
}
void vOutput(int iN)
{
printf("%d\n",iN);
for(int i=1; i<iN; i++)
{
printf("%d ",iArr[i]);
}
printf("%d\n",iArr[iN]);
}
void vShellSort(int iN)
{
int i,j;
int iTemp;
int iDistance;
iDistance = iN/2;
while(iDistance >= 1)
{
for(i=iDistance; i<=iN; i++)
{
iTemp = iArr[i];
for(j=i; j>=iDistance && iTemp<iArr[j-iDistance]; j-=iDistance)
{
iArr[j] = iArr[j-iDistance];
}
iArr[j] = iTemp;
}
iDistance /= 2;
}
}
下面的解释是网上看到的:
希尔属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序
排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止
初始:d=5
49 38 65 97 76 13 27 49 55 04
49 13
|-------------------|
38 27
|-------------------|
65 49
|-------------------|
97 55
|-------------------|
76 04
|-------------------|
一趟结果:13 27 49 55 04 49 38 65 97 76
d=3
13 27 49 55 04 49 38 65 97 76
13 55 38 76
|------------|------------|------------|
27 04 65
|------------|------------|
49 49 97
|------------|------------|
二趟结果:13 04 49 38 27 49 55 65 97 76
d=1
13 04 49 38 27 49 55 65 97 76
|----|----|----|----|----|----|----|----|----|
三趟结果: 04 13 27 38 49 49 55 65 76 97
希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。
分享到:
相关推荐
希尔排序(Shell Sort)是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的元素按照一定的间隔分组,对每组进行插入排序,然后逐渐减小间隔,直到间隔为1,此时整个序列视为...
希尔排序(Shell Sort)是由Donald Shell在1959年提出的一种基于插入排序的改进算法。它的主要思想是通过设置一系列的增量序列,逐步减少这些增量,将待排序的元素进行分组,然后在每个小组内进行直接插入排序。这个...
本文将详细讲解六种经典的排序算法——合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并结合提供的文件名(sort.c、set.c、main.c、set.h、sort.h)推测出每个文件可能包含的代码实现。 1. **合并...
希尔排序(Shell Sort)是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一个增量序列分成若干个子序列,然后对每个子序列进行插入排序,最后再进行一次全局的插入...
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
### 希尔排序法(希尔插入排序,希尔交换排序) #### 一、希尔排序法简介 希尔排序法是计算机科学领域中一种重要的排序算法,它由美国计算机科学家Donald Shell于1959年提出,因此得名希尔排序。希尔排序是一种...
希尔排序(Shell Sort)是一种基于插入排序的快速排序方法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一定的间隔进行分组,然后对每组进行插入排序,随着间隔逐渐缩小,最后进行一次全排列,...
### 直接插入排序与希尔排序的比较 #### 一、概述 本篇文章将通过一组具体的数据集(8个整数)对直接插入排序(Direct Insertion Sort)和希尔排序(Shell Sort)这两种排序方法进行深入分析和比较。这两种排序...
希尔排序(Shell Sort)是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一定的增量分组,对每组使用直接插入排序,然后逐渐减小增量,继续进行分组排序,直到增量...
根据提供的文件信息,我们可以深入探讨几种经典的排序算法:冒泡排序、直接插入排序、快速排序以及希尔排序。这些算法在数据结构与算法课程中是非常重要的基础内容,它们各自有着独特的特性和应用场景。 ### 1. ...
下面将详细讲解这7种排序算法:快速排序、归并排序、插入排序、选择排序、冒泡排序、堆排序以及希尔排序。 1. **快速排序**:由C.A.R. Hoare提出的,采用分治策略。基本思想是选取一个基准元素,通过一趟排序将待...
本主题将详细探讨希尔排序、冒泡排序、堆排序等经典的排序算法,这些都是数据结构与算法学习中的核心内容,尤其对于北邮数据结构课程来说,理解并掌握这些排序方法至关重要。 1. **插入排序**: 插入排序是一种...
这里我们将深入探讨四种常见的排序算法:基数排序、堆排序、希尔排序和直接插入排序。 首先,基数排序是一种非比较型整数排序算法,它的基本思想是将整数按位数切割成不同的数字,然后按每个位数分别比较。基数排序...
希尔排序(Shell Sort)是一种基于插入排序的快速排序算法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据按照一个增量序列分成若干个子序列,然后对每个子序列进行插入排序,最后减小增量,重复这个...
### 希尔排序原理与实现 #### 一、希尔排序简介 希尔排序(Shell Sort)是一种基于插入排序的高效算法。它通过将原始数组分割成多个子序列来进行排序,从而提高了插入排序的效率。希尔排序的核心思想是通过将相隔...
本资源提供了七大经典排序算法的实现程序,包括快速排序、冒泡排序、选择排序、归并排序、插入排序、希尔排序和堆排序。下面将逐一详细介绍这些排序算法及其原理。 1. 快速排序:由C.A.R. Hoare提出,是一种采用...
希尔排序,又称希尔斯排序,是由美国计算机科学家Donald Shell于1959年提出的一种基于插入排序的快速排序算法。这种排序方法通过设置一个增量序列,将待排序数组分割成若干个子序列,然后对每个子序列进行插入排序。...
希尔排序是一种基于插入排序的快速排序算法,由Donald Shell在1959年提出。它的主要特点是通过将待排序的数组元素按照一定的间隔分组,然后对每组进行插入排序,随着间隔逐渐减小,直到间隔为1时,整个数组成为一个...
希尔排序首先选择一个较大的增量,对数组进行插入排序,然后逐渐减小增量,再次对数组进行插入排序,直到增量为1,这时数组的每个元素间隔为1,相当于进行了一次插入排序,整个数组已经基本有序。在给出的`...
### 希尔排序算法详解 #### 算法概述 希尔排序(Shell Sort),又称为缩小增量排序,是插入排序的一种更高效的改进版本。它由Donald Shell在1959年提出。希尔排序的基本思想是:将待排序列分割成若干子序列分别...