归并排序

归并排序
使用合併排序為一列數字進行排序的過程
概况
類別排序算法
資料結構数组
复杂度
平均時間複雜度
最坏时间复杂度
最优时间复杂度
空間複雜度
最佳解有时是
相关变量的定义
使用合併排序為一列數字進行排序的過程

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

概述

采用分治法:

  • 分割：递归地把当前序列平均分割成两半。
  • 整合：在保持元素顺序的同时将上一步得到的子序列整合到一起（归并）。

归并操作

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

递归法（Top-down）

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

迭代法（Bottom-up）

原理如下（假设序列共有个元素）：

  1. 将序列每相邻两个数字进行归并操作，形成个序列，排序后每个序列包含两/一个元素
  2. 若此时序列数不是1个则将上述序列再次归并，形成个序列，每个序列包含四/三个元素
  3. 重复步骤2，直到所有元素排序完毕，即序列数为1

實作範例

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 * 2) {
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, 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 mergeSort_conquer(int* array, int left, int mid, int right, int* temp) {
    // [left, mid]和[mid+1, right]两个有序数组
    int i = left;
    int j = mid + 1;
    int index = 0;
    while (i <= mid && j <= right) {
        if (array[i] < array[j]) {
            temp[index++] = array[i++];
        } else {
            temp[index++] = array[j++];
        }
    }
    // 剩余元素直接放入temp
    while (i <= mid) {
        temp[index++] = array[i++];
    }
    while (j <= right) {
        temp[index++] = array[j++];
    }
    // 放回原数组
    index = 0;
    while (left <= right) {
        array[left++] = temp[index++];
    }
}

// 分治-分
void mergeSort_divide(int* array, int left, int right, int* temp) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        // 左边归并排序
        mergeSort_divide(array, left, mid, temp);
        // 右边归并排序
        mergeSort_divide(array, mid + 1, right, temp);
        // 合并两个有序序列
        mergeSort_conquer(array, left, mid, right, temp);
    }
}

void mergeSort(int* array, int size) {
    int* temp = (int*)malloc(sizeof(int) * size);
    mergeSort_divide(array, 0, size - 1, temp);
}

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;
}

遞歸版： 

void Merge(vector<int> &Array, int front, int mid, int end) {
    // preconditions:
    // Array[front...mid] is sorted
    // Array[mid+1 ... end] is sorted
    // Copy Array[front ... mid] to LeftSubArray
    // Copy Array[mid+1 ... end] to RightSubArray
    vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
    vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
    int idxLeft = 0, idxRight = 0;
    LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
    RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
    // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
    for (int i = front; i <= end; i++) {
        if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {
            Array[i] = LeftSubArray[idxLeft];
            idxLeft++;
        } else {
            Array[i] = RightSubArray[idxRight];
            idxRight++;
        }
    }
}

void MergeSort(vector<int> &Array, int front, int end) {
    if (front >= end)
        return;
    int mid = front + (end - front) / 2;
    MergeSort(Array, front, mid);
    MergeSort(Array, mid + 1, end);
    Merge(Array, front, mid, end);
}

[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 list
  return list if list.size < 2

  pivot = list.size / 2

  # Merge
  lambda { |left, right|
    final = []
    until left.empty? or right.empty?
      final << if left.first < right.first; left.shift else right.shift end
    end
    final + left + right
  }.call merge(list[0...pivot]), merge(list[pivot..-1])
end

Java

遞歸版： 

static void merge_sort_recursive(int[] arr, int[] result, 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, result, start1, end1);
	merge_sort_recursive(arr, result, start2, end2);
	int k = start;
	while (start1 <= end1 && start2 <= end2)
		result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
	while (start1 <= end1)
		result[k++] = arr[start1++];
	while (start2 <= end2)
		result[k++] = arr[start2++];
	for (k = start; k <= end; k++)
		arr[k] = result[k];
}
public static void merge_sort(int[] arr) {
	int len = arr.length;
	int[] result = new int[len];
	merge_sort_recursive(arr, result, 0, len - 1);
}

迭代版： 

public static void merge_sort(int[] arr) {
	int[] orderedArr = new int[arr.length];
	for (int i = 2; i < arr.length * 2; i *= 2) {
		for (int j = 0; j < (arr.length + i - 1) / i; j++) {
			int left = i * j;
			int mid = left + i / 2 >= arr.length ? (arr.length - 1) : (left + i / 2);
			int right = i * (j + 1) - 1 >= arr.length ? (arr.length - 1) : (i * (j + 1) - 1);
			int start = left, l = left, m = mid;
			while (l < mid && m <= right) {
				if (arr[l] < arr[m]) {
					orderedArr[start++] = arr[l++];
				} else {
					orderedArr[start++] = arr[m++];
				}
			}
			while (l < mid)
				orderedArr[start++] = arr[l++];
			while (m <= right)
				orderedArr[start++] = arr[m++];
			System.arraycopy(orderedArr, left, arr, left, right - left + 1);
		}
	}
}

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] . ' ';
}

Python3

def mergeSort(nums):
    if len(nums) < 2:
        return nums
    mid = len(nums) // 2
    left = mergeSort(nums[:mid])
    right = mergeSort(nums[mid:])

    i = j = 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]: 
            result.append(left[i])
            i += 1
        else: 
            result.append(right[j])
            j += 1

    while i < len(left): 
        result.append(left[i]) 
        i += 1

    while j < len(right): 
        result.append(right[j]) 
        j += 1

    return result

if __name__ == "__main__":
    nums = [1, 4, 2, 3.6, -1, 0, 25, -34, 8, 9, 1, 0]
    print("original:", nums)
    print("Sorted:", mergeSort(nums))

Erlang

%% @doc 归并排序
g_sort([]) ->
    [];
g_sort([T]) ->
    [T];
g_sort(L) ->
    g_sort(L, length(L)).

g_sort([_, _ | _] = L, Length) ->
    SplitNum = trunc(Length / 2),
    {L1, L2} = lists:split(SplitNum, L),
    g_merge(g_sort(L1, SplitNum), g_sort(L2, Length - SplitNum));
g_sort(L, _Length) ->
    L.

%% 已经排好序的两个list合并
g_merge([], L2) ->
    L2;
g_merge(L1, []) ->
    L1;
g_merge([T1 | Rest1] = L1, [T2 | Rest2] = L2) ->
    if
        T1 =< T2 -> [T1 | g_merge(Rest1, L2)];
        true -> [T2 | g_merge(L1, Rest2)]
    end.

Javascript

递归法

function merge(left, right){
  var result = [];
  while(left.length > 0 && right.length > 0){
    if(left[0] < right[0]){
      result.push(left.shift());
    }else{
      result.push(right.shift());
    }
  }
  return result.concat(left, right);
}

function mergeSort(arr){
  if(arr.length <=1) return arr;
  var middle = Math.floor(arr.length / 2);
  var left = arr.slice(0, middle);
  var right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

迭代法

Go

package main

import (
	"fmt"
	"sort"
)

func MergeSort(list []int) []int {
	var length = len(list)
	if length < 2 {
		return list
	}
	var mid = length / 2
	return merge(MergeSort(list[:mid]), MergeSort(list[mid:]))
}

func merge(x, y []int) []int {
	var r []int = make([]int, len(x)+len(y))
	for i, j := 0, 0; ; {
		if i < len(x) && (j == len(y) || x[i] < y[j]) {
			r[i+j] = x[i]
			i++
		} else if j < len(y) {
			r[i+j] = y[j]
			j++
		} else {
			break
		}
	}
	return r
}

func main() {
	var list []int = []int{56, 48, 58, 94, 87, 4, 5, 61, 5, 8, 74, 9, 84, 15, 94, 9, 4, 31, 41, 68, 7, 4, 6, 94, 16, 9, 8, 4}
	fmt.Println(MergeSort(list))
	fmt.Println(list)

	sort.Ints(list)
	fmt.Println(list)
}

递归版 

package main

import (
	"fmt"
)

func merge(data []int) []int {
	sum := len(data)
	if sum <= 1 {
		return data
	}
	left := data[0 : sum/2]
	lSize := len(left)
	if lSize >= 2 {
		left = merge(left)
	}
	right := data[sum/2:]
	rSize := len(right)
	if rSize >= 2 {
		right = merge(right)
	}
	j := 0
	t := 0
	arr := make([]int, sum)
	fmt.Println(left, right, data)
	for i := 0; i < sum; i++ {
		if j < lSize && t < rSize {
			if left[j] <= right[t] {
				arr[i] = left[j]
				j++
			} else {
				arr[i] = right[t]
				t++
			}
		}  else if j >= lSize{
			arr[i] = right[t]
			t++
		}  else if t >= rSize{
			arr[i] = left[j]
			j++
		}
	}
	return arr
}

func main() {
	var aa = []int{1000, 2, 31, 34, 5, 9, 7, 4, 6, 89, 90, 99, 99, 99, 99, 99}

	var bb = merge(aa)
	fmt.Println(bb)
}

算法复杂度

比较操作的次数介于和。

赋值操作的次数是。归并算法的空间复杂度为：

参考文献

  1. ^ Cormen, Thomas H. （英语：Thomas H. Cormen）; Leiserson, Charles E. （英语：Charles E. Leiserson）; Rivest, Ronald L.; Stein, Clifford. Section 2.3: Designing algorithms. Introduction to Algorithms 3rd. MIT Press and McGraw-Hill. 2009: 29–34 [1990]. ISBN 0-262-03384-4. .

外部連結
Index: pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve
Prefix: a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9

Portal di Ensiklopedia Dunia

Portal : Agama
Agama
Portal : Bahasa
Bahasa
Portal : Biografi
Biografi
Portal : Budaya
Budaya
Portal : Ekonomi
Ekonomi
Portal : Elektronika
Elektronika
Portal : Film
Film
Portal : Filsafat
Filsafat
Portal : Geografi
Geografi
Portal : Indonesia
Indonesia
Portal : Ilmu
Ilmu
Portal : Lingkungan
Lingkungan
Portal : Masyarakat
Masyarakat
Portal : Matematika
Matematika
Portal : Militer
Militer
Portal : Mitologi
Mitologi
Portal : Musik
Musik
Portal : Olahraga
Olahraga
Portal : Pendidikan
Pendidikan
Portal : Politik
Politik
Portal : Sastra
Sastra
Portal : Sejarah
Sejarah
Portal : Seni
Seni
Portal : Teknologi
Teknologi

Kembali kehalaman sebelumnya