【软考】希尔排序算法分析

2024-09-09 06:36

本文主要是介绍【软考】希尔排序算法分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

          • 1. c代码
          • 2. 运行截图
          • 3. 运行解析

1. c代码
#include <stdio.h>
#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;int dk;int j;k = n;delta = (int *)malloc(sizeof(int)*(n/2));i = 0;do{// 不断除以2k = k / 2;delta[i] = k;printf("%d ", delta[i]);i++;}while(k > 1);printf("\n");i = 0;dk = delta[i];while(dk > 0){for(k = delta[i]; k < n; ++k){// data[k-dk]是靠前的数,data[k]是靠后的数if(data[k] < data[k-dk]){// 用临时变量temp暂存小的数temp = data[k];// for(j = k - dk; j >= 0 && temp < data[j]; j -= dk){data[j+dk] = data[j];}data[j+dk] = temp;}// 打印printf("排序后的数组: ");for (int a = 0; a < n; a++) {printf("%d ", data[a]);}printf("\n");}++i;dk = delta[i];}
}int main(int argc, char const *argv[]){int data[10] = {48, 37, 64, 96, 75, 12, 26, 48, 54, 3};// 数组长度int n = sizeof(data) / sizeof(data[0]);shellSort(data, n);// 打印printf("排序后的数组: ");for (int i = 0; i < n; i++) {printf("%d ", data[i]);}return 0;
}
2. 运行截图

在这里插入图片描述

3. 运行解析
1.从main方法开始
2.待排序数组为: {48, 37, 64, 96, 75, 12, 26, 48, 54, 03}
3.数组长度:int n = sizeof(data) / sizeof(data[0]) = 10/1=10
4.执行shellSort(data, n)
5.k=n=10, i=0
6.delta[0]=10/2=5
7.delta[1]=5/2=2
8.delta[2]=2/2=1
9.dk=delta[i]=delta[0]=5
10.此时dk>0成立,进入while循环11.k=delta[0]=5
12.k<n即5<10成立,进入第一个for循环
13.data[k]=data[5]=12
14.data[k-dk]=data[5-5]即data[0]=48
15.data[k]<data[k-dk]即12<48成立,进入if语句
16.temp=data[k]即temp=data[5]=12
17.j=k-dk=5-5=0
18.j>=0成立
19.data[j]即data[0]=48
20.temp<data[j]即12<48成立,进入第二个for循环
21.data[j+dk]=data[j]即data[j+dk]=data[1],j+dk=5,即data[5]=48
22.j=j-dk=0-5=-5
23.j>=0即-5>=0不成立,跳出第二个for循环
24.data[j+dk]=temp即data[-5+5]=data[0]=12
25.此时data[0]=12,data[5]=48,数组为:{12, 37, 64, 96, 75, 48, 26, 48, 54, 03}
26.k=k+1=5+1=627.k<n即6<10成立,接着第一个for循环
28.data[k]=data[6]=26
29.data[k-dk]=data[6-5]即data[1]=37
30.data[k]<data[k-dk]即26<37成立,进入if语句
31.temp=data[k]即temp=data[6]=26
32.j=k-dk=6-5=1
33.j>=0成立
34.data[j]=data[1]=37
35.temp<data[j]即26<37成立,进入第二个for循环
36.data[j+dk]=data[j]即data[j+dk]=data[1],j+dk=6,即data[6]=37
37.j=j-dk=1-5=-4
38.j>=0即-4>=0不成立,跳出第二个for循环
39.data[j+dk]=temp即data[-4+5]=data[1]=26
40.此时data[1]=26,data[6]=37,数组为:{12, 26, 64, 96, 75, 48, 37, 48, 54, 03}
41.k=k+1=6+1=742.k<n即7<10成立,接着第一个for循环
43.data[k]=data[7]=48
44.data[k-dk]=data[7-5]即data[2]=64
45.data[k]<data[k-dk]即48<64成立,进入if语句
46.temp=data[k]即temp=data[7]=48
47.j=k-dk=7-5=2
48.j>=0成立
49.data[j]=data[2]=64
50.temp<data[j]即48<64成立,进入第二个for循环
51.data[j+dk]=data[j]即data[j]=data[2],j+dk=7,即data[7]=48
52.j=j-dk=2-5=-3
53.j>=0即-3>=0不成立,跳出第二个for循环
54.data[j+dk]=temp即data[-3+5]=data[2]=48
55.此时data[2]=48,data[7]=64,数组为:{12, 26, 48, 96, 75, 48, 37, 64, 54, 03}
56.k=k+1=7+1=857.k<n即8<10成立,接着第一个for循环
58.data[k]=data[8]=54
59.data[k-dk]=data[8-5]=data[3]=96
60.data[k]<data[k-dk]即54<96成立,进入if语句
61.temp=data[k]即temp=data[8]=54
62.j=k-dk=8-5=3
63.j>=0成立
64.data[j]=data[3]=96
65.temp<data[j]即54<96成立,进入第二个for循环
66.data[j+dk]=data[j]即data[j+dk]=data[3],j+dk=8,即data[8]=96
67.j=j-dk=3-5=-2
68.j>=0即-2>=0不成立,跳出第二个for循环
69.data[j+dk]=temp即data[-2+5]=data[3]=54
70.此时data[3]=54,data[8]=96,数组为:{12, 26, 48, 54, 75, 48, 37, 64, 96, 03}
71.k=k+1=8+1=972.k<n即9<10成立,接着第一个for循环
73.data[k]=data[9]=3
74.data[k-dk]=data[9-5]=data[4]=75
75.data[k]<data[k-dk]即3<75成立,进入if语句
76.temp=data[k]即temp=data[9]=3
77.j=k-dk=9-5=4
78.j>=0成立
79.data[j]=data[4]=75
80.temp<data[j]即3<75成立,进入第二个for循环
81.data[j+dk]=data[j]即data[j+dk]=data[4],j+dk=9,即data[9]=75
82.j=j-dk=4-5=-1
83.j>=0即-1>=0不成立,跳出第二个for循环
84.data[j+dk]=temp即data[-1+5]=data[4]=3
85.此时data[4]=3,data[9]=75,数组为:{12, 26, 48, 54, 03, 48, 37, 64, 96, 75}
86.k=k+1=9+1=1087.k<n即10<10不成立,跳出第一个for循环
88.i++, i=0+1=1
89.dk=delta[i]=delta[1]=2
90.dk>0成立,接着while循环
91.k=delta[1]=292.k<n即2<10成立,进入第一个for循环
93.data[k]=data[2]=48
94.data[k-dk]=data[2-2]即data[0]=12
95.data[k]<data[k-dk]即48<12不成立,不进入if语句
96.k=k+1=2+1=397.k<n即3<10成立,进入第一个for循环
98.data[k]=data[3]=54
99.data[k-dk]=data[3-2]=data[1]=26
100.data[k]<data[k-dk]即54<26不成立,不进入if语句
101.k=k+1=3+1=4102.k<n即4<10成立,进入第一个for循环
103.data[k]=data[4]=3
104.data[k-dk]=data[4-2]=data[2]=48
105.data[k]<data[k-dk]即3<48成立,进入if语句
106.temp=data[k]=data[4]=3
107.j=k-dk=4-2=2
108.j>=0成立
109.data[j]=data[2]=48
110.temp<data[j]即3<48成立,进入第二个for循环
111.data[j+dk]=data[j]=data[2],j+dk=4,即data[4]=48
112.j=j-dk=2-2=0
113.j>=0成立
114.data[j]=data[0]=12
115.temp<data[j]即3<12成立,接着第二个for循环
116.data[j+dk]=data[j]=data[0],j+dk=2,即data[2]=12
117.j=j-dk=0-2=-2
118.j>=0即-2>=0不成立,跳出第二个for循环
119.data[j+dk]=temp即data[-2+2]=data[0]=3
120.此时data[4]=48,data[2]=12,data[0]=3,数组为:{03, 26, 12, 54, 48, 48, 37, 64, 96, 75}
121.k=k+1=4+1=5122.k<n即5<10成立,接着第一个for循环
123.data[k]=data[5]=48
124.data[k-dk]=data[5-2]=data[3]=54
125.data[k]<data[k-dk]即48<54成立,进入if语句
126.temp=data[k]=data[5]=48
127.j=k-dk=5-2=3
128.j>=0成立
129.data[j]=data[3]=54
130.temp<data[j]即48<54成立,进入第二个for循环
131.data[j+dk]=data[j]即data[j]=data[3],j+dk=5,即data[5]=54
132.j=j-dk=3-2=1
133.j>=0成立
134.data[j]=data[1]=26
135.temp<data[j]即48<26不成立,跳出第二个for循环
136.data[j+dk]=temp即data[1+2]=data[3]=48
137.此时data[5]=54,data[3]=48,数组为:{03, 26, 12, 48, 48, 54, 37, 64, 96, 75}
138.k=k+1=5+1=6122.k<n即6<10成立,接着第一个for循环
123.data[k]=data[6]=37
124.data[k-dk]=data[6-2]=data[4]=48
125.data[k]<data[k-dk]即37<48成立,进入if语句
126.temp=data[k]=data[6]=37
127.j=k-dk=6-2=4
128.j>=0成立
129.data[j]=data[4]=48
130.temp<data[j]即37<48成立,进入第二个for循环
131.data[j+dk]=data[j]=data[4],j+dk=6,即data[6]=48
132.j=j-dk=4-2=2
133.j>=0成立
134.data[j]=data[2]=12
135.temp<data[j]即37<12不成立,跳出第二个for循环
136.data[j+dk]=temp即data[2+2]=data[4]=37
137.此时data[6]=48,data[4]=37,数组为:{03, 26, 12, 54, 37, 48, 48, 64, 96, 75}
138.k=k+1=6+1=7139.k<n即7<10成立,接着第一个for循环
140.data[k]=data[7]=64
141.data[k-dk]=data[7-2]=data[5]=48
142.data[k]<data[k-dk]即64<48不成立,不进入if语句
143.k=k+1=7+1=8144.k<n即8<10成立,接着第一个for循环
145.data[k]=data[8]=96
146.data[k-dk]=data[8-2]=data[6]=48
147.data[k]<data[k-dk]即96<48不成立,不进入if语句
148.k=k+1=8+1=9149.k<n即9<10成立,接着第一个for循环
150.data[k]=data[9]=75
151.data[k-dk]=data[9-2]=data[7]=64
152.data[k]<data[k-dk]即75<64不成立,不进入if语句
153.k=k+1=9+1=10154.k<n即10<10不成立,跳出第一个for循环
155.i=i+1=1+1=2
156.dk=delta[2]=1
157.k=delta[i]=delta[2]=1158.k<n即1<10成立,接着第一个for循环
159.data[k]=data[1]=26
160.data[k-dk]=data[1-1]=data[0]=3
161.data[k]<data[k-dk]即26<3不成立,不进入if语句
162.k=k+1=2163.k<n即2<10成立,接着第一个for循环
164.data[k]=data[2]=12
165.data[k-dk]=data[1]=26
166.data[k]<data[k-dk]即12<26成立,进入if语句
167.temp=data[k]=data[2]=12
168.j=k-dk=2-1=1
169.j>=0成立
170.data[j]=data[1]=26
171.temp<data[j]即12<26成立,进入第二个for循环
172.data[j+dk]=data[j]即data[j+dk]=data[1],j+dk=2,即data[2]=26173.j=j-dk=1-1=0
174.j>=0成立
175.data[j]=data[0]=3
176.temp<data[j]即12<3不成立,跳出第二个for循环
178.data[j+dk]=temp即data[0+1]=data[1]=12
179.此时data[2]=26,data[1]=12,data[0]=3,数组为:{03, 12, 26, 54, 48, 48, 37, 64, 96, 75}
180.k=k+1=3181.k<n即3<10成立,接着第一个for循环
182.data[k]=data[3]=54
183.data[k-dk]=data[3-1]=data[2]=26
184.data[k]<data[k-dk]即54<26不成立,不进入if语句
185.k=k+1=4182.k<n即4<10成立,接着第一个for循环
183.data[k]=data[4]=48
184.data[k-dk]=data[4-1]=data[3]=54
185.data[k]<data[k-dk]即48<54成立,进入if语句
186.temp=data[k]=data[4]=48
187.j=k-dk=4-1=3
188.j>=0成立
189.data[j]=data[3]=54
190.temp<data[j]即48<54成立,进入第二个for循环
191.data[j+dk]=data[j]即data[j]=data[3],j+dk=4,即data[4]=54
192.j=j-dk=3-1=2
193.j>=0成立
194.data[j]=data[2]=26
195.temp<data[j]即48<26不成立,跳出第二个for循环
196.data[j+dk]=temp即data[2+1]=data[3]=48
197.此时data[4]=54,data[3]=48,数组为:{03, 12, 26, 48, 54, 48, 37, 64, 96, 75}
198.k=k+1=4+1=5199.k<n即5<10成立,接着第一个for循环
200.data[k]=data[5]=48
201.data[k-dk]=data[5-1]=data[4]=54
202.data[k]<data[k-dk]即48<54成立,进入if语句
203.temp=data[k]=data[5]=48
204.j=k-dk=5-1=4
205.j>=0成立
206.data[j]=data[4]=54
207.temp<data[j]即48<54成立,进入第二个for循环
208.data[j+dk]=data[j]即data[j]=data[4],j+dk=5,即data[5]=54
209.j=j-dk=4-1=3
210.j>=0成立
211.data[j]=data[3]=48
212.temp<data[j]即48<48不成立,跳出第二个for循环
213.data[j+dk]=temp即data[3+1]=data[4]=48
214.此时data[5]=54,data[4]=48,数组为{03, 12, 26, 48, 48, 54, 37, 64, 96, 75}......

这篇关于【软考】希尔排序算法分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1150429

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时