簡介

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

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

流程範例如圖所示:

618px-Merge_sort_algorithm_diagram_svg     

實作又可分為Top-downBottom-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] < left[0]
			pop right 加到 result
		else
			pop left 加到 result
		end if
	end while
	left 剩下的加到 result
	right 剩下的加到 result
	return result
end function

Bottom-up

function sort(list)
	// count為每個已排序的子陣列長度,每次合併後每個已排序的片段長度都會加倍,故增量為乘2
	for count = 1;count < list.length;count *= 2
		var work = []
		// 每次取兩個片段來合併,故增量為兩個片段長度
		for leftStart = 0;leftStart < list.length;leftStart += count*2
			rightStart = min(leftStart + count, list.length - 1)
			left = 取出從 list[leftStart] 到 list[rightStart - 1]
			right = 取出從 list[rightStart] 到 list[min(rightStart + count - 1, list.length)]
			// merge 同Top-down
			merge(left, right) 加到 work
		end for
		list = work
	end for
	return list
end function

語法

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<int> Sort(List<int> list)
        {
            if (list.Count < 2)
                return list;

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

        private static List<int> Merge(List<int> left, List<int> right)
        {
            List<int> result = new List<int>(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<int> 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 < leftBound)
                    workArray[index] = array[i++];
                else
                    workArray[index] = array[j++];
                ++index;
            }
            for (i = leftStart; i < index; ++i)
                array[i] = workArray[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; count *= 2)
                for (int leftStart = 0; leftStart < array.Length; leftStart += 2 * count)
                {
                    if (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 < leftBound)
                    workArray[index] = array[i++];
                else
                    workArray[index] = array[j++];
                ++index;
            }
            for (i = leftStart; i < index; ++i)
                array[i] = workArray[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] < array[i]) 
	                workArray[index] = array[j++]; 
	            else
	                workArray[index] = array[i++]; 
	        } 
	        else if (i < leftBound) 
	            workArray[index] = array[i++]; 
	        else
	            workArray[index] = array[j++]; 
	        ++index; 
	    } 
	    for (i = leftStart; i < index; ++i) 
	        array[i] = workArray[i]; 
	}
}

Bottom-up

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

        for (int count = 1; count < array.length; count *= 2) 
            for (int leftStart = 0; leftStart < array.length; leftStart += 2 * count) 
            { 
                if (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 < leftBound) 
                workArray[index] = array[i++]; 
            else
                workArray[index] = array[j++]; 
            ++index; 
        } 
        for (i = leftStart; i < index; ++i) 
            array[i] = workArray[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] < array[i])
                workArray[index] = array[j++];
            else
                workArray[index] = array[i++];
        }
        else if (i < leftBound)
            workArray[index] = array[i++];
        else
            workArray[index] = array[j++];
        ++index;
    }
    for (i = leftStart; i < index; ++i)
        array[i] = workArray[i];
}

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 <algorithm>
using namespace std;

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

    for (int count = 1; count < length; count *= 2)
        for (int leftStart = 0; leftStart < length; leftStart += 2 * count)
        {
            if (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] < array[i])
                workArray[index] = array[j++];
            else
                workArray[index] = array[i++];
        }
        else if (i < leftBound)
            workArray[index] = array[i++];
        else
            workArray[index] = array[j++];
        ++index;
    }
    for (i = leftStart; i < index; ++i)
        array[i] = workArray[i];
}

隨機產生100000筆資料實測

C#
TopDown: 50ms
ButtonUp: 40ms

Java
TopDown: 30ms
ButtonUp: 40ms

C++
TopDown: 50ms
BottomUp: 40ms

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

文章標籤
創作者介紹

小殘的程式光廊

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()