[第一讲] 快速排序算法

aliouying · 发表于 2014-3-2 09:56:45

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

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

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

当然，欢迎灌水

抛砖引玉：

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

001Module QuickSortMod
002!
003! quick sort algorithm
004!
005    Integer,    Parameter :: RealPrec = kind(0.0d0)
006    !
007    ! InterFace
008    !
009    Interface QuickSort
010        Module Procedure quick_sort_i
011        Module Procedure quick_sort_d
012    End InterFace QuickSort
013     
014    Contains
015!****************************************************************!******************************************************************************!
016    Recursive Subroutine quick_sort_i(ilist1,ilist2,dlist1,zlist1)
017       Integer,    dimension(:), intent(in out)             :: ilist1
018       Integer,    dimension(:), intent(in out), optional   :: ilist2
019       Real(RealPrec),    dimension(:), intent(in out), optional   :: dlist1
020       Complex(RealPrec), dimension(:), intent(in out), optional   :: zlist1
021        
022       Integer              :: i, j, n 
023       Integer              :: chosen, temp
024       complex(RealPrec)           :: ztemp
025       Integer, parameter   :: max_simple_sort_size = 6
026        
027       n = size(ilist1)
028        
029       If (n <= max_simple_sort_size) Then
030          ! Use interchange sort for small lists 
031          If ( (Present(ilist2)) .and. (Present(dlist1)) .and. (Present(zlist1)) ) Then
032                call interchange_sort(ilist1,ilist2=ilist2,dlist1=dlist1,zlist1=zlist1)
033          ElseIf ( (Present(dlist1)) .and. (Present(zlist1)) ) Then
034                call interchange_sort(ilist1,dlist1=dlist1,zlist1=zlist1)
035          ElseIf ( (Present(ilist2)) .and. (Present(dlist1)) ) Then
036                call interchange_sort(ilist1,ilist2=ilist2,dlist1=dlist1)
037          ElseIf ( (Present(ilist2)) .and. (Present(zlist1)) ) Then
038                call interchange_sort(ilist1,ilist2=ilist2,zlist1=zlist1)      
039          ElseIf ( (Present(dlist1)) ) Then
040                call interchange_sort(ilist1,dlist1=dlist1)     
041          ElseIf ( (Present(ilist2)) ) Then
042                call interchange_sort(ilist1,ilist2=ilist2)     
043          ElseIf ( (Present(zlist1)) ) Then
044                call interchange_sort(ilist1,zlist1=zlist1)        
045          Else
046                call interchange_sort(ilist1)
047          endif
048       Else
049          ! Use partition (“quick”) sort 
050          chosen = ilist1(n/2)
051          i = 0
052          j = n + 1
053          Do
054             ! Scan list from left End 
055             ! until element >= chosen is found 
056             Do
057                i = i + 1
058                If (ilist1(i) >= chosen) exit
059             End Do
060             ! Scan list from right End 
061             ! until element <= chosen is found 
062             Do
063                j = j - 1
064                If (ilist1(j) <= chosen) exit
065             End Do   
066             If (i < j) Then
067              
068                ! Swap two out of place elements 
069                temp      = ilist1(i)
070                ilist1(i) = ilist1(j)
071                ilist1(j) = temp                 
072                  
073                If (Present(ilist2)) Then
074                    temp      = ilist2(i)
075                    ilist2(i) = ilist2(j)
076                    ilist2(j) = temp                       
077                endif
078                  
079                If  (Present(dlist1)) Then 
080                    ztemp     = dlist1(i)
081                    dlist1(i) = dlist1(j)
082                    dlist1(j) = ztemp 
083                endif
084                 
085                If  (Present(zlist1)) Then 
086                    ztemp     = zlist1(i)
087                    zlist1(i) = zlist1(j)
088                    zlist1(j) = ztemp 
089                endif
090                 
091             Else If (i == j) Then
092                i = i + 1
093                exit
094             Else
095                exit
096             End If
097          End Do
098        
099          If ( (Present(ilist2)) .and. (Present(dlist1)) .and. (Present(zlist1)) ) Then
100                If (1 < j) call quick_sort_i(ilist1(:j),ilist2=ilist2(:j),dlist1=dlist1(:j),zlist1=zlist1(:j))
101                If (i < n) call quick_sort_i(ilist1(i:),ilist2=ilist2(i:),dlist1=dlist1(i:),zlist1=zlist1(i:))
102          ElseIf ( (Present(dlist1)) .and. (Present(zlist1)) ) Then
103                If (1 < j) call quick_sort_i(ilist1(:j),dlist1=dlist1(:j),zlist1=zlist1(:j))
104                If (i < n) call quick_sort_i(ilist1(i:),dlist1=dlist1(i:),zlist1=zlist1(i:))
105          ElseIf ( (Present(ilist2)) .and. (Present(dlist1)) ) Then
106                If (1 < j) call quick_sort_i(ilist1(:j),ilist2=ilist2(:j),dlist1=dlist1(:j))
107                If (i < n) call quick_sort_i(ilist1(i:),ilist2=ilist2(i:),dlist1=dlist1(i:))
108          ElseIf ( (Present(ilist2)) .and. (Present(zlist1)) ) Then
109                If (1 < j) call quick_sort_i(ilist1(:j),ilist2=ilist2(:j),zlist1=zlist1(:j))
110                If (i < n) call quick_sort_i(ilist1(i:),ilist2=ilist2(i:),zlist1=zlist1(i:))     
111          ElseIf ( (Present(dlist1)) ) Then
112                If (1 < j) call quick_sort_i(ilist1(:j),dlist1=dlist1(:j))
113                If (i < n) call quick_sort_i(ilist1(i:),dlist1=dlist1(i:))  
114          ElseIf ( (Present(ilist2)) ) Then
115                If (1 < j) call quick_sort_i(ilist1(:j),ilist2=ilist2(:j))
116                If (i < n) call quick_sort_i(ilist1(i:),ilist2=ilist2(i:))     
117          ElseIf ( (Present(zlist1)) ) Then
118                If (1 < j) call quick_sort_i(ilist1(:j),zlist1=zlist1(:j))
119                If (i < n) call quick_sort_i(ilist1(i:),zlist1=zlist1(i:))       
120          Else
121                If (1 < j) call quick_sort_i(ilist1(:j))
122                If (i < n) call quick_sort_i(ilist1(i:))  
123          endif
124       End If  ! test for small array 
125    End Subroutine quick_sort_i 
126!****************************************************************!******************************************************************************!
127    Subroutine interchange_sort(ilist1,ilist2,dlist1,zlist1)
128      
129       Integer,    dimension(:), intent(in out)             :: ilist1
130       Integer,    dimension(:), intent(in out), optional   :: ilist2
131       Real(RealPrec),    dimension(:), intent(in out), optional   :: dlist1
132       Complex(RealPrec), dimension(:), intent(in out), optional   :: zlist1
133        
134       Integer      :: i, j 
135       Integer      :: temp 
136       complex(RealPrec)   :: ztemp
137        
138       Do i = 1, size(ilist1) - 1
139        
140          Do j = i + 1, size(ilist1)
141           
142             If (ilist1(i) >  ilist1(j)) Then
143              
144                temp      = ilist1(i)
145                ilist1(i) = ilist1(j)
146                ilist1(j) = temp 
147                              
148                If (Present(ilist2)) Then
149                    temp      = ilist2(i)
150                    ilist2(i) = ilist2(j)
151                    ilist2(j) = temp                       
152                endif
153                  
154                If  (Present(dlist1)) Then 
155                    ztemp     = dlist1(i)
156                    dlist1(i) = dlist1(j)
157                    dlist1(j) = ztemp 
158                endif
159         
160                If  (Present(zlist1)) Then 
161                    ztemp     = zlist1(i)
162                    zlist1(i) = zlist1(j)
163                    zlist1(j) = ztemp 
164                endif
165                                 
166             End If
167          End Do
168       End Do
169    End Subroutine interchange_sort     
170!****************************************************************!******************************************************************************!  
171    Recursive Subroutine quick_sort_d(dlist1,dlist2,ilist1,zlist1)
172       Real(RealPrec),    dimension(:), intent(in out)             :: dlist1
173       Real(RealPrec),    dimension(:), intent(in out), optional   :: dlist2
174       Integer,    dimension(:), intent(in out), optional   :: ilist1
175       Complex(RealPrec), dimension(:), intent(in out), optional   :: zlist1
176    
177        
178       Integer              :: i, j, n 
179       Integer              :: temp
180       real(RealPrec)              :: dtemp, chosen
181       Complex(RealPrec)           :: ztemp
182       Integer, parameter   :: max_simple_sort_size = 6
183        
184       n = size(dlist1)
185 
186       If (n <= max_simple_sort_size) Then
187          ! Use interchange sort for small lists 
188           If ( (Present(ilist1)).and.(Present(dlist2)) .and. (Present(zlist1)) ) Then
189                call interchange_sort_d(dlist1,dlist2=dlist2,ilist1=ilist1,zlist1=zlist1)  
190           ElseIf( (Present(ilist1)) .and. (Present(zlist1)) ) Then
191               call interchange_sort_d(dlist1,ilist1=ilist1,zlist1=zlist1)  
192            ElseIf ( (Present(dlist2)) .and. (Present(zlist1)) ) Then
193                call interchange_sort_d(dlist1,dlist2=dlist2,zlist1=zlist1)
194            ElseIf ( (Present(dlist2)) .and. (Present(ilist1)) ) Then
195                call interchange_sort_d(dlist1,dlist2=dlist2,ilist1=ilist1)
196          ElseIf ( (Present(ilist1)) ) Then
197                call interchange_sort_d(dlist1,ilist1=ilist1)   
198          ElseIf ( (Present(zlist1)) ) Then
199              call interchange_sort_d(dlist1,zlist1=zlist1) 
200          ElseIf ( (Present(dlist2)) ) Then
201                call interchange_sort_d(dlist1,dlist2=dlist2)         
202          Else
203                call interchange_sort_d(dlist1)
204          endif
205       Else
206          ! Use partition (“quick”) sort 
207          chosen = dlist1(n/2)
208          i = 0
209          j = n + 1
210          Do
211             ! Scan list from left End 
212             ! until element >= chosen is found 
213             Do
214                i = i + 1
215                If (dlist1(i) >= chosen) exit
216             End Do
217             ! Scan list from right End 
218             ! until element <= chosen is found 
219             Do
220                j = j - 1
221                If (dlist1(j) <= chosen) exit
222             End Do   
223             If (i < j) Then
224              
225                ! Swap two out of place elements 
226                dtemp     = dlist1(i)
227                dlist1(i) = dlist1(j)
228                dlist1(j) = dtemp                 
229                  
230                If (Present(ilist1)) Then
231                    temp      = ilist1(i)
232                    ilist1(i) = ilist1(j)
233                    ilist1(j) = temp                       
234                endif
235                 
236                If (Present(dlist2)) Then
237                    dtemp     = dlist2(i)
238                    dlist2(i) = dlist2(j)
239                    dlist2(j) = dtemp                       
240                endif
241                 
242                If  (Present(zlist1)) Then 
243                    ztemp     = zlist1(i)
244                    zlist1(i) = zlist1(j)
245                    zlist1(j) = ztemp 
246                endif
247             Else If (i == j) Then
248                i = i + 1
249                exit
250             Else
251                exit
252             End If
253          End Do
254             
255           If ( (Present(ilist1)).and.(Present(dlist2)) .and. (Present(zlist1)) ) Then
256                If (1 < j) call quick_sort_d(dlist1(:j),dlist2=dlist2(:j),ilist1=ilist1(:j),zlist1=zlist1(:j))
257                If (i < n) call quick_sort_d(dlist1(i:),dlist2=dlist2(i:),ilist1=ilist1(i:),zlist1=zlist1(i:))  
258           ElseIf( (Present(ilist1)) .and. (Present(zlist1)) ) Then
259               If (1 < j) call quick_sort_d(dlist1(:j),ilist1=ilist1(:j),zlist1=zlist1(:j))
260               If (i < n) call quick_sort_d(dlist1(i:),ilist1=ilist1(i:),zlist1=zlist1(i:))  
261            ElseIf ( (Present(dlist2)) .and. (Present(zlist1)) ) Then
262                If (1 < j) call quick_sort_d(dlist1(:j),dlist2=dlist2(:j),zlist1=zlist1(:j))
263                If (i < n) call quick_sort_d(dlist1(i:),dlist2=dlist2(i:),zlist1=zlist1(i:))
264            ElseIf ( (Present(dlist2)) .and. (Present(ilist1)) ) Then
265                If (1 < j) call quick_sort_d(dlist1(:j),dlist2=dlist2(:j),ilist1=ilist1(:j))
266                If (i < n) call quick_sort_d(dlist1(i:),dlist2=dlist2(i:),ilist1=ilist1(i:))
267          ElseIf ( (Present(ilist1)) ) Then
268                If (1 < j) call quick_sort_d(dlist1(:j),ilist1=ilist1(:j))
269                If (i < n) call quick_sort_d(dlist1(i:),ilist1=ilist1(i:))
270          ElseIf ( (Present(zlist1)) ) Then
271               If (1 < j) call quick_sort_d(dlist1(:j),zlist1=zlist1(:j))
272               If (i < n) call quick_sort_d(dlist1(i:),zlist1=zlist1(i:))
273          ElseIf ( (Present(dlist2)) ) Then
274                If (1 < j) call quick_sort_d(dlist1(:j),dlist2=dlist2(:j))
275                If (i < n) call quick_sort_d(dlist1(i:),dlist2=dlist2(i:))     
276          Else
277                If (1 < j) call quick_sort_d(dlist1(:j))
278                If (i < n) call quick_sort_d(dlist1(i:))
279          endif
280  
281       End If  ! test for small array 
282    End Subroutine quick_sort_d 
283!****************************************************************!******************************************************************************!
284    Subroutine interchange_sort_d(dlist1,dlist2,ilist1,zlist1)
285      
286       Real(RealPrec),    dimension(:), intent(in out)             :: dlist1
287       Real(RealPrec),    dimension(:), intent(in out), optional   :: dlist2
288       Integer,    dimension(:), intent(in out), optional   :: ilist1
289       Complex(RealPrec), dimension(:), intent(in out), optional   :: zlist1
290        
291       Integer      :: i, j 
292       Integer      :: temp 
293       real(RealPrec)      :: dtemp
294       complex(RealPrec)   :: ztemp
295        
296       Do i = 1, size(dlist1) - 1
297        
298          Do j = i + 1, size(dlist1)
299           
300             If (dlist1(i) >  dlist1(j)) Then
301              
302                dtemp     = dlist1(i)
303                dlist1(i) = dlist1(j)
304                dlist1(j) = dtemp 
305                 
306                If (Present(dlist2)) Then
307                    dtemp     = dlist2(i)
308                    dlist2(i) = dlist2(j)
309                    dlist2(j) = dtemp                       
310                endif         
311                  
312                If (Present(ilist1)) Then
313                    temp      = ilist1(i)
314                    ilist1(i) = ilist1(j)
315                    ilist1(j) = temp                       
316                endif
317                 
318                If  (Present(zlist1)) Then 
319                    ztemp     = zlist1(i)
320                    zlist1(i) = zlist1(j)
321                    zlist1(j) = ztemp 
322                endif
323             End If
324          End Do
325       End Do
326       Return
327    End Subroutine interchange_sort_d  
328!****************************************************************!******************************************************************************!
329End Module

主程序：

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

01Program QuickSortMain
02    Use QuickSortMod
03    Implicit None
04    Integer :: N
05    Integer,    allocatable :: IntDat(:)
06    Real(8),    allocatable :: RealDat(:)
07    Complex(8), allocatable :: ComplexDat(:)
08    real,       allocatable :: Dat(:)
09     
10    N = 10
11     
12    allocate( IntDat(N), RealDat(N), ComplexDat(N), Dat(N) )
13     
14    Call Random_Seed()
15     
16    ! set integer data
17    Call Random_number(Dat)
18     
19    IntDat = Int( (2*Dat-1)*100 )
20     
21    ! set real data
22    Call Random_number(Dat)
23     
24    RealDat = (2*Dat-1)*100
25     
26    ! set complx data
27    Call Random_number(Dat)
28     
29    ComplexDat = (2*Dat-1)*100
30     
31    Call QuickSort(IntDat,dlist1=RealDat,zlist1=ComplexDat)
32     
33    Call QuickSort(RealDat,ilist1=IntDat,zlist1=ComplexDat)
34Stop
35End Program QuickSortMain