合併排序
 | 此條目需要補充更多來源。 (2019年5月20日) |
| 合併排序 | |
|---|---|
 使用合併排序為一列數字進行排序的過程 | |
| 概況 | |
| 類別 | 排序演算法 |
| 資料結構 | 陣列 |
| 複雜度 | |
| 平均時間複雜度 | |
| 最壞時間複雜度 | |
| 最佳時間複雜度 | |
| 空間複雜度 | |
| 最佳解 | 有時是 |
| 相關變數的定義 | |
合併排序（英語：Merge sort，或mergesort），是建立在合併操作上的一種有效的排序演算法，效率為（大O符號）。1945年由約翰·馮·諾伊曼首次提出。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。
概述
[編輯]採用分治法:
- 分割：遞歸地把當前序列平均分割成兩半。
- 整合：在保持元素順序的同時將上一步得到的子序列整合到一起（合併）。
合併操作
[編輯]合併操作（merge），也叫合併演算法，指的是將兩個已經排序的序列合併成一個序列的操作。合併排序演算法依賴合併操作。
遞歸法（Top-down）
[編輯]- 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
- 設定兩個指標，最初位置分別為兩個已經排序序列的起始位置
- 比較兩個指標所指向的元素，選擇相對小的元素放入到合併空間，並移動指標到下一位置
- 重複步驟3直到某一指標到達序列尾
- 將另一序列剩下的所有元素直接複製到合併序列尾
迭代法（Bottom-up）
[編輯]原理如下（假設序列共有個元素）：
- 將序列每相鄰兩個數字進行合併操作，形成個序列，排序後每個序列包含兩/一個元素
- 若此時序列數不是1個則將上述序列再次合併，形成個序列，每個序列包含四/三個元素
- 重複步驟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);
}
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)
}
演算法複雜度
[編輯]比較操作的次數介於和。
賦值操作的次數是。合併演算法的空間複雜度為：
參考文獻
[編輯]- ^ Cormen, Thomas H. ; Leiserson, Charles E. ; 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..