归并排序及其非递归实现

个人主页：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);