希尔排序是对直接插入排序算法的一种改进,其基本原理就是让一个无序的数列变得“基本有序”,那么在最后进行直接插入排序的时候时间复杂度将会降低很多(在理想情况下,如果一个数列是有序的,那么使用直接插入排序的算法时间复杂度为O(n));希尔排序算法的效率和“步长”的定义息息相关,但是如何给出一个步长使得希尔排序算法的效率最高,是非常困难的。
import java.util.Scanner; public class ShellInsertSort{ public static void main(String args[]){ Scanner scanner=new Scanner(System.in); int total=scanner.nextInt(); int[] array=new int[1024]; for(int i=0;i<total;i++){ array[i]=scanner.nextInt(); } //定义步长数组 int[] step={10,8,6,5,4,3,2,1}; shellSort(array,total,step); output(array,total); } public static void output(int[] array,int total){ for(int i=0;i<total;i++){ System.out.print(array[i]+" "); } System.out.println(); } /** 参数说明: array:待排数组; total:数组长度; step:步长定义 */ public static void shellSort(int[] array,int total,int[] step){ for(int i=0;i<step.length;i++){ int dk=step[i]; int temp=0; for(int j=dk;j<total;j++){ if(array[j]<array[j-dk]){ temp=array[j]; int k=0; for(k=j-dk;k>=0&&temp<array[k];k-=dk){ array[k+dk]=array[k]; } array[k+dk]=temp; } } } } }
测试用例:仍然使用MyRandom类生成1024个打乱的整数:
import java.util.Random; public class MyRandom { public static void main(String args[]){ int[] array=new int[1024]; for(int i=0;i<1024;i++){ array[i]=i; } for(int i=0;i<=1023;i++){ int m=new Random().nextInt(1024); int n=new Random().nextInt(1024); int temp=array[m]; array[m]=array[n]; array[n]=temp; } System.out.println("1024"); for(int i=0;i<1024;i++){ System.out.print(array[i]+" "); } System.out.println(); } }
运行方法:
java MyRandom | java ShellSort
运行结果:
相关推荐
插入排序在处理小规模有序数据时效率较高,希尔排序正是利用了这一点,先处理较大的间隔,使得元素尽可能接近其最终位置,然后再处理较小的间隔,直到间隔为1,此时相当于执行了一次插入排序,但因为之前的预处理,...
数据结构排序一章的希尔结构排序,显示结果的
这些算法在数据结构与算法课程中是非常重要的基础内容,它们各自有着独特的特性和应用场景。 ### 1. 冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果...
在提供的“希尔排序算法.c”文件中,我们可以预期看到以下关键代码结构: 1. **初始化增量**:定义初始增量,通常为序列长度的一半。 2. **循环处理**:根据增量序列进行循环,每次循环内部: - **分组**:根据...
数据结构 希尔排序 演示 一看就懂 非常直观
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
通过这个程序就可以实现希尔排序,对数据用希尔进行排序
"C语言学习之排序数据结构链表堆排序希尔排序快速排序递归排序" 本资源主要介绍了C语言中的排序算法,包括链表、堆排序、希尔排序、快速排序和递归排序等五种方法。同时,文章还提供了每种排序方法的原理、流程图和...
### 数据结构排序实验报告知识点解析 #### 实验背景与目的 - **实验背景**:本实验报告来源于南昌大学科学技术学院信息学科部计算机系的一次专业课程实验。《数据结构》作为一门重要的计算机基础课程,其目的在于...
希尔排序因其较高的效率和较低的空间复杂度,在处理大规模数据集时表现出色。适用于需要快速排序但空间受限的情况,如内存排序、外部排序等场景。 总之,希尔排序作为一种经典的排序算法,虽然不如快速排序和归并...
python数据结构与算法分析,希尔排序法实现,希尔排序.py
一、实验目的 1、掌握排序的不同方法,并能用高级语言实现排序算法 二、实验内容 1、实现希尔排序算法。
希尔排序(Shell Sort)是一种基于插入排序的算法,由Donald Shell于1959年提出。它的主要思想是将待排序的数据分割成若干个子序列,每个子序列中...理解并熟练掌握希尔排序有助于提升在数据结构和算法领域的专业素养。
### 数据结构之希尔排序 #### 一、希尔排序概述 希尔排序(Shell Sort)是一种基于插入排序的高效算法。它通过将原始数组分为若干个子序列进行插入排序,然后逐步减少子序列的数量,最终达到完全排序的目的。这种...
在编程领域,排序算法是数据结构与算法中的基础部分,对于C语言开发者来说,理解并实现这些算法至关重要。本文将详细讲解六种经典的排序算法——合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并...
编写一个程序实现希尔插入排序过程,并输入{9,8,7,6,5,4,3,2,1,0}的排序过程。希尔排序又称“缩小增量排序”,也是一种插入排序的分析方法,但是在时间效率上较高。
以上是数据结构中关于排序的一些基本知识,包括排序的稳定性、比较次数、内部排序和外部排序的定义,以及直接插入排序、折半插入排序、希尔排序和冒泡排序的原理和特点。这些排序算法各有优缺点,选择哪种排序算法取...