//歸并排序

void mergeArray(int a[], int first, int mid, int last, int temp[]) //對(duì)兩個(gè)有序數(shù)列合并

{

   int i = first;

   int j = mid + 1;

   int m = mid;

   int n = last;

   int k = 0;

 

 //每次把兩個(gè)數(shù)列中較小的值存在temp中

   while(i <= m && j <= n)

   {

     if(a[i]<= a[j])

     {

       temp[k++] = a[i++];

     }

     else

     {

       temp[k++] = a[j++];

     }

   }

 //哪一個(gè)數(shù)列先完成拷貝就把另一個(gè)數(shù)列的剩余的值存在temp中

   while(i <= m)

   {

     temp[k++] = a[i++];

   }

   while(j <= n)

   {

     temp[k++] = a[j++];

   }

 

 //把temp中的值拷貝到a中

   for(int i = 0; i < k; ++i)

   {

     a[first+i] = temp[i];

   }

}

 

void mergeSort(int a[], int first, int last, int temp[])

{

   if(first < last)

   {

     int mid = (last + first)/2; //注意用加號(hào),不是減號(hào), 

     //將數(shù)組劃分成由單個(gè)數(shù)組成的數(shù)列,則就可看成是每個(gè)數(shù)列都是有序的,可以用mergeArray函數(shù)了

     mergeSort(a, first, mid, temp);

     mergeSort(a, mid+1, last, temp);

     mergeArray(a, first, mid, last, temp);

   }

}

 

bool MergeSort(int a[], int n)

{

   int *p = new int[n];

   if(p == NULL)

   {

     return false;

   }

   else

   {

     mergeSort(a, 0, n-1, p);

     delete[] p;

     return true;

   }

}

QQ截圖20160315092144.png