本页使用了标题或全文手工转换

归并排序

维基百科,自由的百科全书
跳转至: 导航搜索
归并排序
Merge-sort-example-300px.gif
分類 排序算法
數據結構 数组
最差時間複雜度
最優時間複雜度
平均時間複雜度
最差空間複雜度
一个归并排序的例子:对一个随机点的链表进行排序

归并排序英语:Merge sort,或mergesort),是建立在归并操作上的一种有效的排序算法,效率為O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

归并操作[编辑]

归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

迭代法[编辑]

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

遞歸法[编辑]

原理如下(假设序列共有n个元素):

  1. 将序列每相邻两个数字进行归并操作,形成个序列,排序后每个序列包含两个元素
  2. 将上述序列再次归并,形成个序列,每个序列包含四个元素
  3. 重复步骤2,直到所有元素排序完毕

實作範例[编辑]

C語言[编辑]

迭代版:

int min(int x, int y) {
	return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
	int* a = arr;
	int* b = (int*) malloc(len * sizeof(int*));
	int seg, start;
	for (seg = 1; seg < len; seg += seg) {
		for (start = 0; start < len; start += seg + seg) {
			int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
			int k = low;
			int start1 = low, end1 = mid;
			int start2 = mid, end2 = high;
			while (start1 < end1 && start2 < end2)
				b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
			while (start1 < end1)
				b[k++] = a[start1++];
			while (start2 < end2)
				b[k++] = a[start2++];
		}
		int* temp = a;
		a = b;
		b = temp;
	}
	if (a != arr) {
		int i;
		for (i = 0; i < len; i++)
			b[i] = a[i];
		b = a;
	}
	free(b);
}

遞歸版:

void merge_sort_recursive(int arr[], int reg[], int start, int end) {
	if (start >= end)
		return;
	int len = end - start, mid = (len >> 1) + start;
	int start1 = start, end1 = mid;
	int start2 = mid + 1, end2 = end;
	merge_sort_recursive(arr, reg, start1, end1);
	merge_sort_recursive(arr, reg, start2, end2);
	int k = start;
	while (start1 <= end1 && start2 <= end2)
		reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
	while (start1 <= end1)
		reg[k++] = arr[start1++];
	while (start2 <= end2)
		reg[k++] = arr[start2++];
	for (k = start; k <= end; k++)
		arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
	int reg[len];
	merge_sort_recursive(arr, reg, 0, len - 1);
}

C++[编辑]

迭代版:

template<typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能
void merge_sort(T arr[], int len) {
	T* a = arr;
	T* b = new T[len];
	for (int seg = 1; seg < len; seg += seg) {
		for (int start = 0; start < len; start += seg + seg) {
			int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
			int k = low;
			int start1 = low, end1 = mid;
			int start2 = mid, end2 = high;
			while (start1 < end1 && start2 < end2)
				b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
			while (start1 < end1)
				b[k++] = a[start1++];
			while (start2 < end2)
				b[k++] = a[start2++];
		}
		T* temp = a;
		a = b;
		b = temp;
	}
	if (a != arr) {
		for (int i = 0; i < len; i++)
			b[i] = a[i];
		b = a;
	}
	delete[] b;
}

遞歸版:

template<typename T>
void merge_sort_recursive(T arr[], T reg[], int start, int end) {
	if (start >= end)
		return;
	int len = end - start, mid = (len >> 1) + start;
	int start1 = start, end1 = mid;
	int start2 = mid + 1, end2 = end;
	merge_sort_recursive(arr, reg, start1, end1);
	merge_sort_recursive(arr, reg, start2, end2);
	int k = start;
	while (start1 <= end1 && start2 <= end2)
		reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
	while (start1 <= end1)
		reg[k++] = arr[start1++];
	while (start2 <= end2)
		reg[k++] = arr[start2++];
	for (k = start; k <= end; k++)
		arr[k] = reg[k];
}
template<typename T> //整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能
void merge_sort(T arr[], const int len) {
	T reg[len];
	merge_sort_recursive(arr, reg, 0, len - 1);
}

C#[编辑]

public static List<int> sort(List<int> lst)
{
    if (lst.Count <= 1)
    {
        return lst;
    }
    int mid = lst.Count / 2;
    List<int> left = new List<int>();//定义左侧List
    List<int> right = new List<int>();//定义右侧List
    
    //以下兩個循環把lst分為左右兩個List
    for (int i = 0; i < mid; i++)
    {
        left.Add(lst[i]);
    }
    for (int j = mid; j < lst.Count; j++)
    {
        right.Add(lst[j]);
    }
    left = sort(left);
    right = sort(right);
    return merge(left, right);
}
/// <summary>
/// 合併兩個已經排好序的List
/// </summary>
/// <param name="left">左側List</param>
/// <param name="right">右側List</param>
/// <returns></returns>
static List<int> merge(List<int> left, List<int> right)
{
    List<int> temp = new List<int>();
    while (left.Count > 0 && right.Count > 0)
    {
        if (left[0] <= right[0])
        {
            temp.Add(left[0]);
            left.RemoveAt(0);
        }
        else
        {
            temp.Add(right[0]);
            right.RemoveAt(0);
        }
    }
    if (left.Count > 0)
    {
        for (int i = 0; i < left.Count; i++)
        {
            temp.Add(left[i]);
        }
    }
    if (right.Count > 0)
    {
        for (int i = 0; i < right.Count; i++)
        {
            temp.Add(right[i]);
        }
    }
    return temp;
}

Ruby[编辑]

def merge(left, right)
  final = []
  until left.empty? or right.empty?
    final << (left.first < right.first ? left.shift : right.shift)
  end
  final + left + right
end

def merge_sort(array)
  return array if array.size < 2
  pivot = array.size / 2
  merge(merge_sort(array[0...pivot]), merge_sort(array[pivot..-1]))
end

Java[编辑]

遞歸版:

static void merge_sort_recursive(int[] arr, int[] reg, int start, int end) {
	if (start >= end)
		return;
	int len = end - start, mid = (len >> 1) + start;
	int start1 = start, end1 = mid;
	int start2 = mid + 1, end2 = end;
	merge_sort_recursive(arr, reg, start1, end1);
	merge_sort_recursive(arr, reg, start2, end2);
	int k = start;
	while (start1 <= end1 && start2 <= end2)
		reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
	while (start1 <= end1)
		reg[k++] = arr[start1++];
	while (start2 <= end2)
		reg[k++] = arr[start2++];
	for (k = start; k <= end; k++)
		arr[k] = reg[k];
}
public static void merge_sort(int[] arr) {
	int len = arr.length;
	int[] reg = new int[len];
	merge_sort_recursive(arr, reg, 0, len - 1);
}

迭代版:

public static void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    int block, start;
		
    for(block = 1; block < len ; block *= 2) {
        for(start = 0; start <len; start += 2 * block) {
            int low = start;
            int mid = (start + block) < len ? (start + block) : len;
            int high = (start + 2 * block) < len ? (start + 2 * block) : len;
            //两个块的起始下标及结束下标
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            //开始对两个block进行归并排序
            while (start1 < end1 && start2 < end2) {
	        result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
            }
            while(start1 < end1) {
	        result[low++] = arr[start1++];
            }
            while(start2 < end2) {
	        result[low++] = arr[start2++];
            }
        }
	int[] temp = arr;
	arr = result;
	result = temp;
    }
    result = arr;       
}

PHP[编辑]

function merge_sort($arr) {
	$len = count($arr);
	if ($len <= 1)
		return $arr;
	$half = ($len>>1) + ($len & 1);
	$arr2d = array_chunk($arr, $half);
	$left = merge_sort($arr2d[0]);
	$right = merge_sort($arr2d[1]);
	while (count($left) && count($right))
		if ($left[0] < $right[0])
			$reg[] = array_shift($left);
		else
			$reg[] = array_shift($right);
	return array_merge($reg, $left, $right);
}

$arr = array(21, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70);
$arr = merge_sort($arr);
for ($i = 0; $i < count($arr); $i++) {
	echo $arr[$i] . ' ';
}

Python[编辑]

from collections import deque

def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    def merge(left, right):
        merged,left,right = deque(),deque(left),deque(right)
        while left and right:
            merged.append(left.popleft() if left[0] <= right[0] else right.popleft())  # deque popleft is also O(1)
        merged.extend(right if right else left)
        return list(merged)

    middle = int(len(lst) // 2)
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])
    return merge(left, right)

Erlang[编辑]

%%排序外壳
sort([]) -> [];
sort([E]) -> [E];
sort(L) ->
	{L1, L2} = lists:split(round(length(L)/2), L),
	merge(sort(L1), sort(L2)).

%%归并操作
merge([], L2) -> L2;
merge(L1, []) -> L1;
merge([H1|T1]=L1, [H2|T2]=L2) ->
	if H1H2 ->  [H1] ++ merge(T1, L2);
	   true	 ->  [H2] ++ merge(L1, T2)
	end.

Javascript[编辑]

Array.prototype.merge_sort = function() {
	var merge = function(left, right) {
		var final = [];
		while (left.length && right.length)
			final.push(left[0] <= right[0] ? left.shift() : right.shift());
		return final.concat(left.concat(right));
	};
	var len = this.length;
	if (len < 2) return this;
	var mid = len / 2;
	return merge(this.slice(0, parseInt(mid)).merge_sort(), this.slice(parseInt(mid)).merge_sort());
};

算法复杂度[编辑]

比较操作的次数介于赋值操作的次数是。归并算法的空间复杂度为:Θ(n)

外部連結[编辑]