由一道面试题想到的关于归并排序的几种写法

View Code
  1 // 搜狐一道题.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 /*********************************
  5 一数组前半部分已经有序，后半部分也有序，先要求在
  6 O（1）的空间下实现对该数组的排序。
  7 
  8 关于归并排序
  9 
 10 1 实现o（1）空间的原地排序算法
 11 
 12 2 实现辅助数组的归并排序算法
 13 
 14 
 15 
 16 
 17 *********************************/
 18 
 19 #include "stdafx.h"
 20 #include <iostream>
 21 using namespace std;
 22 
 23 
 24 
 25 
 26 void MergeSort(int* Arr,int Length)
 27 {
 28     if(!Arr||Length<=0)
 29         return;
 30     int Temp=0;
 31     for(int i=Length>>1;i<Length;i++)
 32     {
 33         Temp=Arr[i];
 34         for(int j=i-(Length>>1);j<i;j++)
 35         {
 36             if(Arr[j]>Arr[i])
 37             {
 38                 while(j<i)    //{1,2,3,4,8,5,7,9,12,32,34};  
 39                 {
 40                     Arr[i]=Arr[i-1];
 41                     i--;
 42                 }
 43                 Arr[j]=Temp;
 44             }
 45         }
 46     }
 47     for(int k=0;k<Length;k++)
 48         cout<<Arr[k]<<" ";
 49     cout<<endl;
 50 }
 51 
 52 
 53 template <typename T>
 54 void Swap(T& t1,T& t2)
 55 {
 56     T t=t1;
 57     t1=t2;
 58     t2=t;
 59 }
 60 
 61 template <typename T>
 62 void Reverse(T* Arr,size_t size)
 63 {
 64     if(!Arr) return;
 65     size_t b=0,e=size-1;
 66     while(b<e&&b<size&&e>0)
 67     {
 68         Swap(Arr[b++],Arr[e--]);
 69     }
 70 }
 71 
 72 
 73 template<typename T>
 74 void Exchange(T* Arr,size_t size,size_t n)
 75 {
 76     if(!Arr) return;
 77     Reverse(Arr,n);
 78     Reverse(Arr+n,size-n);
 79     Reverse(Arr,size);
 80 }
 81 
 82 
 83 template <typename T>
 84 void Merge(T* Arr,size_t Size,size_t Pos)
 85 {
 86      size_t First=0,Second=Pos;
 87      while(First<Second&&Second<Size)
 88      {
 89          while(Arr[First]<=Arr[Second]&&First<Second) First++;
 90          size_t MaxMove=0;
 91          while(Arr[First]>Arr[Second]&&Second<Size) MaxMove++,Second++;
 92          Exchange(&Arr[First],Second-First,Second-First-MaxMove);
 93          First+=MaxMove;
 94      }
 95 }
 96 
 97 template <typename T>
 98 void display(T* Arr, size_t n)
 99 {
100      if(!Arr) return ;
101      for (size_t i = 0; i < n; ++i)
102      {
103          printf("%d  ", Arr[i]);
104      }
105      printf("\n");
106 }
107 
108 template<typename T>
109 void MergeSort( T* Arr, size_t size )
110 {
111     if ( size <= 1 ) return;
112     MergeSort( Arr, size/2 );
113     MergeSort( Arr+size/2,size-size/2 );
114     Merge( Arr, size, size/2 );
115 }
116 
117 
118 
119 
120 
121 void Merge_Sort(int* Arr,int x,int y,int* T)
122 {
123     if(y-x>1)
124     {
125         int m=x+((y-x)>>1);
126         int p=x,q=m,i=x;
127         Merge_Sort(Arr,x,m,T);
128         Merge_Sort(Arr,m,y,T);
129         while(p<m||q<y)
130         {
131             if(q>=y||(p<m&&Arr[p]<=Arr[q]))
132                 T[i++]=Arr[p++];
133             else
134                 T[i++]=Arr[q++];
135         }
136         for(i=x;i<y;i++) 
137             Arr[i]=T[i];
138     }
139 }
140 
141 
142 void Test2()
143 {
144     int arr[] = {3,5,7,8,1,2,4,6};
145     int brr[8];
146     display(arr,sizeof(arr)/sizeof(int));
147     Merge_Sort(arr,0,8,brr);
148     display(arr, sizeof(arr)/sizeof(int));
149 }
150 
151 void Test1()
152 {
153     int arr[] = {3,5,7,8,1,2,4,6};
154     display(arr,sizeof(arr)/sizeof(int));
155     MergeSort(arr,sizeof(arr)/sizeof(int));
156     display(arr, sizeof(arr)/sizeof(int));
157 }
158 int main()  
159 {  
160     int a[11]={1,2,3,4,8,5,6,7,12,32,34};  
161     MergeSort(a,11);
162     for(int k=0;k<11;k++)  
163         cout<<a[k]<<" ";  
164     cout<<endl;
165     cout<<"Test1 have Begun!"<<endl;
166     Test1();
167     cout<<"Test2 have Begun!"<<endl;
168     Test2();
169     return 0;  
170 }