如何在Universe BASIC中高效实现多字段排序？

我使用的Universe BASIC版本没有内置SORT函数，需要从包含100+条值标记分隔条目的记录文件中，按字段A、B、C的顺序排序。目前我用LOCATE、INS函数加循环实现了仅按A、B字段排序的逻辑，但代码已经变得混乱不堪，时间复杂度至少是O(n²)，请问有没有更高效的排序方案？

当前实现代码：

*FOR EXAMPLE A]B]B]A
*            3]4]3]1
*NEED TO BE SORTED AS
             A]A]B]B
             1]3]3]4
*IN THE FORM OF BY 1ST FIELD, BY 2ND FIELD
SORTED.ARRAY.1=""
UNSORTED.ARRAY.2=""
READ XX.REC FROM XX.FILE.VARIABLE,KEY ELSE
END
1ST.FIELD.TO.SORT=XX.REC<1>
2ND.FIELD.TO.SORT=XX.REC<2>
X=DCOUNT(1ST.FIELD.TO.SORT,@VM)
FOR I=1 TO X
Z1=1ST.FIELD.TO.SORT<1,I>
Z2=2ND.FIELD.TO.SORT<2,I>
LOCATE Z1 IN SORTED.ARRAY.1<1> BY "DR" SETTING POS THEN
     INS Z1 BEFORE SORTED.ARRAY.1<1,POS>
     INS Z2 BEFORE UNSORTED.ARRAY.2<1,POS>
END ELSE
    LOCATE Z1 IN SORTED.ARRAY.1<1> BY "DR" SETTING POS ELSE
     INS Z1 BEFORE SORTED.ARRAY.1<1,POS>
     INS Z2 BEFORE UNSORTED.ARRAY.2<1,POS>
    END
END
NEXT X
*THIS COMPLETE 1ST SORTED ARRAY, NOW NEED TO SLICE THE THE 1ST ARRAY THAT CONSIST OF THE SAME ITEM
*FOR EXAMPLE A]A]B]B] NEED TO CAPTURE THE START POSITION OF "A" AND END POSTION OF "A" THEN SORT THE *2ND FIELD
FOR I2=1 TO X1
    Z1=SORTED.ARRAY.1<1,I2>
    ORIG.START.POS=I2
    FOR I3=ORIG.START.POS TO X+1
        IF Z1#SORTED.ARRAY<1,I3> THEN
            CUT.OFF.POS.OF.SAME.ITEM=I3
            LAST.INDEX.OF.SAME.ITEM=I3-1
            EXIT
        END
    NEXT I3
    TEMP.STORAGE=""
    FOR I4=ORIG.START.POS TO LAST.INDEX.OF.SAME.ITEM
    ITEM.TO.SORT=UNSORTED.ARRAY.2<1,I4>
    LOCATE ITEM.TO.SORT IN TEMP.STORAGE<1> BY "DR" SETTING POS THEN
        INS ITEM.TO.SORT BEFORE TEMP.STORAGE<1,POS>
    END ELSE
        LOCATE ITEM.TO.SORT IN TEMP.STORAGE<1> BY "DR" SETTING POS ELSE
        INS ITEM.TO.SORT BEFORE TEMP.STORAGE<1,POS>
        END
    END
COUNT=1
FOR I5=ORIG.START.POS TO LAST.INDEX.OF.SAME.ITEM
    CUR.ITEM=TEMP.STORAGE<1,COUNT>
    UNSORTED.ARRAY.2<1,I5>=CUR.ITEM
    COUNT=COUNT+1
NEXT I5
ORIG.START.POS=CUT.OFF.POS.OF.SAME.ITEM
NEXT I2

针对Universe BASIC无内置SORT函数的场景，推荐两种更高效的思路，时间复杂度可降至O(n log n)级别：

1. 复合排序键+快速排序实现 #

核心思路是把需要排序的多个字段拼接成复合排序键，同时保留原始记录的索引，通过快速排序对复合键数组排序后，再根据索引重组原始数据。这种方案效率最高，适合记录量较大的场景。

示例代码：

* 读取原始记录，假设XX.REC中<1>是字段A数组，<2>是字段B数组，<3>是字段C数组，用@VM分隔条目
READ XX.REC FROM XX.FILE.VARIABLE, KEY ELSE STOP "记录读取失败"
REC.COUNT = DCOUNT(XX.REC<1>, @VM)

* 构建复合排序键数组和原始索引数组
SORT.KEYS = ""
INDEX.ARRAY = ""
FOR I = 1 TO REC.COUNT
    * 拼接复合键：字段A + 格式化后的字段B + 字段C
    * 数值类型字段需补前导零，保证排序时的数值顺序正确（比如字段B是数值，格式化为10位长度）
    KEY.A = XX.REC<1, I>
    KEY.B = FMT(XX.REC<2, I>, "R10") ;* R表示右对齐，补前导零到10位
    KEY.C = XX.REC<3, I>
    COMPOSITE.KEY = KEY.A : KEY.B : KEY.C
    
    SORT.KEYS<1, I> = COMPOSITE.KEY
    INDEX.ARRAY<1, I> = I
NEXT I

* 调用快速排序子程序
CALL QUICK.SORT(SORT.KEYS, INDEX.ARRAY, 1, REC.COUNT)

* 根据排序后的索引重组结果数组
SORTED.A = ""
SORTED.B = ""
SORTED.C = ""
FOR I = 1 TO REC.COUNT
    ORIG.IDX = INDEX.ARRAY<1, I>
    SORTED.A<1, I> = XX.REC<1, ORIG.IDX>
    SORTED.B<1, I> = XX.REC<2, ORIG.IDX>
    SORTED.C<1, I> = XX.REC<3, ORIG.IDX>
NEXT I

* ------------------------------
* 快速排序子程序（Universe BASIC兼容）
* ------------------------------
SUBROUTINE QUICK.SORT(KEYS, INDICES, LOW, HIGH)
    LOCAL PIVOT.KEY, LEFT, RIGHT, TEMP.KEY, TEMP.IDX
    
    IF LOW >= HIGH THEN RETURN
    
    * 取中间位置作为基准键
    PIVOT.KEY = KEYS<1, (LOW + HIGH) // 2>
    LEFT = LOW
    RIGHT = HIGH
    
    DO WHILE LEFT <= RIGHT
        * 找到左侧大于等于基准键的位置
        DO WHILE KEYS<1, LEFT> < PIVOT.KEY AND LEFT <= HIGH
            LEFT += 1
        LOOP
        * 找到右侧小于等于基准键的位置
        DO WHILE KEYS<1, RIGHT> > PIVOT.KEY AND RIGHT >= LOW
            RIGHT -= 1
        LOOP
        
        IF LEFT <= RIGHT THEN
            * 交换键和对应的原始索引
            TEMP.KEY = KEYS<1, LEFT>
            KEYS<1, LEFT> = KEYS<1, RIGHT>
            KEYS<1, RIGHT> = TEMP.KEY
            
            TEMP.IDX = INDICES<1, LEFT>
            INDICES<1, LEFT> = INDICES<1, RIGHT>
            INDICES<1, RIGHT> = TEMP.IDX
            
            LEFT += 1
            RIGHT -= 1
        END IF
    LOOP
    
    * 递归排序左右子数组
    CALL QUICK.SORT(KEYS, INDICES, LOW, RIGHT)
    CALL QUICK.SORT(KEYS, INDICES, LEFT, HIGH)
END

2. 优化版冒泡排序（实现简单） #

如果不想实现复杂的快速排序，可采用优化后的冒泡排序，加入已排序标记提前终止循环，同时直接操作包含所有字段的条目数组，避免拆分多个数组维护，代码更简洁。

示例代码：

READ XX.REC FROM XX.FILE.VARIABLE, KEY ELSE STOP "记录读取失败"
REC.COUNT = DCOUNT(XX.REC<1>, @VM)

* 构建包含所有字段的条目数组，每个条目用@FM分隔A、B、C字段
ITEM.ARRAY = ""
FOR I = 1 TO REC.COUNT
    ITEM.ARRAY<1, I> = XX.REC<1, I> : @FM : XX.REC<2, I> : @FM : XX.REC<3, I>
NEXT I

* 优化版冒泡排序：加入SWAPPED标记，无交换时提前退出
SWAPPED = 1
FOR I = 1 TO REC.COUNT - 1
    IF SWAPPED = 0 THEN EXIT
    SWAPPED = 0
    
    FOR J = 1 TO REC.COUNT - I
        * 拆分当前条目和下一条目的字段
        CUR.A = ITEM.ARRAY<1, J><1>
        CUR.B = ITEM.ARRAY<1, J><2>
        CUR.C = ITEM.ARRAY<1, J><3>
        
        NEXT.A = ITEM.ARRAY<1, J+1><1>
        NEXT.B = ITEM.ARRAY<1, J+1><2>
        NEXT.C = ITEM.ARRAY<1, J+1><3>
        
        * 按A→B→C的优先级比较排序
        IF CUR.A > NEXT.A THEN
            * 交换条目
            TEMP = ITEM.ARRAY<1, J>
            ITEM.ARRAY<1, J> = ITEM.ARRAY<1, J+1>
            ITEM.ARRAY<1, J+1> = TEMP
            SWAPPED = 1
        END ELSEIF CUR.A = NEXT.A THEN
            IF CUR.B > NEXT.B THEN
                TEMP = ITEM.ARRAY<1, J>
                ITEM.ARRAY<1, J> = ITEM.ARRAY<1, J+1>
                ITEM.ARRAY<1, J+1> = TEMP
                SWAPPED = 1
            END ELSEIF CUR.B = NEXT.B THEN
                IF CUR.C > NEXT.C THEN
                    TEMP = ITEM.ARRAY<1, J>
                    ITEM.ARRAY<1, J> = ITEM.ARRAY<1, J+1>
                    ITEM.ARRAY<1, J+1> = TEMP
                    SWAPPED = 1
                END IF
            END IF
        END IF
    NEXT J
NEXT I

* 拆分排序后的条目到结果数组
SORTED.A = ""
SORTED.B = ""
SORTED.C = ""
FOR I = 1 TO REC.COUNT
    SORTED.A<1, I> = ITEM.ARRAY<1, I><1>
    SORTED.B<1, I> = ITEM.ARRAY<1, I><2>
    SORTED.C<1, I> = ITEM.ARRAY<1, I><3>
NEXT I

方案对比 #

• 快速排序方案：时间复杂度O(n log n)，适合100条以上的记录，效率远高于原O(n²)的插入式排序，且可灵活扩展到更多排序字段；
• 优化冒泡排序：实现简单，代码易维护，最坏情况时间复杂度仍为O(n²)，但实际运行中因提前终止循环，效率比原代码提升明显，适合快速落地小批量数据排序。

内容的提问来源于stack exchange，提问作者chuackt