包括MergeSort， QuickSort， 包括数组和链表的实现

  1// SortAlgorithm.cpp : Defines the entry point for the console application.
  2//
  3
  4#include "stdafx.h"
  5#include <iostream>
  6#include <time.h> 
  7#include "CProTimer.h"
  8
  9using namespace std;
 10const int nSize = 500000 ;
 11 
 12// MergeSort
 13void MergeSort( int nlow, int nhigh);
 14void Merge( int nlow, int nmid, int nhigh);
 15int A[nSize];
 16int B[nSize]; // temp array
 17
 18// MergeSortL
 19int MergeSortL( int low, int high);//, int p
 20int MergeL( int q, int r );//返回int p
 21int InsertSortL( int low, int high);//, int p
 22int AL[nSize+1];  //比较特殊，第0个不用
 23int Link[nSize+1]; // linked list
 24
 25//QuickSort
 26int Partition( int m, int p);
 27void QuickSort( int p, int q);
 28int Aq[nSize];
 29void InsertSort(int p,int q);
 30
 31int _tmain(int argc, _TCHAR* argv[])
 32{
 33    srand( (unsigned)time( NULL ) );
 34    for (int i=1; i<nSize+1; i++)
 35    {
 36        AL[i] = (int)rand() ;
 37        Link[i]=i+1;
 38
 39        Aq[i-1] = AL[i];
 40     }
 41    Link[0]=1;
 42    Link[nSize]=0;    
 43    //MergeSort( 0, nSize-1);
 44
 45    // Aq[3]=Aq[0];
 46    //for (int i=0; i<nSize; i++)
 47    //{
 48    //    cout<< Aq[i] << " ";
 49
 50    //}
 51    cout<< endl;
 52
 53//    int s1=CTime::GetCurrentTime(); 
 54    //int e1=CTime::GetCurrentTime();
 55
 56    CProTimer  proTimer;
 57    proTimer.Reset();
 58    MergeSortL(1,nSize);
 59    float f=proTimer.GetTimeMicro(TRUE);
 60    cout<<"MergeSort: "<<nSize<<"个耗时(Microsecond): "<< f <<endl;
 61
 62//    s1=GetTickCount();
 63    proTimer.Reset();
 64    QuickSort(0,nSize-1) ;
 65//    e1=GetTickCount();
 66    f=proTimer.GetTimeMicro(TRUE);
 67    cout<<"QuickSort: "<<nSize<<"个耗时(Microsecond): "<< f << endl;
 68
 69    //for (int i=0; i<nSize; i++)
 70    //{
 71 //
 72    //    cout<< Aq[i]  << " ";
 73
 74    //}
 75    //cout<<endl<<"quicksort data:"<<endl;
 76    //int i=0;
 77    //while (1)
 78    //{
 79    //    int temp=AL[i];
 80    //    i=Link[i];
 81    //    if (i==0)
 82    //    {
 83    //        break;
 84    //    }
 85    //    cout<<AL[i]<<" ";
 86    //}
 87
 88    ;
 89    //for (int i=0; i<(nSize-1); i++)
 90    //{
 91    //    cout<< (Aq[i+1]-Aq[i]) << " ";
 92    //    if ((Aq[i+1]-Aq[i])<0)
 93    //    {
 94    //        cout<<endl<<"*****"<<endl;
 95    //    }
 96    //     
 97    //}
 98 
 99    return 0;
100}
101
102void MergeSort( int nlow, int nhigh)
103{
104    if ( nlow < nhigh )
105    {
106            int nmid = ( nlow + nhigh ) / 2;
107     
108            MergeSort( nlow, nmid);
109     
110     
111            MergeSort( (nmid+1) , nhigh);
112         
113            Merge( nlow, nmid, nhigh );
114    }
115}
116
117void Merge( int nlow, int nmid, int nhigh )
118{
119    int h, i, j, k;
120    // 
121    h = nlow; i = nlow; j = nmid +1;
122
123    while ( h <= nmid && j <= nhigh)
124    {
125        if ( A[h] <= A[j] )
126        {
127            B[i++] = A[h++];
128             
129        }
130        else
131        {
132            B[i++] = A[j++]; 
133        } 
134    }
135
136    //while (j <=nhigh)
137    //{
138    //    B[i++]=A[j++];
139    //}
140    //while (h <=nmid)
141    //{
142    //    B[i++]=A[h++];
143    //}
144    if( h > nmid)
145        for ( k= j; k <=nhigh; k ++)
146        {
147            B[i]=A[k];
148            ++i;
149        }
150    else
151        for (k = h; k <=nmid; k ++)
152        {
153            B[i]=A[k];
154            ++i;
155        }
156    
157    for ( k = nlow; k <=nhigh; k ++)
158    {
159        A[k] = B[k];
160    }
161
162}
163
164// MergeSortL
165int MergeSortL(int low, int high)
166{
167    if ( high - low < 10)
168    {
169        return InsertSortL(low,high);
170    }
171    else
172    {
173        int mid = (low+high)/2;
174        int q=MergeSortL(low, mid);
175        int r=MergeSortL(mid+1,high);
176        return MergeL(q,r);
177    }
178}
179int MergeL( int q, int r)
180{
181    int i=q,j=r,k=0;
182    while (i!=0&&j!=0)
183    {
184        if (AL[i] <= AL[j])
185        {
186            Link[k]=i;
187            k=i;
188            i=Link[i];
189        }
190        else
191        {
192            Link[k]=j;
193            k=j;
194            j=Link[j];
195        }
196
197    }
198        if (i==0)
199        {
200            Link[k]=j;
201        }
202        else
203            Link[k]=i;
204
205        return Link[0];
206
207}
208int InsertSortL( int low, int high)
209{
210    for (int i=low;i<=high;i++)
211    {
212        for (int j=i;j<=high;j++)
213        {
214            if (AL[j]<AL[i])
215            {
216                int temp = AL[i];
217                AL[i]=AL[j];
218                AL[j]=temp;
219            }
220        }
221    }
222    Link[high]=0;
223    return low;    
224}
225
226// Quick Sort
227int Partition(int m, int p)
228{
229    int i;
230    int v = Aq[m]; 
231    int t1=m,t2=p;
232    int v1=Aq[p],v2=Aq[(m+p)/2];  //选择首，中，尾三个数中的中间值
233    if ((v-v1)*(v-v2)>0)
234    {
235        if (v>v1)
236        {
237            if (v1>v2)
238            {
239                Aq[m]=v1;
240                Aq[p]=v;
241                v=v1;
242            }
243            else
244            {
245                Aq[m]=v2;
246                Aq[(m+p)/2]=v;
247                v=v2;
248            }
249        }
250        else
251        {
252            if (v1<v2)
253            {
254                Aq[m]=v1;
255                Aq[p]=v;
256                v=v1;
257            }
258            else
259            {
260                Aq[m]=v2;
261                Aq[(m+p)/2]=v;
262                v=v2;
263            }
264
265        }
266    }
267    
268    i=m;
269    //p=p-1;
270    while (1)
271    {
272         while (Aq[i]<=v)
273        { 
274             i++;
275        }
276        while (Aq[p]>=v&&p>m)
277        { 
278             p--;
279        }
280        if ( i < p)
281        {             
282             int temp = Aq[i];
283             Aq[i]=Aq[p];
284             Aq[p]=temp;             
285        }
286        else
287            break;
288
289    }
290
291    if (p<0)
292    {
293        cout<<"";
294    }
295     Aq[m]=Aq[p]; Aq[p]=v;
296    return p;
297
298}
299
300void QuickSort( int p, int q)
301{
302    if (q>p)
303    {
304        if ((q-p)<10)
305        {
306            InsertSort(p,q);
307        }
308        else
309        {
310            int x=Partition(p,q);
311            QuickSort(p,x-1);
312            QuickSort(x+1,q);
313        }
314
315    }
316}
317
318void InsertSort(int p,int q)
319{
320    for (int i=p;i<=q;i++)
321    {
322        for (int j=i;j<=q;j++)
323        {
324            if (Aq[j]<Aq[i])
325            {
326                int temp = Aq[i];
327                Aq[i]=Aq[j];
328                Aq[j]=temp;
329            }
330        }
331    }
332}