归并排序

归并排序是"分治思想"的典型例子，分治思想分为三个步骤： 分解、解决子问题、合并。

伪代码

c语言实现： #include<iostream> using namespace std; int a[100]={0,1,2,3,4,5,6,7,8,9}; void Merge(int l, int mid, int r) { int t[100]; for(int i = l; i <= r; i++) { t[i] = a[i]; } int i = l, j = mid+1, k = 0; //初始化操作 // 遍历子数组，进行合并 while(i <= mid && j <= r) { if (t[i] <= t[j]) { a[l+k] = t[i]; i++; } else { a[l+k] = t[j]; j++; } k++; } // 将剩余的子数组赋值进原数组 while(i <= mid) { a[l+k] = t[i++]; k++; } while(j <= r) { a[l+k] = t[j++]; k++; } return; } void MergeSort(int l, int r) { if (l >= r) return;//递归终止条件 int mid = (l + r)/2; MergeSort(l, mid); // MergeSort(mid+1, r); // 递归求解子问题 Merge(l, mid, r); // 合并子问题 return; } int main() { MergeSort(0,9); for (int i = 0; i < 10; i++) { cout << a[i] << " "; } return 0; } 时间复杂度分析 递归式为$T(n)=T(\frac{n}{2})+n$ 利用主定理，或者递归树方法求得其时间复杂度为$O(nlogn)$