建设网银登录官方网站,渭南公司做网站,旅游类网站模板,广告优化师面试一、前言#xff1a; 这是怀化学院的#xff1a;Java数据结构中的一道难度中等的一道编程题(此方法为博主自己研究#xff0c;问题基本解决#xff0c;若有bug欢迎下方评论提出意见#xff0c;我会第一时间改进代码#xff0c;谢谢#xff01;) 后面其他编程题只要我写完… 一、前言 这是怀化学院的Java数据结构中的一道难度中等的一道编程题(此方法为博主自己研究问题基本解决若有bug欢迎下方评论提出意见我会第一时间改进代码谢谢) 后面其他编程题只要我写完并成功实现会陆续更新记得三连哈哈! 所有答案供参考不是标准答案是博主自己研究的写法。(这一个题书上也有现成的代码重要的是理解它的算法原理!) 二、题目如下 (第 5 题) 希尔排序(难度系数85) 希尔排序 描述 利用希尔排序算法实现线性表的排序。希尔排序是根据给定的增量序列将线性表分隔成某个“增量”的记录组成一个子序例在子序列中采用直接插入排序完成。 输入 第一行为元素个数n(1n1000)第二行为n个元素值(整数)即需要排序的元素个数第三行增量序列中增量个数m第四行为m个增量可以假定最后一个增量为1。 输出 对每一测试用例用m行输出各增量进行希尔排序结果用空格隔开。 样例输入 10 49 38 65 97 76 13 27 49 55 4 3 5 3 1 样例输出 13 27 49 55 4 49 38 65 97 76 13 4 49 38 27 49 55 65 97 76 4 13 27 38 49 49 55 65 76 97 三、代码实现(代码的做题原理全部在代码注释中若还有疑问也可以翻书关于希尔排序的内容) (提示相当于进阶版的直接插入排序根据每次设定的增量有一个增量区间比较区间两头的元素这个比较就是相当于插入排序了再依次往后直到第一次排序完。再接着下一个较小的增量继续划分区间......) (1)创建Main类实现题目里面的所有希尔排序操作
package com.fs.sort;
import java.util.Scanner;
public class Shell_Sort {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt(); //总共需要排序的元素个数int[] data new int[n]; //放到一个数组里for (int i 0; i n; i) {data[i] sc.nextInt();}int m sc.nextInt(); //代表跳跃时插入排序的跳跃增量int[] increment new int[m]; //存入m个增量值for (int j 0; j m; j) {increment[j] sc.nextInt();}//接下来就要用从第一个增量开始到最后一个增量的跳跃式插入排序for (int k 0; k m; k) {int d increment[k]; //每次跳跃时的增量for (int i d; i data.length; i) { //从每次增量下标的位置开始每加一个就是下一个需要比较的区间if (data[i] data[i - d]) { //就是如果当前增量位置的元素要小于当前位置减增量的小标的元素,要登记当前较小位置的元素int temp data[i];int index 0; //从最前面的元素作为一个有序区的第一个元素for (index i - d; (index 0) (data[index] temp); ) { //只要前面的有序区元素大于后面的无序区元素就要交换位置data[index d] data[index];//将原来大的元素给放到原来小的元素的地方(注意是相差一个增量)index index - d; //每次弄完就相当于把第一个有序区的第一个元素后移不满足for循环就退出然后i会加1这样就相当于后面一个增量区间的比较}//如果前面满足了那么index-d的值会变成一个负数所以要给原来增量区间的第一个值赋上较小值就要把下标加上ddata[index d] temp;}}//迭代器依次输出for (Integer data01 : data) {System.out.print(data01 );}System.out.println();}}
}四、不同情况的代码测试运行结果
1首先是题目中的测试输入样例(最好手打输入测试直接复制可能格式问题导致报错) 2其他测试 11 70 30 40 10 80 20 90 100 75 60 45 3 3 2 1
