合併排序法(Merge Sort)

文章已搬家，請點擊前往👈

REDIRECT_MODE = 1;

簡介

合併排序法(或稱歸併排序法)，是 排序演算法 的一種，使用 Divide and Conquer 的演算法來實作。排序時需要額外的空間來處理，過程依照以下步驟進行：

將陣列分割直到只有一個元素。 開始兩兩合併，每次合併同時進行排序，合併出排序過的陣列。 重複2的動作直接全部合併完成。

流程範例如圖所示：

實作又可分為 Top-down 和 Bottom-up ，依據原始的步驟會先將陣量分割直到剩一個元素(Top-down)，然而也可以一開始就直接切割成單一元素開始合併(Bottom-up)。

分析

最佳時間複雜度：O(nlog n)

平均時間複雜度：O(nlog n)

最差時間複雜度：O(nlog n)

空間複雜度：O(n)

Stable sort：是

虛擬碼

以下以較高階的想法寫出虛擬碼，實作上效能要好必須還要進一步修改：

Top-down

function sort(list) if list.length == 1 return list end if left = 取出從 list[0] 到 list[list.length / 2 - 1] right = 取出從 list[list.length / 2] 到 list[list.length - 1] return merge(sort(left), sort(right)) end function

function merge(left, right) var result = [] while left.length > 0 && right.length > 0 if right[0]

Bottom-up

function sort(list) // count為每個已排序的子陣列長度，每次合併後每個已排序的片段長度都會加倍，故增量為乘2 for count = 1;count < list.length;count *= 2 var work = [] // 每次取兩個片段來合併，故增量為兩個片段長度 for leftStart = 0;leftStart

語法

C#

Top-down物件導向的寫法

using System; using System.Collections.Generic; using System.Linq; using System.Text;

namespace MergeSort { // Top-down oo style class ObjectOriented { public static void Sort(int[] array) { Sort(array.ToList()).ToArray().CopyTo(array, 0); }

private static List Sort(List list) { if (list.Count < 2) return list;

List left = list.GetRange(0, list.Count / 2); List right = list.GetRange(list.Count / 2, list.Count - list.Count / 2); return Merge(Sort(left), Sort(right)); }

private static List Merge(List left, List right) { List result = new List (left.Count + right.Count); while (left.Count > 0 && right.Count > 0) result.Add(right.First() < left.First() ? Pop(right) : Pop(left)); result.AddRange(left); result.AddRange(right); return result; }

private static int Pop(List list) { int i = list.First(); list.RemoveAt(0); return i; } } }

Top-down修改版

using System; using System.Collections.Generic; using System.Linq; using System.Text;

namespace MergeSort { class TopDown { public static void Sort(int[] array) { int[] workArray = new int[array.Length]; Sort(array, workArray, 0, array.Length); }

private static void Sort(int[] array, int[] workArray, int start, int count) { if (count < 2) return;

Sort(array, workArray, start, count / 2); Sort(array, workArray, start + count / 2, count - count / 2); Merge(array, workArray, start, count / 2, start + count / 2, count - count / 2); }

private static void Merge(int[] array, int[] workArray, int leftStart, int leftCount, int rightStart, int rightCount) { int i = leftStart, j = rightStart, leftBound = leftStart + leftCount, rightBound = rightStart + rightCount, index = leftStart; while (i < leftBound || j < rightBound) { if (i < leftBound && j < rightBound) { if (array[j] < array[i]) workArray[index] = array[j++]; else workArray[index] = array[i++]; } else if (i

Bottom-up

using System; using System.Collections.Generic; using System.Linq; using System.Text;

namespace MergeSort { class BottomUp { public static void Sort(int[] array) { int[] workArray = new int[array.Length];

for (int count = 1; count array.Length - leftStart) break; Merge(array, workArray, leftStart, count, leftStart + count, Math.Min(count, array.Length - leftStart - count)); } }

private static void Merge(int[] array, int[] workArray, int leftStart, int leftCount, int rightStart, int rightCount) { int i = leftStart, j = rightStart, leftBound = leftStart + leftCount, rightBound = rightStart + rightCount, index = leftStart; while (i < leftBound || j < rightBound) { if (i < leftBound && j < rightBound) { if (array[j] < array[i]) workArray[index] = array[j++]; else workArray[index] = array[i++]; } else if (i

Java

Top-down

public class TopDown { public static void Sort(int[] array) { int[] workArray = new int[array.length]; Sort(array, workArray, 0, array.length); } private static void Sort(int[] array, int[] workArray, int start, int count) { if (count < 2) return; Sort(array, workArray, start, count / 2); Sort(array, workArray, start + count / 2, count - count / 2); Merge(array, workArray, start, count / 2, start + count / 2, count - count / 2); } private static void Merge(int[] array, int[] workArray, int leftStart, int leftCount, int rightStart, int rightCount) { int i = leftStart, j = rightStart, leftBound = leftStart + leftCount, rightBound = rightStart + rightCount, index = leftStart; while (i < leftBound || j < rightBound) { if (i < leftBound && j < rightBound) { if (array[j]

Bottom-up

public class BottomUp { public static void Sort(int[] array) { int[] workArray = new int[array.length];

for (int count = 1; count array.length - leftStart) break; Merge(array, workArray, leftStart, count, leftStart + count, Math.min(count, array.length - leftStart - count)); } }

private static void Merge(int[] array, int[] workArray, int leftStart, int leftCount, int rightStart, int rightCount) { int i = leftStart, j = rightStart, leftBound = leftStart + leftCount, rightBound = rightStart + rightCount, index = leftStart; while (i < leftBound || j < rightBound) { if (i < leftBound && j < rightBound) { if (array[j] < array[i]) workArray[index] = array[j++]; else workArray[index] = array[i++]; } else if (i

C++

Top-down

TopDown.h

#ifndef TOPDOWN_H #define TOPDOWN_H

class TopDown { public: static void Sort(int* array, int length); protected: private: static void Sort(int* array, int* workArray, int length, int start, int count); static void Merge(int* array, int* workArray, int length, int leftStart, int leftCount, int rightStart, int rightCount); };

#endif // TOPDOWN_H

TopDown.cpp

#include "TopDown.h"

void TopDown::Sort(int* array, int length) { int* workArray = new int[length]; Sort(array, workArray, length, 0, length); }

void TopDown::Sort(int* array, int* workArray, int length, int start, int count) { if (count < 2) return;

TopDown::Sort(array, workArray, length, start, count / 2); TopDown::Sort(array, workArray, length, start + count / 2, count - count / 2); TopDown::Merge(array, workArray, length, start, count / 2, start + count / 2, count - count / 2); }

void TopDown::Merge(int* array, int* workArray, int length, int leftStart, int leftCount, int rightStart, int rightCount) { int i = leftStart, j = rightStart, leftBound = leftStart + leftCount, rightBound = rightStart + rightCount, index = leftStart; while (i < leftBound || j < rightBound) { if (i < leftBound && j < rightBound) { if (array[j]

Bottom-up

Bottom.h

#ifndef BOTTOMUP_H #define BOTTOMUP_H

class BottomUp { public: static void Sort(int* array, int length); protected: private: static void Merge(int* array, int* workArray, int length, int leftStart, int leftCount, int rightStart, int rightCount); };

#endif // BOTTOMUP_H

BottomUp.cpp

#include "BottomUp.h" #include using namespace std;

void BottomUp::Sort(int* array, int length) { int* workArray = new int[length];

for (int count = 1; count length - leftStart) break; Merge(array, workArray, length, leftStart, count, leftStart + count, min(count, length - leftStart - count)); } }

void BottomUp::Merge(int* array, int* workArray, int length, int leftStart, int leftCount, int rightStart, int rightCount) { int i = leftStart, j = rightStart, leftBound = leftStart + leftCount, rightBound = rightStart + rightCount, index = leftStart; while (i < leftBound || j < rightBound) { if (i < leftBound && j < rightBound) { if (array[j]

隨機產生100000筆資料實測

C# TopDown: 50ms ButtonUp: 40ms

Java TopDown: 30ms ButtonUp: 40ms

C++ TopDown: 50ms BottomUp: 40ms

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

-->

小殘的程式光廊

提供一些演算法、資料結構、程式題目的整理與說明，PHP和JavaScript的基本教學和一些程式相關問題與解法。

合併排序法(Merge Sort)

參觀人氣

熱門文章

文章分類

電腦程式 (10)

最新文章

最新留言

文章搜尋

文章精選