排序算法的数组实现 -- 合并排序（三）

[cpp]
static const int Sentinel_Card = 100000;//哨兵，假设元素值都比它小  
void static Merger(int *a, int p, int q, int r) 
{ 
    int L_Size = q - p + 1; 
    int R_Size = r - q; 
     
    int *a1 = new int[L_Size + 1]; 
    int *a2 = new int[R_Size + 1]; 
 
    for (int i = 0; i < L_Size; i++) 
        a1[i] = a[p + i]; 
     
    a1[L_Size] = Sentinel_Card;  
     
    for (int i = 0; i < R_Size; i++) 
    { 
        a2[i] = a[q + 1 + i]; 
    } 
    a2[R_Size] = Sentinel_Card; 
     
    int m = 0, n = 0; 
    for (int i = p; i <= r; i ++) 
    { 
        if(a1[m] < a2[n]) 
        { 
            a[i] = a1[m]; 
            m++; 
        } 
        else 
        { 
            a[i] = a2[n]; 
            n++; 
        } 
 
    } 
 
} 
 
void Merger_Sort(int *a, int p, int r) 
{ 
    if(p < r) 
    { 
        int q = (p + r)/2; 
        Merger_Sort(a, p, q); 
        Merger_Sort(a, q + 1, r); 
        Merger(a, p, q, r); 
    } 
} 

static const int Sentinel_Card = 100000;//哨兵，假设元素值都比它小
void static Merger(int *a, int p, int q, int r)
{
 int L_Size = q - p + 1;
 int R_Size = r - q;
 
 int *a1 = new int[L_Size + 1];
 int *a2 = new int[R_Size + 1];

 for (int i = 0; i < L_Size; i++)
  a1[i] = a[p + i];
 
 a1[L_Size] = Sentinel_Card;
 
 for (int i = 0; i < R_Size; i++)
 {
  a2[i] = a[q + 1 + i];
 }
 a2[R_Size] = Sentinel_Card;
 
 int m = 0, n = 0;
 for (int i = p; i <= r; i ++)
 {
  if(a1[m] < a2[n])
  {
   a[i] = a1[m];
   m++;
  }
  else
  {
   a[i] = a2[n];
   n++;
  }

 }

}

void Merger_Sort(int *a, int p, int r)
{
 if(p < r)
 {
  int q = (p + r)/2;
  Merger_Sort(a, p, q);
  Merger_Sort(a, q + 1, r);
  Merger(a, p, q, r);
 }
}

补充：软件开发 , C++ ,

上一个：排序算法的数组实现 -- 合并排序（五）
下一个：排序算法的数组实现 -- 堆排序（二）