Fortran 快速排序算法
2014-02-08 19:10:41   来源：Fortran.com   评论：0 点击：

快速排序（Quicksort）是对冒泡排序的一种改进。此段代码实现了Fortran快速排序算法。 Visual Fortran 提供的 QSort 函数内部即采用此算法。

! Recursive Fortran 95 quicksort routine
! sorts real numbers into ascending numerical order
! Author: Juli Rew, SCD Consulting (juliana@ucar.edu), 9/03
! Based on algorithm from Cormen et al., Introduction to Algorithms,
! 1997 printing
! Made F conformant by Walt Brainerd
module qsort_c_module
  implicit none
  public :: QsortC
  private :: Partition

contains

  recursive subroutine QsortC(A)
    real, intent(in out), dimension(:) :: A
    integer :: iq
    if(size(A) > 1) then
      call Partition(A, iq)
      call QsortC(A(:iq-1))
      call QsortC(A(iq:))
    endif
  end subroutine QsortC

  subroutine Partition(A, marker)
    real, intent(in out), dimension(:) :: A
    integer, intent(out) :: marker
    integer :: i, j
    real :: temp
    real :: x      ! pivot point
    x = A(1)
    i= 0
    j= size(A) + 1
    do
      j = j-1
      do
        if (A(j) <= x) exit
        j = j-1
      end do
      i = i+1
      do
        if (A(i) >= x) exit
        i = i+1
      end do
      if (i < j) then
        ! exchange A(i) and A(j)
        temp = A(i)
        A(i) = A(j)
        A(j) = temp
      elseif (i == j) then
        marker = i+1
        return
      else
        marker = i
        return
      endif
    end do
  end subroutine Partition

end module qsort_c_module

program www_fcode_cn
  use qsort_c_module
  implicit none
  integer, parameter :: r = 10
  real, dimension(1:r) :: myarray = (/0, 50, 20, 25, 90, 10, 5, 1, 99, 75/)
  print *, "原数组:", myarray
  call QsortC(myarray)
  print *, "排序后:", myarray
end program www_fcode_cn