个人主页：Lei宝啊
愿所有美好如期而遇
目录
归并排序递归实现
图示：
代码：
先分再归并，像是后序一般。
//归并排序 void MergeSort(int* arr, int left, int right) { int* temp = (int*)malloc(sizeof(int) * (right)); if (temp == NULL) { perror("malloc fail"); } _MergeSort(arr, temp, left, right - 1); free(temp); } void _MergeSort(int* arr, int* temp, int left, int right) { if (left >= right) return; int mid = (left + right) / 2; int begin1 = left; int begin2 = mid + 1; int end1 = mid; int end2 = right; _MergeSort(arr, temp, left, mid); _MergeSort(arr, temp, mid + 1, right); int index = left; while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] < arr[begin2]) { temp[index++] = arr[begin1++]; } else { temp[index++] = arr[begin2++]; } } while (begin1 <= end1) { temp[index++] = arr[begin1++]; } while (begin2 <= end2) { temp[index++] = arr[begin2++]; } memcpy(arr + left, temp + left, sizeof(int) * (right - left + 1)); }
归并排序非递归实现
这里的非递归实现不可借助栈实现，因为返回去的时候，不能使之有序。
代码：
//归并排序非递归 void MergeSortNonR(int* arr, int n) { int* temp = (int*)malloc(sizeof(int) * n); if (temp == NULL) { perror("malloc fail"); } int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { //归并的区间 int begin1 = i; int end1 = i + gap - 1; int begin2 = i + gap; int end2 = i + gap * 2 - 1; if (begin2 > n - 1) { break; } if (end2 > n - 1) { end2 = n - 1; } int index = i;//每次归并从i位置开始 while (begin1 <= end1 && begin2 <= end2) { if (arr[begin1] < arr[begin2]) { temp[index++] = arr[begin1++]; } else { temp[index++] = arr[begin2++]; } } while (begin1 <= end1) { temp[index++] = arr[begin1++]; } while (begin2 <= end2) { temp[index++] = arr[begin2++]; } memcpy(arr + i, temp + i, sizeof(int) * (end2 - i + 1)); } gap *= 2; } free(temp); }
时间复杂度O(n*logn),空间复杂度O(N);
