排序
归并排序
归并排序和快速排序相反, 快排是先排后分再合并, 归并则是先分后排再合并
归并排序时间复杂度是 O(n logn)
分析: ----------------------------------------------------------------- // 待排序的序列长度
- ----------------------------- ----------------------------------
- ------------- -------------- -------------- ------------------
- ......
- - - - - - - - - - - - - - - - - - - - - - - - - - // 总共 logn 层
待排序列会被分成 logn 层, 对于每层我们需要执行 n 次操作, 所以时间复杂度就是 O(n logn)
要是不太明白最下面有张图, 看着图容易理解
模板:
- void merge_sort(int q[], int l, int r)
- {
- if(l>= r) return;
- int mid = l + r>> 1;
- merge_sort(q, l, mid);
- merge_sort(q, mid + 1, r);
- int k = 0, i = l, j = mid + 1;
- while(i <= mid && j <= r)
- if(q[i] < q[j]) temp[k++] = q[i++];
- else temp[k++] = q[j++];
- while(i <= mid) tmep[k++] = q[i++];
- while(j <= r) temp[k++] = q[j++];
- for(int i = l, j = 0; j <= r; i ++, j ++)
- q[i] = temp[j];
- }
图片
来源: https://www.cnblogs.com/chuyds/p/10941073.html