寻求Fortran排名子程序及前M大值部分排序实现方案

一、全降序排序的原索引返回子程序 #

要实现返回降序排序后的原数组索引，核心是将数组元素与其原始索引绑定，对绑定结构按元素值降序排序后提取索引即可。以下是兼容Fortran 90及以上版本的实现：

module sort_indices_mod
    implicit none

    private
    public :: sort_indices_desc

    ! 存储数组值与对应原始索引的派生类型
    type :: val_idx
        real :: val
        integer :: idx
    end type val_idx

contains

    ! 降序排序的比较函数，供qsort调用
    function compare_desc(a, b) result(res)
        type(val_idx), intent(in) :: a, b
        integer :: res
        if (a%val > b%val) then
            res = -1  ! a值更大则排在前，返回-1调整qsort顺序
        else if (a%val < b%val) then
            res = 1
        else
            res = 0
        end if
    end function compare_desc

    ! 主子程序：输入一维实数组，返回降序排序后的原索引数组
    subroutine sort_indices_desc(arr, idx_arr)
        real, intent(in) :: arr(:)
        integer, intent(out) :: idx_arr(:)
        type(val_idx), allocatable :: temp(:)
        integer :: n, i

        n = size(arr)
        if (size(idx_arr) /= n) error stop "索引数组长度必须与输入数组匹配"

        allocate(temp(n))
        do i = 1, n
            temp(i)%val = arr(i)
            temp(i)%idx = i
        end do

        call qsort(temp, compare_desc)

        do i = 1, n
            idx_arr(i) = temp(i)%idx
        end do

        deallocate(temp)
    end subroutine sort_indices_desc

end module sort_indices_mod

使用示例：

program test_sort_indices
    use sort_indices_mod
    implicit none
    real :: arr(5) = [3.1, 1.5, 4.2, 0.8, 2.9]
    integer :: idx(5)

    call sort_indices_desc(arr, idx)
    print *, "原数组: ", arr
    print *, "降序索引: ", idx
    ! 输出：原数组: 3.100000 1.500000 4.200000 0.8000000 2.900000
    ! 降序索引: 3 1 5 2 4
end program test_sort_indices

二、部分排序：返回前M个最大值的原索引 #

若仅需前M个最大元素的索引（其余元素顺序无关），无需全排序，用选择排序思路更高效（时间复杂度O(n*M)，适合M远小于n的场景）：

module partial_sort_mod
    implicit none

    private
    public :: top_m_indices_desc

contains

    ! 子程序：输入一维实数组和M，返回前M个最大值的原索引（降序排列）
    subroutine top_m_indices_desc(arr, M, top_idx)
        real, intent(in) :: arr(:)
        integer, intent(in) :: M
        integer, intent(out) :: top_idx(:)
        real, allocatable :: temp_arr(:)
        integer, allocatable :: temp_idx(:)
        integer :: n, i, j, max_pos

        n = size(arr)
        if (M < 1 .or. M > n) error stop "M必须介于1和数组长度之间"
        if (size(top_idx) /= M) error stop "结果索引数组长度必须等于M"

        allocate(temp_arr(n), temp_idx(n))
        temp_arr = arr
        temp_idx = [(i, i=1, n)]

        do i = 1, M
            max_pos = i
            do j = i+1, n
                if (temp_arr(j) > temp_arr(max_pos)) then
                    max_pos = j
                end if
            end do
            ! 交换当前位置与最大值位置的元素和索引
            call swap(temp_arr(i), temp_arr(max_pos))
            call swap(temp_idx(i), temp_idx(max_pos))
            top_idx(i) = temp_idx(i)
        end do

        deallocate(temp_arr, temp_idx)
    end subroutine top_m_indices_desc

    ! 通用交换辅助子程序
    subroutine swap(a, b)
        class(*), intent(inout) :: a, b
        class(*), allocatable :: temp
        temp = a
        a = b
        b = temp
    end subroutine swap

end module partial_sort_mod

使用示例：

program test_partial_sort
    use partial_sort_mod
    implicit none
    real :: arr(5) = [3.1, 1.5, 4.2, 0.8, 2.9]
    integer :: top_idx(2)

    call top_m_indices_desc(arr, 2, top_idx)
    print *, "原数组: ", arr
    print *, "前2个最大值的索引: ", top_idx
    ! 输出：原数组: 3.100000 1.500000 4.200000 0.8000000 2.900000
    ! 前2个最大值的索引: 3 1
end program test_partial_sort

说明 #

• 全排序实现借助Fortran内置qsort和自定义比较函数，兼容性强；
• 部分排序针对小M场景优化，避免无意义的全排序操作；
• 若需处理整数数组，只需修改派生类型和子程序中的变量类型即可适配。

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