1.归并排序的实现
文章图片
通常是通过二分法达到logn这样一个层级，然后每一层级用O(n)级别的算法合并.
归并排序需要额外的存储空间来完成排序
文章图片
【1.归并排序的实现】i,j指向的是当前正在考虑的元素，k表示需要放的位置 最左边的元素l,最右边的元素r, 中间这个位置放在第一个 排好序的数组的最后一个位置叫m.
代码部分：
template
void mergeSort(T arr[], int n){
__mergeSort( arr, 0 ,n-1 );
//对数组的不同部分做归并 ,该区间为前闭后闭.
}
// 递归使用归并排序,对arr[l...r]的范围进行排序template
void __mergeSort(T arr[] ,int l, int r){
if( l >= r ) //数组个数为1或为空
return;
int mid = (l + r) / 2;
//二分查找中，当l r都是非常大的int的话，相加可能发生溢出.
//对左右两个部分分别进行归并排序.
__mergeSort(arr, l, mid);
__mergeSort(arr, mid+1, r);
//合并两个数组
__merge(arr, l, mid, r);
}//将arr[l...mid]和arr[mid+l...r]两部分进行归并
template
void __merge(T arr[], int l, int mid, int r){T aux[r-l+1];
for( int i = l;
i <= r;
i++ )
aux[i-l] = arr[i];
//有l的偏移//这里要说一下，这个i和j是作用在arr上的，但它不是用来操作arr的值的.
//arr的值是通过k来操作的, i和j的作用是用来控制范围同时操作aux数组.
//arr数组的i和j是和aux数组的i-l和j-l同步变化的.
//也可以直接将i和j作用在aux数组上，不过比较麻烦，因为aux的范围是[0, r-l+1]，还要求mid的值，这样式子的值就比较复杂了.int i = l, j = mid + 1;
for( int k = l;
k <= r;
k++ ){
//看arr[k]的位置应该放谁
if( i > mid ) {
arr[k] = aux[j-l];
j++;
}
else if( j > r ){
arr[k] = aux[i-l];
i++;
}
else if( aux[i-l] 测试归并排序：
文章图片
推荐阅读
- 热闹中的孤独
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 布丽吉特，人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事，我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量