stdlib_sorting 模块

排序概述

数据集合的排序在这些集合的分析中很有用。由于缺乏泛型和有限的多态性，在当前的 Fortran 中，为任意数据类型的任意集合提供排序例程是不切实际的。但是，Fortran 的数组是迄今为止使用最广泛的集合，并且任意数据类型的数组通常可以根据单个内在类型组件进行排序。因此，Fortran 标准库提供了一个模块 stdlib_sorting，其中包含用于对简单内在数值类型数组进行排序的过程，即不同种类的整数和实数、默认假定长度字符以及 stdlib_string_type 模块的 string_type 类型。

模块概述

模块 stdlib_sorting 定义了几个公共实体，两个默认整数参数 int_index 和 int_index_low，以及四个重载子程序：ORD_SORT、SORT、RADIX_SORT 和 SORT_INDEX。重载子程序还分别为对应于不同类型数组参数的版本提供了几个特定的名称。

参数 int_index 和 int_index_low

参数 int_index 和 int_index_low 用于指定用于索引各种数组的整数类型。目前，模块分别将 int_index 和 int_index_low 设置为 stdlib_kinds 模块中的 int64 和 int32 的值。

模块子程序

stdlib_sorting 模块提供了三个不同的重载子程序，用于对三种不同类型的数组数据进行排序

• ORD_SORT 用于对具有在排序前部分排序的重要部分的简单内在数据数组进行排序；
• SORT_INDEX 基于 ORD_SORT，但除了对输入数组进行排序外，它还返回将原始数组映射到其排序版本的索引。这使得相关数组能够以相同的方式重新排序；
• SORT 用于对在排序前实际上是无序的简单内在数据数组进行排序；
• RADIX_SORT 用于对固定宽度内在数据类型（整数和实数）进行排序。

许可证

Fortran 标准库根据 MIT 许可证分发。但是，库的组件可能基于具有其他许可限制的代码。特别是 ORD_SORT、SORT_INDEX 和 SORT 是具有其自身分发限制的代码的翻译。

ORD_SORT 和 SORT_INDEX 子程序本质上是将 Rust 语言的“Rust 排序”翻译成 Fortran 2008，该语言作为 slice.rs 的一部分分发。slice.rs 文件的头部将其许可要求列为

Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
file at the top-level directory of this distribution and at
https://rust-lang.net.cn/COPYRIGHT.

Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
https://apache.ac.cn/licenses/LICENSE-2.0> or the MIT license
<LICENSE-MIT or https://open-source.org.cn/licenses/MIT>, at your
option. This file may not be copied, modified, or distributed
except according to those terms.

因此，slice.rs 代码的许可证与在 MIT 许可证下在 Fortran 标准库中使用修改后的代码版本兼容。

SORT 子程序本质上是将 David Musser 的 [introsort]((http://www.cs.rpi.edu/~musser/gp/introsort.ps) 翻译成 Fortran 2008。David Musser 已授权在 MIT 许可证下将 introsort 的变体包含在 Fortran 标准库中，前提是我们引用

Musser, D.R., “Introspective Sorting and Selection Algorithms,”
Software—Practice and Experience, Vol. 27(8), 983–993 (August 1997).

作为算法的官方来源。

ORD_SORT 子程序

ORD_SORT 是 [slice.rs] (https://github.com/rust-lang/rust/blob/90eb44a5897c39e3dff9c7e48e3973671dcd9496/src/liballoc/slice.rs) 中包含的“Rust 排序”排序算法的翻译。“Rust 排序”反过来又受到 Tim Peters 为 Python 语言创建的 [timsort 算法] (http://svn.python.org/projects/python/trunk/Objects/listsort.txt) 的启发。ORD_SORT 是一种混合稳定的比较算法，结合了 归并排序 和 插入排序。在对随机数据进行排序时，它的最坏情况运行时性能始终为 O(N Ln(N))，在这些数据上的性能比 SORT 慢约 15-25%。但是，它在部分排序的数据上的性能比 SORT 好得多，在均匀递增或递减的数据上具有 O(N) 性能。

在按升序排序时，ORD_SORT 从尾部开始遍历数组，试图识别数组中的“运行”，其中运行要么是均匀递减的序列 ARRAY(i-1) > ARRAY(i)，要么是非递减的 ARRAY(i-1) <= ARRAY(i) 序列。首先，分隔的递减序列按顺序反转。然后，如果序列的元素少于 MIN_RUN 个，则使用 插入排序 将数组中先前的元素添加到运行中，直到运行包含 MIN_RUN 个元素或数组完全处理完毕。识别每个运行后，运行的起始位置和长度将被推送到堆栈上，然后使用 合并 处理堆栈，直到它满足堆栈不变式

1. len(i-2) > len(i-1) + len(i)
2. len(i-1) > len(i)

确保堆栈的处理在最坏情况下为 O(N Ln(N)) 阶。但是，由于识别了递减和非递减运行，因此结构化数据的处理速度可能会快得多，均匀递减或非递减数组的处理速度为 O(N) 阶。我们的测试结果表明，根据编译器的不同，ORD_SORT 在纯随机数据上的速度比 SORT 慢约 25%，但在高度结构化数据上可以比 SORT 快 Ln(N) 倍。作为修改后的 归并排序，ORD_SORT 需要使用一个“暂存”数组，该数组可以作为可选的 work 参数提供，也可以在堆栈上内部分配。

通过提供参数 reverse = .true.，还可以按降序对数组进行排序。

SORT_INDEX 子程序

SORT 和 ORD_SORT 子程序可以对内在类型的 1 阶孤立数组进行排序，但对相关数据的协调排序（例如，多个相关的 1 阶数组、更高阶数组或派生类型的数组）没有任何作用。对于此类相关数据，有用的是一个索引数组，它将 1 阶数组映射到其排序形式。对于此类排序，稳定的排序很有用，因此该模块提供了一个子程序 SORT_INDEX，它除了对输入数组进行排序外，还基于 ORD_SORT 算法生成此类索引数组。

SORT_INDEX 的逻辑与 ORD_SORT 的逻辑相似，并增加了额外的管理工作以使索引数组与输入数组的排序位置保持一致。由于此额外的管理工作，它的运行时性能比 ORD_SORT 慢。SORT_INDEX 需要使用两个“暂存”数组，这些数组可以作为可选的 work 和 iwork 参数提供，也可以在堆栈上内部分配。

SORT 子程序

SORT 使用 David Musser 的 introsort 排序算法。introsort 是一种混合不稳定的比较算法，结合了 快速排序、插入排序 和 堆排序。虽然该算法的运行时性能始终为 O(N Ln(N))，但在随机排序的数据上相对较快，但在部分排序的数据上没有显示出 ORD_SORT 所发现的性能改进。

首先，它检查数组并估计快速排序对于理想（随机）数据所需的递归深度 D = Ceiling(Ln(N)/Ln(2))。然后，它定义了允许在处理中进行的 快速排序 递归次数的限制 D_limit = factor * D，其中 factor 当前为 2，并调用 introsort 本身。introsort 本身然后

1. 检查待排序元素的数量，如果少于 16 个，则使用插入排序对其进行排序并返回；
2. 如果它们不少于 16 个，则检查当前递归深度是否超过 D_limit，如果超过，则使用堆排序处理剩余的元素并返回；

3. 如果当前递归深度不超过 D_limit，则实际上执行 快速排序 步骤

   • 使用三者中位数对剩余数组进行分区，
   • 对最左边的分区调用 introsort 本身，
   • 对最右边的分区调用 introsort 本身，然后返回。

生成的算法对所有输入的运行时性能均为 O(N Ln(N)) 阶。因为它依赖于 快速排序，所以 O(N Ln(N)) 行为的系数通常在随机数据上的其他排序算法中较小。在部分排序的数据上，它可以显示出较慢的 堆排序 性能，或者最多提高六倍的性能。尽管如此，即使它显示出增强的性能，它在部分排序的数据上的性能通常也比 ORD_SORT 慢一个数量级。它的内存需求也很低，为 O(Ln(N)) 阶，而 ORD_SORT 和 SORT_INDEX 的内存需求为 O(N) 阶。

RADIX_SORT 子程序

RADIX_SORT 是 LSD 基数排序 的一种实现，使用 256 作为基数。它仅适用于固定宽度数据，因此适用于整数和实数。RADIX_SORT 对于任何输入数据始终具有 O(N) 的运行时性能。对于大型随机数据，它比其他排序子程序快大约五倍（或更多）。

RADIX_SORT 需要一个与输入数据大小相同的缓冲区。您可以使用 work 参数提供它，否则子程序将在返回前分配缓冲区并在返回后释放。

stdlib_sorting 过程的规范

ord_sort - 对输入数组进行排序

状态

实验性

描述

返回一个输入 array，其元素按升序或降序排列。

语法

call ord_sort ( array[, work, reverse ] )

类

通用子程序。

参数

array：应为以下任意类型的一维数组：integer(int8)、integer(int16)、integer(int32)、integer(int64)、real(sp)、real(dp)、real(qp)、character(*)、type(string_type)、type(bitset_64) 或 type(bitset_large)。它是一个 intent(inout) 参数。在输入时，它是要排序的数组。如果 array 的类型为实数，并且至少有一个元素为 NaN，则结果的顺序未定义。否则，在返回时，其元素将按非递减顺序排序。

work（可选）：应与 array 类型相同的一维数组，并且应至少具有 size(array)/2 个元素。它是一个 intent(out) 参数。它旨在用作内部记录保存的“暂存”内存。如果与静态存储中的数组关联，则其使用可以显着减少代码的堆栈内存需求。其返回时的内容未定义。

reverse（可选）：应为默认逻辑类型的标量。它是一个 intent(in) 参数。如果存在且值为 .true.，则 array 将按非递增值以稳定顺序排序。否则，index 将按非递减值以稳定顺序对 array 进行排序。

备注

ORD_SORT 实现了一种混合排序算法，该算法结合了 merge sort 和 insertion sort。在大多数情况下，它的行为类似于 merge sort，为大多数随机数组提供最坏情况为 O(N Ln(N)) 的运行时性能，这通常比 SORT 慢。但是，如果数组具有大量递减或非递减值的运行，则性能可能会比 SORT 好得多，在均匀递减或非递减数组上具有 O(N) 的行为。可选的 work 数组替换了原本在堆栈上分配的“暂存”内存。如果 array 为任何 REAL 类型，则如果 array 的任何元素为 NaN，则返回时其元素的顺序未定义。CHARACTER(*) 和 STRING_TYPE 数组的排序基于运算符 > 和 <，而不是基于函数 LGT。

示例

program example_ord_sort
  use stdlib_sorting, only: ord_sort
  implicit none
  integer, allocatable :: array1(:), work(:)

  array1 = [5, 4, 3, 1, 10, 4, 9]
  allocate (work, mold=array1)
  call ord_sort(array1, work)
  print *, array1   !print [1, 3, 4, 4, 5, 9, 10]
end program example_ord_sort

sort - 对输入数组进行排序

状态

实验性

描述

返回一个输入数组，其元素按升序或降序排列。

语法

call sort ( array[, reverse] )

类

纯通用子程序。

参数

array：应为以下任意类型的一维数组：integer(int8)、integer(int16)、integer(int32)、integer(int64)、real(sp)、real(dp)、real(qp)、character(*)、type(string_type)、type(bitset_64) 或 type(bitset_large)。它是一个 intent(inout) 参数。在返回时，其输入元素将按非递减顺序排序。

reverse（可选）：应为默认逻辑类型的标量。它是一个 intent(in) 参数。如果存在且值为 .true.，则 array 将按非递增值以不稳定顺序排序。否则，index 将按非递减值以不稳定顺序对 array 进行排序。

备注

SORT 实现了一种混合排序算法，该算法结合了 quicksort、merge sort 和 insertion sort。在大多数情况下，它的行为类似于具有三者中值分区的 quicksort，为大多数随机数组提供了良好的 O(N Ln(N)) 运行时性能，但在数组的结构导致 quicksort 未能像预期的那样快速收敛时，默认为 merge sort。如果 array 为任何 REAL 类型，则如果 array 的任何元素为 NaN，则排序的行为未定义。CHARACTER(*) 和 STRING_TYPE 数组的排序基于运算符 <、<=、> 和 >=，而不是基于函数 LLT、LLE、LGT 或 LGE。

示例

program example_sort
  use stdlib_sorting, only: sort
  implicit none
  integer, allocatable :: array(:)

  array = [5, 4, 3, 1, 10, 4, 9]
  call sort(array)
  print *, array   !print [1, 3, 4, 4, 5, 9, 10]
end program example_sort

radix_sort - 对输入数组进行排序

状态

实验性

描述

返回一个输入数组，其元素按升序或降序排列。

语法

call radix_sort ( array[, work, reverse] )

类

通用子程序。

参数

array：应为以下任意类型的一维数组：integer(int8)、integer(int16)、integer(int32)、integer(int64)、real(sp)、real(dp)。它是一个 intent(inout) 参数。在返回时，其输入元素将按非递减顺序排序。

work（可选）：应与 array 类型相同的一维数组，并且应至少具有 size(array) 个元素。它是一个 intent(inout) 参数，其返回时的内容未定义。

reverse（可选）：应为默认 logical 类型的标量。它是一个 intent(in) 参数。如果存在且值为 .true.，则 array 将按非递增值以不稳定顺序排序。否则，index 将按非递减值以不稳定顺序对 array 进行排序。

备注

radix_sort 实现了一种具有 256 基数的 LSD 基数排序算法。对于任何输入数据，它都提供 O(N) 的运行时性能。如果 array 为任何 real 类型，则如果 array 的任何元素为 NaN，则返回时其元素的顺序未定义。

示例

program example_radix_sort
    use iso_fortran_env, only: int8, int16, dp => real64
    use stdlib_sorting, only: radix_sort
    implicit none
    integer(int8), allocatable :: arri8(:)
    integer(int16), allocatable :: arri16(:)
    real(dp) ::  x
    real(dp), allocatable ::  arrf64(:)

    arri8 = [-128, 127, 0, -1, 1]
    call radix_sort(arri8)
    print *, arri8

    arri16 = [-32767, 32767, 0, 0, -3, 2, -3]
    call radix_sort(arri16, reverse=.true.)
    print *, arri16

    allocate (arrf64(10))
    x = 0.0_dp ! divide zero will arise compile error
    arrf64 = [1.0_dp/x, 0.0_dp, 0.0_dp/x, -1.0_dp/x, -0.0_dp, 1.0_dp, -1.0_dp, 3.45_dp, -3.14_dp, 3.44_dp]
    call radix_sort(arrf64)
    print *, arrf64
    ! Expected output:
    ! nan, -inf, -3.14, -1.0, -0.0, 0.0, 1.0, 3.44, 3.45, inf
    ! Note: the position of nan is undefined
end program example_radix_sort

sort_index - 为输入数组创建排序索引数组，同时对数组进行排序。

状态

实验性

描述

返回按请求方向排序的输入 array，同时保持顺序稳定性，以及一个整数数组，其元素将对输入 array 进行排序以生成输出 array。

语法

call sort_index ( array, index[, work, iwork, reverse ] )

类

通用子程序。

参数

array：应为以下任意类型的一维数组：integer(int8)、integer(int16)、integer(int32)、integer(int64)、real(sp)、real(dp)、real(qp)、character(*)、type(string_type)、type(bitset_64) 或 type(bitset_large)。它是一个 intent(inout) 参数。在输入时，它将是一个需要确定其排序索引的数组。在返回时，它将是排序后的数组。

index：应为 kind 为 int_index 或 int_index_low 且大小为 array 的一维整数数组。它是一个 intent(out) 参数。在返回时，它应具有按所需方向对原始数组进行排序所需的索引值。

work（可选）：应为与 array 类型相同的任意类型的一维数组，并且应至少具有 size(array)/2 个元素。它是一个 intent(out) 参数。它旨在用作内部记录保存的“暂存”内存。如果与静态存储中的数组关联，则其使用可以显着减少代码的堆栈内存需求。其返回时的内容未定义。

iwork（可选）：应为与数组 index 相同 kind 的一维整数数组，并且应至少具有 size(array)/2 个元素。它是一个 intent(out) 参数。它旨在用作内部记录保存的“暂存”内存。如果与静态存储中的数组关联，则其使用可以显着减少代码的堆栈内存需求。其返回时的内容未定义。

reverse（可选）：应为默认逻辑类型的标量。它是一个 intent(in) 参数。如果存在且值为 .true.，则 index 将按非递增值以稳定顺序对 array 进行排序。否则，index 将按非递减值以稳定顺序对 array 进行排序。

备注

SORT_INDEX 实施了 ORD_SORT 的混合排序算法，在排序时保持 index 的值与 array 的元素一致。作为基于 merge sort 的算法，它是一种稳定的排序比较算法。可选的 work 和 iwork 数组替换了原本在堆栈上分配的“暂存”内存。如果 array 为任何 REAL 类型，则如果 array 的任何元素为 NaN，则返回时 index 和 array 中元素的顺序未定义。CHARACTER(*) 和 STRING_TYPE 数组的排序基于运算符 >，而不是基于函数 LGT。

需要强调的是，返回时 array 的顺序通常会不同

示例

使用 sort_index 对一维数组进行排序

program example_sort_index
  use stdlib_sorting, only: sort_index
  implicit none
  integer, allocatable :: array(:)
  integer, allocatable :: index(:)

  array = [5, 4, 3, 1, 10, 4, 9]
  allocate(index, mold=array)

  call sort_index(array, index)

  print *, array   !print [1, 3, 4, 4, 5, 9, 10]
  print *, index   !print [4, 3, 2, 6, 1, 7, 5]

end program example_sort_index

排序相关的秩一数组

    subroutine sort_related_data( a, b, work, index, iwork )
        ! Sort `a`, and  also  sort `b` to be reorderd the same way as `a`
        integer, intent(inout)         :: a(:)
        integer(int32), intent(inout)  :: b(:) ! The same size as a
        integer(int32), intent(out)    :: work(:)
        integer(int_index), intent(out) :: index(:)
        integer(int_index), intent(out) :: iwork(:)
        ! Find the indices to sort a
        call sort_index(a, index(1:size(a)),&
            work(1:size(a)/2), iwork(1:size(a)/2))
        ! Sort b based on the sorting of a
        b(:) = b( index(1:size(a)) )
    end subroutine sort_related_data

基于列中的数据对秩二数组进行排序

    subroutine sort_related_data( array, column, work, index, iwork )
        ! Reorder rows of `array` such that `array(:, column)` is  sorted
        integer, intent(inout)         :: array(:,:)
        integer(int32), intent(in)     :: column
        integer(int32), intent(out)    :: work(:)
        integer(int_index), intent(out) :: index(:)
        integer(int_index), intent(out) :: iwork(:)
        integer, allocatable           :: dummy(:)
        integer :: i
        allocate(dummy(size(array, dim=1)))
        ! Extract a column of `array`
        dummy(:) = array(:, column)
        ! Find the indices to sort the column
        call sort_index(dummy, index(1:size(dummy)),&
            work(1:size(dummy)/2), iwork(1:size(dummy)/2))
        ! Sort a based on the sorting of its column
        do i=1, size(array, dim=2)
            array(:, i) = array(index(1:size(array, dim=1)), i)
        end do
    end subroutine sort_related_data

基于一个组件中的数据对派生类型数组进行排序

    subroutine sort_a_data( a_data, a, work, index, iwork )
        ! Sort `a_data` in terms of its component `a`
        type(a_type), intent(inout)      :: a_data(:)
        integer(int32), intent(inout)    :: a(:)
        integer(int32), intent(out)    :: work(:)
        integer(int_index), intent(out) :: index(:)
        integer(int_index), intent(out) :: iwork(:)
        ! Extract a component of `a_data`
        a(1:size(a_data)) = a_data(:) % a
        ! Find the indices to sort the component
        call sort_index(a(1:size(a_data)), index(1:size(a_data)),&
            work(1:size(a_data)/2), iwork(1:size(a_data)/2))
        ! Sort a_data based on the sorting of that component
        a_data(:) = a_data( index(1:size(a_data)) )
    end subroutine sort_a_data

性能基准测试

我们对九个不同的整数数组进行了过程基准测试，每个数组的大小为 2**16

• 块 - 数组被分成六个块，每个块包含不同的均匀递增整数。
• 递减 - 值从 2**16-1 均匀递减到 0。
• 相同 - 所有整数都具有相同的值 10。
• 递增 - 值从 0 均匀递增到 2**16-1。
• 随机密集 - 整数从 0 到 2**14-1 的值集中随机生成，因此重复项很密集。
• 随机顺序 - 一组从 0 到 2**16 - 1 的整数，以随机顺序排列。
• 随机稀疏 - 整数从 0 到 2**18-1 的值集中随机生成，因此重复项很稀疏。
• 随机-3 - 递增数组对单个元素进行了 3 次随机交换。
• 随机-10 - 递增数组的最后十个元素被随机值替换。

在三个不同的默认字符数组上，每个数组长度为 4，大小为 20**4，字符取自集合“a”-“p”

• 字符递减 - 值从 "pppp" 均匀递减到 "aaaa"。
• 字符递增 - 值从 "aaaa" 均匀递增到 "pppp"。
• 字符随机 - 一组从 "aaaa" 到 "pppp" 的字符串，以随机顺序排列。

在三个不同的 string_type 数组上，每个数组包含 4 个元素，大小为 16**3，字符取自集合“a”-“p”

• 字符串递减 - 值从 "ppp" 均匀递减到 "aaa"。
• 字符串递增 - 值从 "aaa" 均匀递增到 "ppp"。
• 字符串随机 - 一组从 "aaa" 到 "ppp" 的字符串，以随机顺序排列。

这些基准测试是在两个不同的编译器上进行的，两者都在使用WSL的Ubuntu-20.04系统上运行，处理器为Intel(R) Core(TM) i7-10700 CPU @ 2.9GHz，内存为32 GB DDR4。第一个编译器是GNU Fortran (GCC) 9.4.0，其结果如下。

第二个编译器是Intel(R) Fortran Intel(R) 64 Compiler Classic，适用于在Intel(R) 64上运行的应用程序，版本为2021.7.0 Build 20220726_000000，其结果如下。