【算法表达】一种排序算法的分类、纠错与完善#排序算法#
vb吧
全部回复
仅看楼主
level 11
余思培 楼主
作为一名业余的VB爱好者,我学习VB并不是完全按照资料书上的顺序来安排学习的,而是任务导向型,即预设一个任务,然后逐渐学习通过完成既定任务的过程中所需要的知识和技巧,再加上在上大学之前我一直没有充裕的时间来学习VB,所以到现在我才开始接触排序算法。
回归正题,当我需要排序算法时,我最先想到的是冒泡排序法,但我又想挑战一下,所以我结合了所查找到的一些常见的排序的基本思路,我写出了此算法的程序表达。(由于回家没带电脑,所以没有试运行。)
所以希望大佬们能看看此算法表达属于那种算法或其变种,有什么逻辑错误或表达错误,还有什么地方值得改进。(使用中文变量名是因为更方便于交流时的算法理解)
2020年02月13日 15点02分 1
level 11
余思培 楼主
算法表达:
Sub 自定义排序(n As Long,ByRef 源数组() As Integer)
'声明变量
Dim 转存数组(1 to n) As Long
Dim 顺序标记(1 to n) As Long
Dim 任务标记(1 to n) As Long
Dim 相等校验 As Long
Dim 完成标记 As Long
Dim 当前完成标记 As Long
Dim 当前状态标记 As Long
Dim 任务组平均数 As Long
Dim 任务数量 As Long
Dim i As Long
'初始化
For i = 1 to n
顺序标记(i) = 1
Next
完成标记 = 1
'排序算法
Do
当前完成标记 = 0
For 当前状态标记 = 1 to 完成标记
任务数量 = 0
任务组平均数 = 0
For i = 1 to n
If 顺序标记(i) = 当前状态标记 Then
任务数量 = 任务数量 + 1
任务标记(j) = i
End If
Next
If 任务数量 = 1 Then
当前完成标记 = 当前完成标记 + 1
顺序标记(任务标记(1)) = 当前完成标记
Else
当前完成标记 = 当前完成标记 + 2
For i = 1 to 任务数量
任务组平均数 = 任务组平均数 + 源数组(任务标记(i))
Next
任务组平均数 = 任务组平均数 \ 任务数量
For i = 1 to 任务数量
If 源数组(任务标记(i)) > 任务组平均数 Then
顺序标记(任务标记(i)) = 当前完成标记 - 1
Else
顺序标记(任务标记(i)) = 当前完成标记
End If
Next
'相等校验
相等校验 = 0
For i = 1 to 任务数量
If 顺序标记(任务标记(i)) = 当前完成标记
相等校验 = 相等校验 + 1
End If
Next
If 相等校验 = 任务数量 Then
当前完成标记 = 当前完成标记 - 2
For i = 1 to 任务数量
顺序标记(任务标记(i)) = 当前完成标记 + i
Next
当前完成标记 = 当前完成标记 + 任务数量
End If
End If
Next
完成标记 = 当前完成标记
Loop Until 完成标记 = n
'交换顺序
For i = 1 to n
转存数组(i) = 源数组(i)
Next
For i = 1 to n
源数组(i) = 转存数组(顺序标记(i))
Next
End Sub
2020年02月13日 15点02分 2
level 11
余思培 楼主
算法思路:
1.将一组无序数据根据平均数与平均数的比对结果进行二分,并根据由大到小的顺序进行标记。
2.后根据的顺序标记生成无序任务组,并对无序任务组进行前一步操作。操作完成后添加完成标记。
重复此操作直到完成标记等于原始数据总量
3.最后根据顺序标记排列源数据
注:针对相等数据的平均数是其本身,故增加了相等校验
2020年02月13日 15点02分 3
level 11
余思培 楼主
【缺陷】
■描述:无序数据的综合不得大于长整型的数值上限
■完善方案:改变平均数的计算方式
□方案缺陷:大大降低排序效率
2020年02月13日 15点02分 4
level 9
继续更新呀,楼主。
2020年02月14日 02点02分 5
level 11
余思培 楼主
算法的思路其实来自于霍夫曼编码(因为其实我排序的目的也是为了构建霍夫曼编码),仿照其建立二叉树,我也将无序数据不断二分,最终完成排序。
但实际上我并不知道这种算法是什么(刚刚我去搜索了一下,应该是属于排序算法,并据此又有了新的思路),在二分的时候不一定严格以平均数来进行二分,可以选取一个任意在范围内的值即可,所以......
(PS:我发帖其实是希望有大佬给予指导和帮助)
2020年02月14日 04点02分 6
level 11
余思培 楼主
这是稍微修改后的代码部分,将二分的标准变为中位数,并将原相等校验调整为相等校验及中位数最大校验。
另前面的代码中有个变量j其实是变量[任务数量],变量名中文化时没改全
2020年02月14日 05点02分 7
level 11
余思培 楼主
修改部分代码:
当前完成标记 = 当前完成标记 + 2
If 任务数量 Mod 2 = 1 Then
任务组中位数 = 源数组((任务数量 + 1) \ 2)
Else
任务组中位数 = (源数组(任务数量 \ 2) + 源数组(任务数量 \ 2 + 1))
End If
For i = 1 to 任务数量
If 源数组(任务标记(i)) > 任务组中位数 Then
顺序标记(任务标记(i)) = 当前完成标记 - 1
Else
顺序标记(任务标记(i)) = 当前完成标记
End If
Next
'相等校验及中位数最大校验
标记校验 = 0
相等校验 = True
For i = 1 to 任务数量
If 顺序标记(任务标记(i)) = 当前完成标记 Then
标记校验 = 标记校验 + 1
End If
Next
If 标记校验 = 任务数量 Then
For i = 1 to 任务数量
If 源数组(任务标记(i)) <> 任务组中位数 Then
相等校验 = False
Exit For
End If
Next
If 相等校验 = True Then
当前完成标记 = 当前完成标记 - 2
For i = 1 to 任务数量
顺序标记(任务标记(i)) = 当前完成标记 + i
Next
当前完成标记 = 当前完成标记 + 任务数
Else
顺序标记(任务标记((任务数量 + 1) \ 2))
Next
End If
2020年02月14日 05点02分 8
//PS:本来准备贴修改后全码,但贴不全,所以只贴出了修改后的代码 ■修改后 ●变量[相等校验]更名为[标记校验] ●新声明一个Boolean类型变量[相等校验]
2020年02月14日 05点02分
level 15
二分的话应该是快速排序的思路
从你这个描述来看,我感觉差不多就是快速排序了(不过一般的排序算法都可以原位排序,不需要借助转存数组)
代码没仔细看
2020年02月15日 08点02分 10
刚刚查了下,确实属于快速排序的非递归(循环体)非就地排序的(使用了辅助空间)稳定(由于算法原因,存在相等校验,故相同数值的相对位置不变)实现。另,问下大佬,除三数取中,还有快速排序还有哪些常用的优化(非递归实现的优化),还有大量长整形数据取平均数怎么算
2020年02月15日 09点02分
@余思培 我也不是大佬,对算法之类的也没什么研究,你问的这些我都不清楚了……
2020年02月15日 10点02分
level 11
余思培 楼主
【调整】
1.在此算法中,比对数取中位数没有实际意义,故更改为取两个不相等的数的平均数(整除)
2.将相等校验提前到取不相等两数
3.由于两不相等数的平均值不存在最大数小于比对数,故取消原中位数最大校验
【其他】
1.此算法属于快速排序(可能吧,不太确定)的一种程序表达
2.理论上无序组中取平均数作为比对数可以减少比对次数,但由于数学逻辑不太好加VB语言学习不到位,所产生的算法表达存在较大问题故放弃比对数使用平均数
3.此次调整后由于存在取二值平均数,故存在二值和不得大于长整型数值上限的问题
2020年02月15日 08点02分 11
level 11
余思培 楼主
11楼超出截图部分
2020年02月15日 08点02分 12
level 11
余思培 楼主
很多时候不实际操作很难找出逻辑问题(所以这段时间有什么想法难以实现和验证),就这个核心思想取自快速排序的严重劣化版的快速排序而言,刚写出时,我是真的发现不了问题,而且无法验证,实际上出了很多问题。最近我实在闲着无聊就用Aide学了下Java,然后我想尝试在Java上复现我自己写的这个劣化快排,然后问题就浮现出来了,楼下我会统计我已经发现的问题和初步的修改方案,望大家能够指点。
2020年05月04日 09点05分 14
level 11
余思培 楼主
●由于没有快排的就地排序的思路,所以我写得快排实际上使用的是辅助数组进行排序,但最近我重新审视我写得算法逻辑时,顺序标记数组会在排序过程中被干扰,以致效率降低或无法排序。
2020年05月04日 09点05分 15
level 11
余思培 楼主
●对于某些特殊情况的考虑不充分,以至于可能会出现无法排序或出不了循环的情况。
2020年05月04日 09点05分 16
1 2 尾页