首页 > 代码库 > [数据结构]归并排序

[数据结构]归并排序

2024-11-08 10:54:02   203人阅读

归并排序

点击打开链接

[cpp] view plaincopy技术分享技术分享
 
  1. //将有二个有序数列a[first...mid]和a[mid...last]合并。     
  2. void mergearray(int a[], int first, int mid, int last, int temp[])    
  3. {    
  4.     int i = first, j = mid + 1;    
  5.     int m = mid,   n = last;    
  6.     int k = 0;    
  7.         
  8.     while (i <= m && j <= n)    
  9.     {    
  10.         if (a[i] <= a[j])    
  11.             temp[k++] = a[i++];    
  12.         else    
  13.             temp[k++] = a[j++];    
  14.     }    
  15.         
  16.     while (i <= m)    
  17.         temp[k++] = a[i++];    
  18.         
  19.     while (j <= n)    
  20.         temp[k++] = a[j++];    
  21.         
  22.     for (i = 0; i < k; i++)    
  23.         a[first + i] = temp[i];    
  24. }    
  25. void mergesort(int a[], int first, int last, int temp[])    
  26. {    
  27.     if (first < last)    
  28.     {    
  29.         int mid = (first + last) / 2;    
  30.         mergesort(a, first, mid, temp);    //左边有序     
  31.         mergesort(a, mid + 1, last, temp); //右边有序     
  32.         mergearray(a, first, mid, last, temp); //再将二个有序数列合并     
  33.     }    
  34. }    
  35.     
  36. bool MergeSort(int a[], int n)    
  37. {    
  38.     int *p = new int[n];    
  39.     if (p == NULL)    
  40.         return false;    
  41.     mergesort(a, 0, n - 1, p);    
  42.     delete[] p;    
  43.     return true;    
  44. }    

[数据结构]归并排序


联系
我们