归并排序非递归和递归实现

归并排序就是将2个有序表组合成一个新的有序表。假定待排序表有n个元素，则可以看成是n个有序的子表，每个子表长度为1，然后两两归并…不停重复，直到合成一个长度为n的有序序列为止。

时间复杂度：每一趟归并为O(n),共log2n趟，所以时间为O(nlog2n) 空间复杂度：O(n) 稳定性：稳定

归并排序非递归实现:

#include <iostream> using namespace std; typedef int Type; void Merge(Type c[], Type d[], int l, int m, int r) { // 合并c[l:m]和c[m+1:r]到d[1:r] int i = l, j = m + 1, k = l; while (i <= m && j <= r) { if (c[i] <= c[j]) { d[k++] = c[i++]; } else { d[k++] = c[j++]; } } if (i > m) { for (int q = j; q <= r; q++) { d[k++] = c[q]; } } else { for (int q = i; q <= m; q++) { d[k++] = c[q]; } } } void MergePass(Type x[], Type y[], int s, int n) { // 合并大小为s的相邻子组 int i = 0; while (i <= n - 2 * s) { // 合并大小为s的相邻2段子数组 Merge(x, y, i, i + s - 1, i + 2 * s - 1); i = i + 2 * s; } // 剩下的元素少于2s if ( i + s < n ) { Merge(x, y, i, i + s - 1, n - 1); } else { for (int j = i; j <= n - 1; j++) { y[j] = x[j]; } } } void MergeSort(Type a[], int n) { Type *b = new Type[n]; int s = 1; while (s < n) { MergePass(a, b, s, n); // 合并到数组b s += s; MergePass(b, a, s, n); // 合并到数组a s += s; } delete[] b; } void print(Type a[], int n) { for (int i=0; i<n; ++i) { cout << a[i] << " "; } cout << endl; } int main(int argc, char *argv[]) { Type a[6] = {1, 5, 2, 3, 6, 4}; MergeSort(a, 6); print(a, 6); return 0; }

归并排序递归实现:

#include <iostream> using namespace std; typedef int Type; Type *B = new Type[6]; // 和数组A一样大 void Merge(Type A[], int low, int mid, int high) { int i, j, k; for (k = low; k <= high; ++k) { B[k] = A[k]; // 将A中所有元素复制到B } for (i = low, j = mid + 1, k = i; i <= mid && j <= high; ++k) { if (B[i] <= B[j]) { // 比较B的左右两段序列中的元素 A[k] = B[i++]; // 将较小值复制到A中 } else { A[k] = B[j++]; } } while (i <= mid) { A[k++] = B[i++]; // 若第一个表未检测完，复制 } while (j <= high) { A[k++] = B[j++]; // 若第二个表未检测完，复制 } } void MergeSort(Type A[], int low, int high) { if (low < high) { int mid = (low + high) / 2; MergeSort(A, low, mid); // 对左侧子序列进行递归排序 MergeSort(A, mid+1, high); // 对右侧子序列进行递归排序 Merge(A, low, mid, high); // 归并 } } void print(Type A[], int n) { for (int i=0; i<n; ++i) { cout << A[i] << " "; } cout << endl; } int main(int argc, char *argv[]) { Type a[6] = {1, 5, 2, 3, 6, 4}; MergeSort(a, 0, 5); print(a, 6); delete[] B; return 0; }