[第一讲] 快速排序算法

aliouying

在数值计算中，不可避免的需要用到排序，对于快速排序算法，数值分析的书里面介绍非常详细，这里我们不讨论具体算法，只讨论程序的标准性、通用性、可扩展性

大家可以从以下方面来讨论：

1、程序的错误地方，需改进的地方
2、跟常用算法库的程序进行对比，贴出相应的效率对比分析，并注明编译器、系统、版本等信息
3、数组大小与时间的效率图
4、针对自己的问题，贴出相关的效率图
5、网络上存在的快速排序算法都有哪些，效率、通用性等

当然，欢迎灌水

抛砖引玉：

[Fortran] 纯文本查看 复制代码

Module QuickSortMod
!
! quick sort algorithm
!
    Integer,    Parameter :: RealPrec = kind(0.0d0)
    !
    ! InterFace
    !
    Interface QuickSort
        Module Procedure quick_sort_i
        Module Procedure quick_sort_d
    End InterFace QuickSort
    
    Contains
!****************************************************************!******************************************************************************!
    Recursive Subroutine quick_sort_i(ilist1,ilist2,dlist1,zlist1) 
       Integer,    dimension(:), intent(in out)             :: ilist1
       Integer,    dimension(:), intent(in out), optional   :: ilist2
       Real(RealPrec),    dimension(:), intent(in out), optional   :: dlist1
       Complex(RealPrec), dimension(:), intent(in out), optional   :: zlist1
       
       Integer              :: i, j, n 
       Integer              :: chosen, temp
       complex(RealPrec)           :: ztemp
       Integer, parameter   :: max_simple_sort_size = 6
       
       n = size(ilist1) 
       
       If (n <= max_simple_sort_size) Then 
          ! Use interchange sort for small lists 
          If ( (Present(ilist2)) .and. (Present(dlist1)) .and. (Present(zlist1)) ) Then
                call interchange_sort(ilist1,ilist2=ilist2,dlist1=dlist1,zlist1=zlist1) 
          ElseIf ( (Present(dlist1)) .and. (Present(zlist1)) ) Then
                call interchange_sort(ilist1,dlist1=dlist1,zlist1=zlist1) 
          ElseIf ( (Present(ilist2)) .and. (Present(dlist1)) ) Then
                call interchange_sort(ilist1,ilist2=ilist2,dlist1=dlist1) 
          ElseIf ( (Present(ilist2)) .and. (Present(zlist1)) ) Then
                call interchange_sort(ilist1,ilist2=ilist2,zlist1=zlist1)       
          ElseIf ( (Present(dlist1)) ) Then
                call interchange_sort(ilist1,dlist1=dlist1)      
          ElseIf ( (Present(ilist2)) ) Then
                call interchange_sort(ilist1,ilist2=ilist2)      
          ElseIf ( (Present(zlist1)) ) Then
                call interchange_sort(ilist1,zlist1=zlist1)         
          Else
                call interchange_sort(ilist1) 
          endif
       Else 
          ! Use partition (“quick”) sort 
          chosen = ilist1(n/2) 
          i = 0 
          j = n + 1 
          Do 
             ! Scan list from left End 
             ! until element >= chosen is found 
             Do 
                i = i + 1 
                If (ilist1(i) >= chosen) exit 
             End Do 
             ! Scan list from right End 
             ! until element <= chosen is found 
             Do 
                j = j - 1 
                If (ilist1(j) <= chosen) exit 
             End Do    
             If (i < j) Then 
             
                ! Swap two out of place elements 
                temp      = ilist1(i) 
                ilist1(i) = ilist1(j) 
                ilist1(j) = temp                 
                 
                If (Present(ilist2)) Then
                    temp      = ilist2(i) 
                    ilist2(i) = ilist2(j) 
                    ilist2(j) = temp                       
                endif
                 
                If  (Present(dlist1)) Then  
                    ztemp     = dlist1(i) 
                    dlist1(i) = dlist1(j) 
                    dlist1(j) = ztemp 
                endif
                
                If  (Present(zlist1)) Then  
                    ztemp     = zlist1(i) 
                    zlist1(i) = zlist1(j) 
                    zlist1(j) = ztemp 
                endif
                
             Else If (i == j) Then 
                i = i + 1 
                exit 
             Else 
                exit 
             End If 
          End Do 
       
          If ( (Present(ilist2)) .and. (Present(dlist1)) .and. (Present(zlist1)) ) Then
                If (1 < j) call quick_sort_i(ilist1(:j),ilist2=ilist2(:j),dlist1=dlist1(:j),zlist1=zlist1(:j)) 
                If (i < n) call quick_sort_i(ilist1(i:),ilist2=ilist2(i:),dlist1=dlist1(i:),zlist1=zlist1(i:)) 
          ElseIf ( (Present(dlist1)) .and. (Present(zlist1)) ) Then
                If (1 < j) call quick_sort_i(ilist1(:j),dlist1=dlist1(:j),zlist1=zlist1(:j)) 
                If (i < n) call quick_sort_i(ilist1(i:),dlist1=dlist1(i:),zlist1=zlist1(i:)) 
          ElseIf ( (Present(ilist2)) .and. (Present(dlist1)) ) Then
                If (1 < j) call quick_sort_i(ilist1(:j),ilist2=ilist2(:j),dlist1=dlist1(:j)) 
                If (i < n) call quick_sort_i(ilist1(i:),ilist2=ilist2(i:),dlist1=dlist1(i:)) 
          ElseIf ( (Present(ilist2)) .and. (Present(zlist1)) ) Then
                If (1 < j) call quick_sort_i(ilist1(:j),ilist2=ilist2(:j),zlist1=zlist1(:j)) 
                If (i < n) call quick_sort_i(ilist1(i:),ilist2=ilist2(i:),zlist1=zlist1(i:))      
          ElseIf ( (Present(dlist1)) ) Then
                If (1 < j) call quick_sort_i(ilist1(:j),dlist1=dlist1(:j)) 
                If (i < n) call quick_sort_i(ilist1(i:),dlist1=dlist1(i:))   
          ElseIf ( (Present(ilist2)) ) Then
                If (1 < j) call quick_sort_i(ilist1(:j),ilist2=ilist2(:j)) 
                If (i < n) call quick_sort_i(ilist1(i:),ilist2=ilist2(i:))      
          ElseIf ( (Present(zlist1)) ) Then
                If (1 < j) call quick_sort_i(ilist1(:j),zlist1=zlist1(:j)) 
                If (i < n) call quick_sort_i(ilist1(i:),zlist1=zlist1(i:))        
          Else
                If (1 < j) call quick_sort_i(ilist1(:j)) 
                If (i < n) call quick_sort_i(ilist1(i:))   
          endif
       End If  ! test for small array 
    End Subroutine quick_sort_i 
!****************************************************************!******************************************************************************!
    Subroutine interchange_sort(ilist1,ilist2,dlist1,zlist1)
     
       Integer,    dimension(:), intent(in out)             :: ilist1
       Integer,    dimension(:), intent(in out), optional   :: ilist2
       Real(RealPrec),    dimension(:), intent(in out), optional   :: dlist1
       Complex(RealPrec), dimension(:), intent(in out), optional   :: zlist1
       
       Integer      :: i, j 
       Integer      :: temp 
       complex(RealPrec)   :: ztemp
       
       Do i = 1, size(ilist1) - 1 
       
          Do j = i + 1, size(ilist1) 
          
             If (ilist1(i) >  ilist1(j)) Then 
             
                temp      = ilist1(i) 
                ilist1(i) = ilist1(j) 
                ilist1(j) = temp 
                             
                If (Present(ilist2)) Then
                    temp      = ilist2(i) 
                    ilist2(i) = ilist2(j) 
                    ilist2(j) = temp                       
                endif
                 
                If  (Present(dlist1)) Then  
                    ztemp     = dlist1(i) 
                    dlist1(i) = dlist1(j) 
                    dlist1(j) = ztemp 
                endif
        
                If  (Present(zlist1)) Then  
                    ztemp     = zlist1(i) 
                    zlist1(i) = zlist1(j) 
                    zlist1(j) = ztemp 
                endif
                                
             End If 
          End Do 
       End Do 
    End Subroutine interchange_sort     
!****************************************************************!******************************************************************************!  
    Recursive Subroutine quick_sort_d(dlist1,dlist2,ilist1,zlist1) 
       Real(RealPrec),    dimension(:), intent(in out)             :: dlist1
       Real(RealPrec),    dimension(:), intent(in out), optional   :: dlist2
       Integer,    dimension(:), intent(in out), optional   :: ilist1
       Complex(RealPrec), dimension(:), intent(in out), optional   :: zlist1
   
       
       Integer              :: i, j, n 
       Integer              :: temp
       real(RealPrec)              :: dtemp, chosen
       Complex(RealPrec)           :: ztemp
       Integer, parameter   :: max_simple_sort_size = 6
       
       n = size(dlist1) 

       If (n <= max_simple_sort_size) Then 
          ! Use interchange sort for small lists 
           If ( (Present(ilist1)).and.(Present(dlist2)) .and. (Present(zlist1)) ) Then
                call interchange_sort_d(dlist1,dlist2=dlist2,ilist1=ilist1,zlist1=zlist1)   
           ElseIf( (Present(ilist1)) .and. (Present(zlist1)) ) Then
               call interchange_sort_d(dlist1,ilist1=ilist1,zlist1=zlist1)   
            ElseIf ( (Present(dlist2)) .and. (Present(zlist1)) ) Then
                call interchange_sort_d(dlist1,dlist2=dlist2,zlist1=zlist1) 
            ElseIf ( (Present(dlist2)) .and. (Present(ilist1)) ) Then 
                call interchange_sort_d(dlist1,dlist2=dlist2,ilist1=ilist1) 
          ElseIf ( (Present(ilist1)) ) Then
                call interchange_sort_d(dlist1,ilist1=ilist1)    
          ElseIf ( (Present(zlist1)) ) Then 
              call interchange_sort_d(dlist1,zlist1=zlist1)  
          ElseIf ( (Present(dlist2)) ) Then
                call interchange_sort_d(dlist1,dlist2=dlist2)          
          Else
                call interchange_sort_d(dlist1) 
          endif
       Else 
          ! Use partition (“quick”) sort 
          chosen = dlist1(n/2) 
          i = 0 
          j = n + 1 
          Do 
             ! Scan list from left End 
             ! until element >= chosen is found 
             Do 
                i = i + 1 
                If (dlist1(i) >= chosen) exit 
             End Do 
             ! Scan list from right End 
             ! until element <= chosen is found 
             Do 
                j = j - 1 
                If (dlist1(j) <= chosen) exit 
             End Do    
             If (i < j) Then 
             
                ! Swap two out of place elements 
                dtemp     = dlist1(i) 
                dlist1(i) = dlist1(j) 
                dlist1(j) = dtemp                 
                 
                If (Present(ilist1)) Then
                    temp      = ilist1(i) 
                    ilist1(i) = ilist1(j) 
                    ilist1(j) = temp                       
                endif
                
                If (Present(dlist2)) Then
                    dtemp     = dlist2(i) 
                    dlist2(i) = dlist2(j) 
                    dlist2(j) = dtemp                       
                endif
                
                If  (Present(zlist1)) Then  
                    ztemp     = zlist1(i) 
                    zlist1(i) = zlist1(j) 
                    zlist1(j) = ztemp 
                endif
             Else If (i == j) Then 
                i = i + 1 
                exit 
             Else 
                exit 
             End If 
          End Do 
            
           If ( (Present(ilist1)).and.(Present(dlist2)) .and. (Present(zlist1)) ) Then
                If (1 < j) call quick_sort_d(dlist1(:j),dlist2=dlist2(:j),ilist1=ilist1(:j),zlist1=zlist1(:j)) 
                If (i < n) call quick_sort_d(dlist1(i:),dlist2=dlist2(i:),ilist1=ilist1(i:),zlist1=zlist1(i:))   
           ElseIf( (Present(ilist1)) .and. (Present(zlist1)) ) Then
               If (1 < j) call quick_sort_d(dlist1(:j),ilist1=ilist1(:j),zlist1=zlist1(:j)) 
               If (i < n) call quick_sort_d(dlist1(i:),ilist1=ilist1(i:),zlist1=zlist1(i:))   
            ElseIf ( (Present(dlist2)) .and. (Present(zlist1)) ) Then
                If (1 < j) call quick_sort_d(dlist1(:j),dlist2=dlist2(:j),zlist1=zlist1(:j)) 
                If (i < n) call quick_sort_d(dlist1(i:),dlist2=dlist2(i:),zlist1=zlist1(i:)) 
            ElseIf ( (Present(dlist2)) .and. (Present(ilist1)) ) Then 
                If (1 < j) call quick_sort_d(dlist1(:j),dlist2=dlist2(:j),ilist1=ilist1(:j)) 
                If (i < n) call quick_sort_d(dlist1(i:),dlist2=dlist2(i:),ilist1=ilist1(i:)) 
          ElseIf ( (Present(ilist1)) ) Then
                If (1 < j) call quick_sort_d(dlist1(:j),ilist1=ilist1(:j)) 
                If (i < n) call quick_sort_d(dlist1(i:),ilist1=ilist1(i:)) 
          ElseIf ( (Present(zlist1)) ) Then 
               If (1 < j) call quick_sort_d(dlist1(:j),zlist1=zlist1(:j)) 
               If (i < n) call quick_sort_d(dlist1(i:),zlist1=zlist1(i:)) 
          ElseIf ( (Present(dlist2)) ) Then
                If (1 < j) call quick_sort_d(dlist1(:j),dlist2=dlist2(:j)) 
                If (i < n) call quick_sort_d(dlist1(i:),dlist2=dlist2(i:))      
          Else
                If (1 < j) call quick_sort_d(dlist1(:j)) 
                If (i < n) call quick_sort_d(dlist1(i:)) 
          endif
 
       End If  ! test for small array 
    End Subroutine quick_sort_d 
!****************************************************************!******************************************************************************!
    Subroutine interchange_sort_d(dlist1,dlist2,ilist1,zlist1)
     
       Real(RealPrec),    dimension(:), intent(in out)             :: dlist1
       Real(RealPrec),    dimension(:), intent(in out), optional   :: dlist2
       Integer,    dimension(:), intent(in out), optional   :: ilist1
       Complex(RealPrec), dimension(:), intent(in out), optional   :: zlist1
       
       Integer      :: i, j 
       Integer      :: temp 
       real(RealPrec)      :: dtemp
       complex(RealPrec)   :: ztemp
       
       Do i = 1, size(dlist1) - 1 
       
          Do j = i + 1, size(dlist1) 
          
             If (dlist1(i) >  dlist1(j)) Then 
             
                dtemp     = dlist1(i) 
                dlist1(i) = dlist1(j) 
                dlist1(j) = dtemp 
                
                If (Present(dlist2)) Then
                    dtemp     = dlist2(i) 
                    dlist2(i) = dlist2(j) 
                    dlist2(j) = dtemp                       
                endif          
                 
                If (Present(ilist1)) Then
                    temp      = ilist1(i) 
                    ilist1(i) = ilist1(j) 
                    ilist1(j) = temp                       
                endif
                
                If  (Present(zlist1)) Then  
                    ztemp     = zlist1(i) 
                    zlist1(i) = zlist1(j) 
                    zlist1(j) = ztemp 
                endif
             End If 
          End Do 
       End Do 
       Return
    End Subroutine interchange_sort_d  
!****************************************************************!******************************************************************************!
End Module 

主程序：

[Fortran] 纯文本查看 复制代码

Program QuickSortMain
    Use QuickSortMod
    Implicit None
    Integer :: N
    Integer,    allocatable :: IntDat(:)
    Real(8),    allocatable :: RealDat(:)
    Complex(8), allocatable :: ComplexDat(:)
    real,       allocatable :: Dat(:)
    
    N = 10
    
    allocate( IntDat(N), RealDat(N), ComplexDat(N), Dat(N) )
    
    Call Random_Seed()
    
    ! set integer data
    Call Random_number(Dat)
    
    IntDat = Int( (2*Dat-1)*100 )
    
    ! set real data
    Call Random_number(Dat)
    
    RealDat = (2*Dat-1)*100
    
    ! set complx data
    Call Random_number(Dat)
    
    ComplexDat = (2*Dat-1)*100
    
    Call QuickSort(IntDat,dlist1=RealDat,zlist1=ComplexDat)
    
    Call QuickSort(RealDat,ilist1=IntDat,zlist1=ComplexDat)
Stop
End Program QuickSortMain

渡箭

你们都这么niubility

chiangtp

優點: 簡單就是美?
缺點: may runtime stack overflow (compiler and array-size dependent),
        Array size越大效率越差 (相對於"正常"coding)

chiangtp

分享一個 Quick Sorting 的 "簡潔" Fortran code
http://bbs.06climate.com/forum.php?mod=viewthread&tid=32383

glodve

实际上，并归排序也是一个不错的排序方法。不知道对于快速排序和并归排序在实际应用中的效率哪一个好

楚香饭

山大克鲁士 发表于 2014-5-26 14:02
快排纵然好理解，但是个人总感觉递归的效率可能不高，正如Davis将所有递归利用压栈弹栈来操作一样，虽然在 ...

递归一定会慢的。尤其是局部变量比较多的函数。

如果不考虑编译器的优化作用的话。

山大克鲁士

快排纵然好理解，但是个人总感觉递归的效率可能不高，正如Davis将所有递归利用压栈弹栈来操作一样，虽然在汇编级递归确实也是不断的弹栈压栈过程。。。
不知诸君有何见解？

岸边的鱼

排序是个很好的课题，方法应该有很多种，期待看到别的排序方法，都拿来比较下

aliouying

pasuka 发表于 2014-3-11 20:26
如果有兴趣，还可以gfortran调用gsl再测试一下

我在写毕业论文，所以没多少时间，等过段时间测试下

pasuka

aliouying 发表于 2014-3-11 18:57
从结果来看，gcc自带的qsort貌似效率最高，不知fortran的代码编译时是否优化？
但QuickSortMod和Juli Rew ...

如果有兴趣，还可以gfortran调用gsl再测试一下