简介
归并排序 (Merge sort),是创立在归并操作上的一种无效的排序算法,其工夫复杂度为 O(N*logN)。该算法是采纳分治法(Divide and Conquer)的一个十分典型的利用,且各层分治递归能够同时进行。
归并排序算法应用了分而治之的思维:
- 分:在数组的两头地位,将数组一分为二,将原数组排序的问题转换为排序两个子数组的问题;
- 治:直到子数组的长度为 1 时,开始向上合并,一直地将两个曾经排序了的子数组归并成一个有序数组,直至归并至失去原数组的解。
实现思路
-
递归:
- 计算中点的地位
mid
,将数组一分为二,并对这两个子数组递归解决,即mergeSort(arr, l, mid)
;mergeSort(arr, mid+1, r)
; - 直到
l >= r
时进行递归。
- 计算中点的地位
-
合并
- 暂存
arr
中区间[l, r]
的元素到长期数组中; -
合并左右子数组:
- 循环遍历长期数组
temp
; - 用
i
和j
别离指向左右子数组的第一个元素,用k
指向原数组中l
的地位; - 当
i
大于左子数组的右边界时,阐明左子数组的元素曾经归并实现,因而增加temp[j - l]
,并执行j++
; - 当
j
大于右子数组的右边界时,阐明右子数组的元素曾经归并实现,因而增加temp[i - l]
,并执行i++
; - 当
temp[i - l]
<=temp[j - l]
时,增加temp[i - l]
,并执行i++
; - 否则增加
temp[j - l]
,并执行j++
;
- 循环遍历长期数组
- 暂存
须要留神的是:
- 长期数组 temp 的索引是从 0 到
r - l
的 ; - 在循环遍历长期数组时,应该先判断 i 和 j 是否出界,再判断 i 和 j 所指向的元素哪个大 。
例子
对数组 [5 , 3, 1, 2, 4, 7, 8, 2] 进行归并排序的过程:
归并
已知两个有序数组 arr1
和 arr2
别离为 [1, 2, 4]
、[3, 5]
,如何把这两个有序数组归并成一个有序数组?
<?php
function mergeSortedArr($arr1, $arr2)
{$arr = [];
$len1 = count($arr1);
$len2 = count($arr2);
$len = $len1 + $len2;
$k = $i = $j = 0;
while($k < $len) {if ($i >= $len1) {$arr[] = $arr2[$j];
$j ++;
} elseif ($j >= $len2) {$arr[] = $arr1[$i];
$i++;
} elseif ($arr1[$i] <= $arr2[$j]) {$arr[] = $arr1[$i];
$i ++;
} elseif ($arr1[$i] > $arr2[$j]) {$arr[] = $arr2[$j];
$j ++;
}
$k ++;
}
return $arr;
}
已知一个数组在区间 [0, mid]
和 [mid+1, len - 1]
都是有序的,其中 len
为数组的长度,即 len
= count(arr)
;mid
为数组的两头地位,即 mid
= floor(len / 2)
。例如数组 arr 为 [1, 2, 4, 3, 5]
,其中 mid
和 len
的值别离为:
len
=count(arr)
= 5;mid
=floor(5 / 2)
= 2;
能够看出数组 arr
在区间 [0, 2]
是有序的,即子数组 [1, 2, 4]
是有序的,在区间 [3, 4]
是有序的,即子数组 [3, 5]
是有序的。问如何把 arr
变成一个有序的数组?
<?php
function merge($arr, $l, $mid, $r)
{$temp = copyOfRange($arr, $l, $r + 1);
$i = $l;
$j = $mid + 1;
for ($k = $l; $k <= $r; $k++) {if ($i > $mid) {$arr[$k] = $temp[$j - $l];
$j ++;
} elseif ($j > $r) {$arr[$k] = $temp[$i - $l];
$i ++;
} elseif ($temp[$i - $l] <= $temp[$j - $l]) {$arr[$k] = $temp[$i - $l];
$i ++;
} else {$arr[$k] = $temp[$j - $l];
$j ++;
}
}
return $arr;
}
function copyOfRange($arr, $l, $r)
{$temp = [];
for ($i = $l; $i < $r; $i++) {$temp[] = $arr[$i];
}
return $temp;
}
代码
<?php
class MergeSort
{public function sort(&$arr)
{$this->implementSort($arr, 0, count($arr) - 1);
}
protected function implementSort(&$arr, $l, $r)
{if ($l >= $r) {return;}
$mid = floor(($l + $r)/2);
$this->implementSort($arr, $l, $mid);
$this->implementSort($arr, $mid+1, $r);
$this->merge($arr, $l, $mid, $r);
}
protected function merge(&$arr, $l, $mid, $r)
{$temp = $this->copyOfRange($arr, $l, $r + 1);
$i = $l;
$j = $mid + 1;
for ($k = $l; $k <= $r; $k++) {if ($i > $mid) {$arr[$k] = $temp[$j - $l];
$j ++;
} elseif ($j > $r) {$arr[$k] = $temp[$i - $l];
$i ++;
} elseif ($temp[$i - $l] <= $temp[$j - $l]) {$arr[$k] = $temp[$i - $l];
$i ++;
} else {$arr[$k] = $temp[$j - $l];
$j ++;
}
}
}
protected function copyOfRange($arr, $l, $r)
{$temp = [];
for ($i = $l; $i < $r; $i++) {$temp[] = $arr[$i];
}
return $temp;
}
}
优化
- 优化 1:判断是否须要 merge;
- 优化 2:对小规模数据应用插入排序;
- 优化 3:只创立一个长期空间。
自底向上
当前有工夫再回来补上。
变式
剑指 Offer 51. 数组中的逆序对:
在数组中的两个数字,如果后面一个数字大于前面的数字,则这两个数字组成一个逆序对。输出一个数组,求出这个数组中的逆序对的总数。
示例:
输出: [7,5,6,4]
输入: 5
限度:
0 <= 数组长度 <= 50000
这道题是逆序排序的变式,它不间接考逆序排序怎么写,而是考查解题人对逆序排序过程的相熟水平。
参考
- 【算法】排序算法之归并排序
- 「排序算法」归并排序