归并字面上的意思是合并,归并算法的核心思想是分治法,就是将一个数组一刀切两半,递归切,直到切成单个元素,然后重新组装合并,单个元素合并成小数组,两个小数组合并成大数组,直到最终合并完成,排序完毕。
我们以[ 8,2,5,9,7 ]
这组数字来举例
首先,一刀切两半:
再切:
再切:
粒度切到最小的时候,就开始归并
数据量设定的比较少,是为了方便图解,数据量为单数,是为了让你看到细节,下面我画了一张更直观的图可能你会更喜欢:
void sort(vector<int> &arr) { vector<int> tmp(arr.size()); sort(arr, tmp, 0, arr.size()-1); } void sort(vector<int> &arr, vector<int> &tmp, int start, int end) { if(end <= start) return; } void sort(vector<int> &arr, vector<int> &tmp, int start, int end) { if(end <= start) return; int mid = start + (end - start) / 2; sort(arr, tmp, start, mid); sort(arr, tmp, mid+1, end); merge(arr, tmp, start, mid, end); } void merge(vector<int>& arr, vector<int>& tmp, int start, int mid, int end) { for(int i = start; i <= end; i++) { tmp[s] = arr[s]; } int left = start; int right = mid +1; for(int j = start; j <= end; j++) { if(left > mid) { //如果左边的首位下标大于中部下标,证明左边的数据已经排完了。 arr[j] = tmp[right++]; } else if(right > end) { //如果右边的首位下标大于了数组长度,证明右边的数据已经排完了。 arr[j] = tmp[left++]; } else if(tmp[right] < tmp[left]) { //将右边的首位排入,然后右边的下标指针+1。 arr[j] = tmp[right++]; } else { //将左边的首位排入,然后左边的下标指针+1。 arr[j] = tmp[left++]; } } }
我们可以发现 merge 方法中只有一个 for 循环,直接就可以得出每次合并的时间复杂度为 \(O(n)\) ,而分解数组每次对半切割,属于对数时间 \(O(\log n)\) ,合起来等于 \(O(\log_2{n})\) ,也就是说,总的时间复杂度为 \(O(n\log n)\) 。