归并排序 merge sort

https://github.com/hotwater99/practice_datastructure_and_algorithm.git

《数据结构与算法分析——C语言描述》机械工业出版社，原书第2版，7.6

归并排序是将待排序的数组分为两个子数组，分别排好序，然后再合并到一起。

使用到了分治的策略。

归并排序：

  1 void Merge(int array[], int tmpArray[], int leftPos, int rightPos, int rightEnd)
  2 {
  3   int i, leftEnd, total, tmp_pos;
  4 
  5   leftEnd = rightPos - 1;
  6   total = rightEnd - leftPos + 1;
  7   tmp_pos = leftPos;
  8 
  9   while (leftPos <= leftEnd && rightPos <= rightEnd) {
 10     if (array[leftPos] < array[rightPos]) {
 11       tmpArray[tmp_pos++] = array[leftPos++];
 12     }
 13     else {
 14       tmpArray[tmp_pos++] = array[rightPos++];
 15     }
 16   }
 17 
 18   while (leftPos <= leftEnd) {
 19     tmpArray[tmp_pos++] = array[leftPos++];
 20   }
 21   while (rightPos <= rightEnd) {
 22     tmpArray[tmp_pos++] = array[rightPos++];
 23   }
 24 
 25   for (i = 0; i < total; i++, rightEnd--) {
 26     array[rightEnd] = tmpArray[rightEnd];
 27   }
 28 }
 29 
 30 void MSort(int array[], int tmpArray[], int left, int right)
 31 {
 32   int center;
 33 
 34   if (left < right) {
 35     center = (left + right) / 2;
 36     MSort(array, tmpArray, left, center);
 37     MSort(array, tmpArray, center + 1, right);
 38     Merge(array, tmpArray, left, center + 1, right);
 39   }
 40 }
 41 
 42 void MergeSort(int array[], int N)
 43 {
 44   int *tmp_array;
 45 
 46   tmp_array = (int *)malloc(N * sizeof(int));
 47   if (tmp_array != NULL) {
 48     MSort(array, tmp_array, 0, N - 1);
 49     free(tmp_array);
 50   }
 51   else {
 52     // error
 53   }
 54 }

完整代码：

  1 #include <iostream>
  2 #include <ctime>
  3 
  4 using namespace std;
  5 
  6 #define random(x)       (rand()%x)
  7 #define ARRAY_LENTH     10
  8 
  9 void Merge(int array[], int tmpArray[], int leftPos, int rightPos, int rightEnd)
 10 {
 11   int i, leftEnd, total, tmp_pos;
 12 
 13   leftEnd = rightPos - 1;
 14   total = rightEnd - leftPos + 1;
 15   tmp_pos = leftPos;
 16 
 17   while (leftPos <= leftEnd && rightPos <= rightEnd) {
 18     if (array[leftPos] < array[rightPos]) {
 19       tmpArray[tmp_pos++] = array[leftPos++];
 20     }
 21     else {
 22       tmpArray[tmp_pos++] = array[rightPos++];
 23     }
 24   }
 25 
 26   while (leftPos <= leftEnd) {
 27     tmpArray[tmp_pos++] = array[leftPos++];
 28   }
 29   while (rightPos <= rightEnd) {
 30     tmpArray[tmp_pos++] = array[rightPos++];
 31   }
 32 
 33   for (i = 0; i < total; i++, rightEnd--) {
 34     array[rightEnd] = tmpArray[rightEnd];
 35   }
 36 }
 37 
 38 void MSort(int array[], int tmpArray[], int left, int right)
 39 {
 40   int center;
 41 
 42   if (left < right) {
 43     center = (left + right) / 2;
 44     MSort(array, tmpArray, left, center);
 45     MSort(array, tmpArray, center + 1, right);
 46     Merge(array, tmpArray, left, center + 1, right);
 47   }
 48 }
 49 
 50 void MergeSort(int array[], int N)
 51 {
 52   int *tmp_array;
 53 
 54   tmp_array = (int *)malloc(N * sizeof(int));
 55   if (tmp_array != NULL) {
 56     MSort(array, tmp_array, 0, N - 1);
 57     free(tmp_array);
 58   }
 59   else {
 60     // error
 61   }
 62 }
 63 
 64 int main() {
 65   int test_array[ARRAY_LENTH];
 66   int i, N = ARRAY_LENTH;
 67   clock_t start_time, stop_time;
 68 
 69   for (i = 0; i < N; i++) {
 70     test_array[i] = random(N);
 71   }
 72 
 73   if (N <= 100) {
 74     cout << "raw : ";
 75     for (i = 0; i < N; i++) {
 76       cout << test_array[i] << " ";
 77     }
 78     cout << endl;
 79   }
 80 
 81   start_time = clock();
 82 
 83   MergeSort(test_array, N);
 84 
 85   stop_time = clock();
 86 
 87   if (N <= 100) {
 88     cout << "sort: ";
 89     for (i = 0; i < N; i++) {
 90       cout << test_array[i] << " ";
 91     }
 92     cout << endl;
 93   }
 94 
 95   cout << "MergeSort(" << N << ")..." << endl;
 96   cout << "total time used: ";
 97   cout << (double)(stop_time - start_time) / CLOCKS_PER_SEC << "s" << endl;
 98 
 99   system("pause");
100 
101   return 0;
102 }

测试结果

N=10

raw : 1 7 4 0 9 4 8 8 2 4
sort: 0 1 2 4 4 4 7 8 8 9
MergeSort(10)...
total time used: 0s

N=100

raw : 41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36 91 4 2 53 92 82 21 16 18 95 47 26 71 38 69 12 67 99 35 94 3 11 22 33 73 64 41 11 53 68 47 44 62 57 37 59 23 41 29 78 16 35 90 42 88 6 40 42 64 48 46 5 90 29 70 50 6 1 93 48 29 23 84 54 56 40 66 76 31 8 44 39 26 23 37 38 18 82 29 41
sort: 0 1 2 3 4 5 5 6 6 8 11 11 12 16 16 18 18 21 22 23 23 23 24 26 26 27 27 29 29 29 29 31 33 34 35 35 36 37 37 38 38 39 40 40 41 41 41 41 42 42 42 44 44 45 46 47 47 48 48 50 53 53 54 56 57 58 59 61 62 62 64 64 64 66 67 67 68 69 69 70 71 73 76 78 78 81 82 82 84 88 90 90 91 91 92 93 94 95 95 99
MergeSort(100)...
total time used: 0s

N=1000

MergeSort(1000)...
total time used: 0s

N=10000

MergeSort(10000)...
total time used: 0.001s

N=100000

MergeSort(100000)...
total time used: 0.015s