Fortran 快速排序算法

christy

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

1. ! Recursive Fortran 95 quicksort routine
   
2. ! sorts real numbers into ascending numerical order
   
3. ! Author: Juli Rew, SCD Consulting (juliana@ucar.edu), 9/03
   
4. ! Based on algorithm from Cormen et al., Introduction to Algorithms,
   
5. ! 1997 printing
   
6. ! Made F conformant by Walt Brainerd
   
7. module qsort_c_module
   
8.   implicit none
   
9.   public :: QsortC
   
10.   private :: Partition
    
11. 
    
12. contains
    
13. 
    
14.   recursive subroutine QsortC(A)
    
15.     real, intent(in out), dimension(:) :: A
    
16.     integer :: iq
    
17.     if(size(A) > 1) then
    
18.       call Partition(A, iq)
    
19.       call QsortC(A(:iq-1))
    
20.       call QsortC(A(iq:))
    
21.     endif
    
22.   end subroutine QsortC
    
23. 
    
24.   subroutine Partition(A, marker)
    
25.     real, intent(in out), dimension(:) :: A
    
26.     integer, intent(out) :: marker
    
27.     integer :: i, j
    
28.     real :: temp
    
29.     real :: x      ! pivot point
    
30.     x = A(1)
    
31.     i= 0
    
32.     j= size(A) + 1
    
33.     do
    
34.       j = j-1
    
35.       do
    
36.         if (A(j) <= x) exit
    
37.         j = j-1
    
38.       end do
    
39.       i = i+1
    
40.       do
    
41.         if (A(i) >= x) exit
    
42.         i = i+1
    
43.       end do
    
44.       if (i < j) then
    
45.         ! exchange A(i) and A(j)
    
46.         temp = A(i)
    
47.         A(i) = A(j)
    
48.         A(j) = temp
    
49.       elseif (i == j) then
    
50.         marker = i+1
    
51.         return
    
52.       else
    
53.         marker = i
    
54.         return
    
55.       endif
    
56.     end do
    
57.   end subroutine Partition
    
58. 
    
59. end module qsort_c_module
    
60. 
    
61. program www_fcode_cn
    
62.   use qsort_c_module
    
63.   implicit none
    
64.   integer, parameter :: r = 10
    
65.   real, dimension(1:r) :: myarray = (/0, 50, 20, 25, 90, 10, 5, 1, 99, 75/)
    
66.   print *, "原数组:", myarray
    
67.   call QsortC(myarray)
    
68.   print *, "排序后:", myarray
    
69. end program www_fcode_cn

复制代码