VBA内存二维数组对象的多key稳定排序算法

Zamyi

搞什么呢？
把数据源用＝int(rnd*10)，看看什么效果吧！
还是先看我的程序，理解完再说吧。
要稳定，简单的很，增加一个Key，按原来序号再排一次。或者干脆用稳定的快速排序作为基础排序。

香川群子

Zamyi 发表于 2015-12-5 20:35
搞什么呢？
把数据源用＝int(rnd*10)，看看什么效果吧！
还是先看我的程序，理解完再说吧。

【用稳定的快速排序作为基础排序】……你错了，快速排序并非【稳定性排序算法】。

我知道你早已写过二维数组多key排序代码(使用了快速排序基础算法)

但我不能确定你的代码是否能满足稳定多key排序的要求。(光看你的代码，应该是做不到的。)

…………
事实上，为了满足排序速度的要求，我使用的排序算法核心代码，也正是快速排序算法。
这一点并无差异。

新的附件中，测试代码test2，也确实使用了=Int(Rnd * 10) 来赋值。
排序结果确证是稳定的。

Zamyi

香川群子 发表于 2015-12-5 21:24
【用稳定的快速排序作为基础排序】……你错了，快速排序并非【稳定性排序算法】。

我知道你早已写过二 ...

经典的快速排序是非稳定的，但快速排序可以实现稳定的，但需付出多用内存及速度作为代价。这一点很多人都读死教科书。有空写一个吧。

香川群子

Zamyi 发表于 2015-12-5 21:34
经典的快速排序是非稳定的，但快速排序可以实现稳定的，但需付出多用内存及速度作为代价。这一点很多人都 ...

理论上，如果一个排序区间中相同内容值只有唯一的1个t(1组n个都是=t)，那么以此t为检查比较值进行快速排序时，结果是稳定的……这是一个可以利用的特点。

PLINQ

我没看代码，这个其实很好理解
比如有一张按学号序列的成绩表原始数据，现在要按照总成绩降序排序，分数相同的学号在前的排在前——一个简单的双关键字排序问题。
其实，这里要求 分数相同学号在前的排在前 换个高端的说法，就是要求按照分数进行稳定排序
所以处理稳定排序的方法也和处理这种要求的方法一样 把原来的序号加进去排就是了
伪代码：（VB6/VBA不支持Return语句，相当于FunctionName=XXX:Exit Function)(并且假设Key可以通过 “-” 运算进行大小比较）
Private Function Compare(entry1,entry2) As Integer
        '# 按Key1升序排列
        r= entry1.Key1-entry2.Key2
          If r<>0 Then Return r

        '# 按key2 降序排列
        r=entry1.Key1-entry2.Key2
        If r<>0 Then Return -r

        '…… ……

        '# 稳定 按Index排序
        r=entry1.Index-entry2.Index
        Return r
End Function

sunny_8848

学习一下，上次还到处找人求助去重，排序

香川群子

PLINQ 发表于 2015-12-5 22:13
我没看代码，这个其实很好理解
比如有一张按学号序列的成绩表原始数据，现在要按照总成绩降序排序，分数相 ...

明白了。你说的对。

看来是我把问题搞复杂了。
根源是受工作表排序做法的影响。如果多key超过3，那么工作表排序需要改为单列倒序排序。

而事实上，无需倒序排序，任可按正常排序权重顺序排，只要最后进行稳定排序处理即可。
Zamyi 说的是对的。他的代码效率高多了。

香川群子

最后是按照Zamyi的方法重新写了代码。

多key排序时，按我原先的方法，每单次排序耗时查不了多少，
而按Zamyi和PLINQ的思路写的代码，第1次排序耗时最多，这以后的耗时将很快减少……因为多key重复(内容相同项将越来越少。)

qx-liuwx

香川群子 发表于 2015-12-6 15:30
最后是按照Zamyi的方法重新写了代码。

还是需要老师帮忙：上了个附件
选取有效区域数据直接排序后输出，谢谢！

香川群子

qx-liuwx 发表于 2015-12-7 11:45
还是需要老师帮忙：上了个附件
选取有效区域数据直接排序后输出，谢谢！

按你附件的要求，用我的二维数组多key排序写了2个代码，比工作表排序大约快3倍。

方法-1、把cx列也列入排序。这样一共是4个key参与排序。
读取数据时，先要把第1列从文本型转为数值型。

排序参数：
sr = Array(102, 2, 103, 2, 1, 2, 2, 1)……102列cx降序、103列cy降序、第1列降序、第2列升序。
nr = szpx1(ar, 2, sr)……此处2代表前面2行不参与排序，从第3行开始。

过程中，第一次cx排序后，忽略后面空值继续。
最后输出有效结果955行。

………………

方法-2、先读取cx列中有效行对应3列写入数组，这样一共只要3个key参与排序。
读取数据时，也要把第1列从文本型转为数值型。

排序参数：
sr = Array(1, 2, 2, 2, 3, 1)……第1列cy列降序、第2列a列降序、第3列b列升序。
nr = szpx2(ar, 0, k - 1, sr)……行范围从0,k-1 （k为有效cx列行数）
最后输出有效结果955行。

…………
结果是，第2种方法速度更快一些。