归并排序

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

归并排序(Merge sort,台灣譯作:合併排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

归并操作[编辑]

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

算法描述[编辑]

归并操作的过程如下:

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

示例代碼[编辑]

C语言[编辑]

/*=============================================================================
#
#     FileName: merge_sort_in_c.c
#         Desc: 归并排序
#
#       Author: gavinyao
#        Email: gavinyao_tencent.com
#
#      Created: 2013-12-25 23:55:02
#      Version: 0.0.1
#      History:
#               0.0.1 | gavinyao | 2013-12-25 23:55:02 | initialization
#
=============================================================================*/
#include <stdio.h>
#include <stdlib.h> // rand sranddev
 
#define DEBUG 1
#define SORT_NUM 10
 
void print_array(int *list, int len);
void merge_array(int *list1, int list1_size, int *list2, int list2_size);
 
/**
 * @brief 归并排序
 *
 * @param *list 要排序的数组
 * @param n 数组中的元素数量
 */
void merge_sort(int *list, int list_size)
{
    if (list_size > 1)
    {
        // 把数组平均分成两个部分
        int *list1 = list;
        int list1_size = list_size / 2;
        int *list2 = list + list_size / 2;
        int list2_size = list_size - list1_size;
        // 分别归并排序
        merge_sort(list1, list1_size);
        merge_sort(list2, list2_size);
 
        // 归并
        merge_array(list1, list1_size, list2, list2_size);
    }
}
 
/**
 * @brief 归并两个有序数组
 *
 * @param list1
 * @param list1_size
 * @param list2
 * @param list2_size
 */
void merge_array(int *list1, int list1_size, int *list2, int list2_size)
{
    int i, j, k;
    i = j = k = 0;
 
    // 声明临时数组用于存储归并结果
    int *list = malloc((list1_size + list2_size)*sizeof(int));
 
    // note: 只要有一个数组到达了尾部就要跳出
    // 也就是说只有两个都没有到达尾部的时候才执行这个循环
    while (i < list1_size && j < list2_size)
    {
        // 把较小的那个数据放到结果数组里, 同时移动指针
        list[k++] = list1[i] < list2[j] ? list1[i++] : list2[j++];
    }
 
    // 如果 list1 还有元素,把剩下的数据直接放到结果数组
    while (i < list1_size)
    {
        list[k++] = list1[i++];
    }
 
    // 如果 list2 还有元素,把剩下的数据直接放到结果数组
    while (j < list2_size)
    {
        list[k++] = list2[j++];
    }
 
    // 把结果数组 copy 到 list1 里
    for (int ii = 0; ii < (list1_size + list2_size); ++ii)
    {
        list1[ii] = list[ii];
    }
    free(list);
 
}
 
/**
 * @brief 打印数组
 *
 * @param list[]
 * @param len
 */
void print_array(int *list, int len)
{
    int i;
    for (i = 0; i < len; ++i)
    {
        // printf("%3d", *(list+i));
        printf("%3d", list[i]);
        if (i < len - 1)
            printf(" ");
    }
    printf("\n");
}
 
int main(void)
{
    int len = SORT_NUM;
    int list[len];
    for (int i = 0; i < len; ++i)
    {
        sranddev();
        list[i] = rand() % (SORT_NUM * SORT_NUM);
    }
 
    print_array(list, len);
    merge_sort(list, len);
    print_array(list, len);
 
    return 0;
}

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

C++語言[编辑]

//#只完成兩段之間歸併的功能#%
void Merge(int a[], int b[], int low, int mid, int high)
{
    int k = low;
    int begin1 = low;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = high;
    while(k <= high )
    {
        if(begin1 > end1)
            b[k++] = a[begin2++];
        else if(begin2 > end2)
            b[k++] = a[begin1++];
        else
	{
	    if(a[begin1] <= a[begin2])
		b[k++] = a[begin1++];
	    else
		b[k++] = a[begin2++];
	}
    }
 
}
 
void MergePass(int a[], int b[], int seg, int size)
{
    int seg_start_ind = 0;
    while(seg_start_ind <= size - 2 * seg) //#size - 2 * seg的意思是滿足可兩兩歸併的最低臨界值#%
    {
	Merge(a, b, seg_start_ind, seg_start_ind + seg - 1, seg_start_ind + seg * 2 - 1);
	seg_start_ind += 2 * seg;
    }
    //#如果一段是正好可歸併的數量而另一段則少於正好可歸併的數量#%
    if(seg_start_ind + seg < size)
	Merge(a, b, seg_start_ind, seg_start_ind + seg - 1, size - 1);
    else
	for(int j = seg_start_ind; j < size; j++) //#如果只剩下一段或者更少的數量#%
	    b[j] = a[j];
}
 
void MergeSort(int a[], int size)
{
    int* temp = new int[size];
    int seg = 1;
    while(seg < size)
    {
	MergePass(a, temp, seg, size);
	seg += seg;
	MergePass(temp, a, seg, size);
	seg += seg;
    }
    delete [] temp;
}
 
int main()
{
    int a[] = {3, 5, 3, 6, 4, 7, 5, 7, 4};
    MergeSort(a, sizeof(a) / sizeof(*a));
    //#輸出#%
    for(int i = 0; i < sizeof(a) / sizeof(*a); i++)
	cout << a[i] << ' ';
    cout << endl;
 
    return 0;
}

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

Java[编辑]

public int[] Two_Way_Merge_Sort(int[] A, int[] B) {
	int[] C = new int[A.length + B.length];
	int k = 0;
	int i = 0;
	int j = 0;
	while(i < A.length && j < B.length) {
		if (A[i] < B[j])
			C[k++] = A[i++];
		else
			C[k++] = B[j++];
	}
	while (i < A.length) 
		C[k++] = A[i++];
	while (j < B.length) 
		C[k++] = B[j++];
	return C;
}
 
/**
 * one good implements. <br />
 *
 * 
 */
public class Sort {
 
        public static final int CUTOFF = 11;
 
        /**
	 * merge sort algorithm.
	 * 
	 * @param arr an array of Comparable item.
         * 1.here only use one temp array (think about it). <br />
         * 2.copy the element back after the sub merge operation. @see merge(T, T, int, int);
         * the above two points make it more efficient. <br />
	 */
	@SuppressWarnings("unchecked")
	public static <T extends Comparable<? super T>> void mergeSort( T[] arr ) {
                //you may use insertionSort instead when the arr.length is not that large.
		/*if ( arr.length < CUTOFF ) {
			insertionSort( arr );
			return;
		}*/
 
		T[] tmpArr = (T[]) new Comparable[arr.length];
 
		mergeSort(arr, tmpArr, 0, arr.length - 1);
	}
 
	/**
	 * internal method to make a recursive call to merge. <br />
	 * 
	 * @param arr an array of Comparable items. <br />
	 * @param tmpArr temp array to placed the merged result. <br />
	 * @param left left-most index of the subarray. <br />
	 * @param right right-most index of the subarray. <br />
	 */
	private static <T extends Comparable<? super T>> 
	void mergeSort( T[] arr, T[] tmpArr,
			int left, int right ) {
		//recursive way
		if ( left < right ) {
			int center = ( left + right ) / 2;
			mergeSort(arr, tmpArr, left, center);
			mergeSort(arr, tmpArr, center + 1, right);
			merge(arr, tmpArr, left, center + 1, right);
		}
 
		//loop instead, not working, do it youself.
                /*
                int n = 0, j;
		while ( true ) {
			int step = ( int ) Math.pow(2, ++n);
			int len = step / 2;
			int count = arr.length / step;
			int rpos;
 
			//previous pow(2, k) elements
			for ( j = 0; j < count; j++ ) {
				rpos = j + len;
				System.out.println(j+", "+rpos);
				merge( arr, tmpArr, j, rpos, rpos + len - 1);
			}
 
			//the rest elements
			//for () ;
 
			if ( step * 2 >= arr.length ) break; 
		}
                 */
	} 
 
	/**
	 * internal method to merge the sorted halves of a subarray. <br />
	 * 
	 * @param arr an array of Comparable items. <br />
	 * @param tmpArr temp array to placed the merged result. <br />
	 * @param leftPos left-most index of the subarray. <br />
	 * @param rightPos right start index of the subarray. <br />
	 * @param endPos right-most index of the subarray. <br />
	 */
	private static <T extends Comparable<? super T>> void merge( T[] arr, T[] tmpArr,
			int lPos, int rPos, int rEnd ) {
		int lEnd = rPos - 1;
		int tPos = lPos;
		int leftTmp = lPos;
 
		while ( lPos <= lEnd && rPos <= rEnd  ) {
			if ( arr[lPos].compareTo( arr[rPos] ) <= 0 )
				tmpArr[ tPos++ ] = arr[ lPos++ ];
			else 
				tmpArr[ tPos++ ] = arr[ rPos++ ];
		}
 
		//copy the rest element of the left half subarray.
		while ( lPos <= lEnd ) 
			tmpArr[ tPos++ ] = arr[ lPos++ ];
		//copy the rest elements of the right half subarray. (only one loop will be execute)
		while ( rPos <= rEnd ) 
			tmpArr[ tPos++ ] = arr[ rPos++ ];
 
		//copy the tmpArr back cause we need to change the arr array items.
		for ( ; rEnd >= leftTmp; rEnd-- )
			arr[rEnd] = tmpArr[rEnd];
	}
}

Java Another[编辑]

public static int[] mergeSort(int[] arr){//归并排序 --递归
	if(arr.length==1){
		return arr;
	}
	int half = arr.length/2;
	int[] arr1 = new int[half];
	int[] arr2 = new int[arr.length-half];
	System.arraycopy(arr, 0, arr1, 0, arr1.length);
	System.arraycopy(arr, half, arr2, 0, arr2.length);
	arr1 = mergeSort(arr1);
	arr2 = mergeSort(arr2);
	return mergeSortSub(arr1,arr2);
}
 
private static int[] mergeSortSub(int[] arr1,int[] arr2){//归并排序子程序
	int[] result = new int[arr1.length+arr2.length];
	int i = 0;
	int j = 0;
	int k = 0;
	while(true){
		if(arr1[i] < arr2[j]){
			result[k] = arr1[i];
			if(++i>arr1.length-1){
				break;
			}
		}else{
			result[k] = arr2[j];
			if(++j>arr2.length-1){
				break;
			}
		}
		k++;
	}
	for(;i<arr1.length;i++){
		result[++k] = arr1[i];
	}
	for(;j<arr2.length;j++){
		result[++k] = arr2[j];
	}
	return result;
}

PHP[编辑]

$lista = array(3,8,4);
$listb = array(5,6,2);
 
print_r(mergeSort($lista, $listb));
 
function mergeSort($la,$lb) {
    //sort two sub-lists
    sort($la);
    sort($lb);
 
    $final = array();
    //keep looping while the two lists both have elements
    while($la && $lb){
        //compare the first two values,choose the smaller one and insert to 'final'
        if($la[0]<=$lb[0]){
            $final[] = array_shift($la);
        }else{
            $final[] = array_shift($lb);
        }
    }
 
    return array_merge($final,$la,$lb);
}
 
#######output#########
#Array ( [0] => 2 [1] => 3 [2] => 4 [3] => 5 [4] => 6 [5] => 8 )

Python[编辑]

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
 
    def merge(left, right):
        merged = []
        while left and right:
            merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
        while left:
            merged.append(left.pop(0))
        while right:
            merged.append(right.pop(0))
        return 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 H1<H2 ->  [H1] ++ merge(T1, L2);
	   true	 ->  [H2] ++ merge(L1, T2)
	end.

归并排序[编辑]

归并排序具体工作原理如下(假设序列共有n个元素):

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

示例代码[编辑]

示例代码为C语言,输入参数中,需要排序的数组为array[],起始索引为first,终止索引为last。调用完成后,array[]中从first到last处于升序排列。

void merge_sort(int array[], unsigned int first, unsigned int last)
{
	int mid = 0;
	if(first<last)
	{
		/*mid = (first+last)/2;*/ /*注意防止溢出*/
                /*mid = first/2 + last/2;*/
                /*mid = ((first & last) + (first ^ last) >> 1);*/
                mid = ((first & last) + ((first ^ last) >> 1));    /*修正上一句优先级错误*/
		merge_sort(array, first, mid);
		merge_sort(array, mid+1,last);
		merge(array,first,mid,last);
	}
}

如果不使用遞歸,而是迭代,則C代碼為:

void merge_sort(int *list, int length){
	int i, left_min, left_max, right_min, right_max, next;
	int *tmp = (int*)malloc(sizeof(int) * length);
	if (tmp == NULL){
		fputs("Error: out of memory\n", stderr);
		abort();
	}
	for (i = 1; i < length; i *= 2)
		for (left_min = 0; left_min < length - i; left_min = right_max){ 
			right_min = left_max = left_min + i;
			right_max = left_max + i;
			if (right_max > length)
				right_max = length;
			next = 0;
			while (left_min < left_max && right_min < right_max)
				tmp[next++] = list[left_min] > list[right_min] ? list[right_min++] : list[left_min++];
			while (left_min < left_max)
				list[--right_min] = list[--left_max];
			while (next > 0)
				list[--right_min] = tmp[--next];
		}
	free(tmp);
}

相应遞歸的Python语言的例子:

def mergesort(List):
    mid=int(len(List)/2)
    if len(List)<=1:return List
    return merge(mergesort(List[:mid]),mergesort(List[mid:]))

如果不使用递归,而是迭代,则python代码为:

def iter_mergesort(List):
    """mergesort的非递归版本,from DPV's <<Algorithms>> 
       http://www.cs.berkeley.edu/~vazirani/algorithms.html
    """
    Q=[]
    for i in List:Q.append([i])
    while len(Q) >1 : Q.append(merge(Q.pop(0),Q.pop(0)))
    return Q.pop()

相应的Ruby语言的例子,通过调用归并操作的merge方法,共同完成完整的归并排序功能。

def mergeSort(array)
	return array if array.size < 2
	left = array.first(array.size/2)
	right = array.last(array.size - array.size/2)
	merge(mergeSort(left), mergeSort(right))
end

相应的Javascript语言的例子,通过调用归并操作merge方法:

Array.prototype.mergeSort=function(array){
                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));
                }//end of the merge
 
                if (this.length < 2) {
                        return this;
                }
                var _left=this.slice(0,parseInt(this.length/2));
                var _right=this.slice(parseInt(this.length/2));
                return merge(_left.mergeSort(),_right.mergeSort());
    }

用法如下: a=[7,7,11,19,13,14,333,134,256,2,3] a.mergeSort() 通过alert(a.mergeSort())可查看排序结果。

算法复杂度[编辑]

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

外部連結[编辑]