歸并排序-有解無憂

簡介：歸并排序的時間復雜度為O( n log n )，是一種速度僅次于快速排序的穩定排序演算法， (題外話：雖然C++的STL中有sort()函式，但有些演算法題用到了歸并排序的思想，如求逆序數，因此歸并排序是必須懂的，當然，網上關于歸并排序的講解很多，這里僅僅只是給出模板，)

模板：

 1 void mergeArray(int *a,int l,int mid,int r,int *temp)
 2 {
 3     int i=l,j=mid+1;
 4     int k=0;
 5     
 6     while(i<=mid&&j<=r)
 7     {
 8         if(a[i]<=a[j])
 9             temp[k++]=a[i++];
10         else
11             temp[k++]=a[j++];
12     }
13     
14     while(i<=mid)
15         temp[k++]=a[i++];
16     while(j<=r)
17         temp[k++]=a[j++];
18     
19     for(int i=0;i<k;i++)
20         a[l+i]=temp[i];    
21 }
22 
23 void mergeSort(int *a,int l,int r,int *temp)
24 {
25     if(l<r)
26     {
27         int mid=(l+r)/2;
28         mergeSort(a,l,mid,temp);
29         mergeSort(a,mid+1,r,temp);
30         mergeArray(a,l,mid,r,temp); 
31     }
32 }

題目：洛谷 P1177

(雖然題目寫著是快速排序的模板題，但也能當作是其他時間復雜度與快速排序不相上下的排序演算法的模板題)

 1 const int Size = 1000000;
 2 int array[Size];
 3 int arrayCopy[Size];
 4 
 5 void mergeArray(int *a,int l,int mid,int r,int *temp)
 6 {
 7     int i=l,j=mid+1;
 8     int k=0;
 9     
10     while(i<=mid&&j<=r)
11     {
12         if(a[i]<=a[j])
13             temp[k++]=a[i++];
14         else
15             temp[k++]=a[j++];
16     }
17     
18     while(i<=mid)
19         temp[k++]=a[i++];
20     while(j<=r)
21         temp[k++]=a[j++];
22     
23     for(int i=0;i<k;i++)
24         a[l+i]=temp[i];    
25 }
26 
27 void mergeSort(int *a,int l,int r,int *temp)
28 {
29     if(l<r)
30     {
31         int mid=(l+r)/2;
32         mergeSort(a,l,mid,temp);
33         mergeSort(a,mid+1,r,temp);
34         mergeArray(a,l,mid,r,temp); 
35     }
36 } 
37 
38 int main()
39 {
40     int n;
41     cin>>n;
42     for(int i=0;i<n;i++)
43     {
44         cin>>array[i];
45     }
46     mergeSort(array,0,n-1,arrayCopy);
47     for(int i=0;i<n;i++)
48     {
49         cout<<array[i]<<" ";
50     }
51 }

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/121128.html

標籤：其他

上一篇：常用資料結構操作與演算法復雜度總結

下一篇：演算法-反轉一個單鏈表