归并排序
时间复杂度：平均、最好、最坏都是O(nlogn)
空间复杂度：O(n)
稳定性：稳定
算法解析
- 归并排序是使用了归并的思想，归并是将两个有序序列合到一个序列并使其有序
- 同时归并排序也使用了分治思想
- 归并排序分为 从上到下 和 从下到上 两种方式
算法描述（来源于百度）
归并操作的工作原理如下：
- 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针超出序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
图片解析：
merge.jpg
上图已经很清楚了解释了归并排序的步骤及思路！如果还觉得不清晰，看下动画演示。
动画演示：
mergeSort.gif
一、从上到下的方式实现
c实现
void mergeSort(int *arr,int s,int mid,int e) {
int *tmp = (int *)malloc((e-s+1)*sizeof(int));
int i = s;
int j = mid+1;
int k = 0;
while (i<=mid && j<=e) {
if (arr[i] < arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
while (i<=mid) {
tmp[k++] = arr[i++];
}
while (j<=e) {
tmp[k++] = arr[j++];
}
for (int l = 0; l<k; l++) {
arr[l+s] = tmp[l];
}
free(tmp);
tmp = NULL;
}
void merge(int *arr,int s,int e) {
if (arr == NULL || s >= e) { return; }
int mid = (s+e)/2;
merge(arr, s, mid);
merge(arr, mid+1, e);
mergeSort(arr, s, mid, e);
}
OC实现
void mergeSort(NSMutableArray *arr,int s,int mid,int e) {
NSMutableArray *arrM = [NSMutableArray array];
int i = s;
int j = mid + 1;
while (i<=mid && j <= e) {
if ([arr[i] intValue] <= [arr[j] intValue]) {
[arrM addObject:arr[i++]];
} else {
//k+=(mid-i+1);逆序数
[arrM addObject:arr[j++]];
}
}
while (i<=mid) {
[arrM addObject:arr[i++]];
}
while (j<=e) {
[arrM addObject:arr[j++]];
}
for (int k = 0; k<arrM.count; k++) {
arr[k+s] = arrM[k];
}
}
void merge(NSMutableArray *arr,int s,int e) {
if (s >= e) { return; }
int mid = (s+e)/2;
merge(arr, s, mid);
merge(arr, mid+1, e);
mergeSort(arr, s, mid, e);
}
Swift实现
func mergeSort(arr:inout [Int],start:Int,end:Int) -> Void {
if arr.count == 0 || start >= end { return }
let mid = (start+end)/2;
mergeSort(arr: &arr, start: start, end: mid)
mergeSort(arr: &arr, start: mid+1, end: end)
//归并
merge(arr: &arr, start: start, mid: mid, end: end)
}
func merge(arr:inout [Int],start:Int,mid:Int,end:Int) -> Void {
if arr.count == 0 || start >= end { return }
var tmp = Array.init(repeating: 0, count: end-start+1)
var i = start
var j = mid+1
var k = 0
while i <= mid && j <= end {
if arr[i] <= arr[j] {
tmp[k] = arr[i]
i+=1
} else {
tmp[k] = arr[j]
j+=1
}
k+=1
}
//把剩余的加进来
while i<=mid {
tmp[k] = arr[i]
i+=1
k+=1
}
while j<=end {
tmp[k] = arr[j]
j+=1
k+=1
}
for l in 0..<k {
arr[l+start] = tmp[l]
}
}
以下实现均来源于网络，未验证
js实现
function mergeSort(arr) { // 采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
Python 代码实现
def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))
def merge(left,right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0));
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0));
while right:
result.append(right.pop(0));
return result
go实现
func mergeSort(arr []int) []int {
length := len(arr)
if length < 2 {
return arr
}
middle := length / 2
left := arr[0:middle]
right := arr[middle:]
return merge(mergeSort(left), mergeSort(right))
}
func merge(left []int, right []int) []int {
var result []int
for len(left) != 0 && len(right) != 0 {
if left[0] <= right[0] {
result = append(result, left[0])
left = left[1:]
} else {
result = append(result, right[0])
right = right[1:]
}
}
for len(left) != 0 {
result = append(result, left[0])
left = left[1:]
}
for len(right) != 0 {
result = append(result, right[0])
right = right[1:]
}
return result
}
Java 代码实现
public class MergeSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
if (arr.length < 2) {
return arr;
}
int middle = (int) Math.floor(arr.length / 2);
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(sort(left), sort(right));
}
protected int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int i = 0;
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while (left.length > 0) {
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
}
PHP 代码实现
function mergeSort($arr)
{
$len = count($arr);
if ($len < 2) {
return $arr;
}
$middle = floor($len / 2);
$left = array_slice($arr, 0, $middle);
$right = array_slice($arr, $middle);
return merge(mergeSort($left), mergeSort($right));
}
function merge($left, $right)
{
$result = [];
while (count($left) > 0 && count($right) > 0) {
if ($left[0] <= $right[0]) {
$result[] = array_shift($left);
} else {
$result[] = array_shift($right);
}
}
while (count($left))
$result[] = array_shift($left);
while (count($right))
$result[] = array_shift($right);
return $result;
}
网友评论