归并排序

百科名片

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序

　　归并排序是建立在归并操作上的一种有效的算法。该算法是采用（Divide and Conquer）的一个非常典型的应用。

　　将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

归并操作

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

　　如　设有数列{6，202，100，301，38，8，1}

　　初始状态： [6] [202] [100] [301] [38] [8] [1] 比较次数

　　i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]　3

　　i=2 [ 6 100 202 301 ] [ 1 8 38 ]　4

　　i=3　[ 1 6 8 38 100 202 301 ] 4

　　总计：　11次

算法描述

　　归并操作的工作原理如下：

　　申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

　　设定两个指针，最初位置分别为两个已经排序序列的起始位置

　　比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

　　重复步骤3直到某一指针达到序列尾

　　将另一序列剩下的所有元素直接复制到合并序列尾

复杂度

　　时间O(nlogn)

　　空间O(n)

　　与快速排序类似。

与快速排序的比较

　　归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比优势的地方.

用途

　　1、排序（速度仅次于快速排序，但较稳定）

　　2、求数

示例代码

　　归并排序

　　　归并排序具体工作原理如下（假设序列共有n个元素）：

　　将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素

　　将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素

　　重复步骤2，直到所有元素排序完毕

　　示例代码

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

　　void MergeSort(int array[], int first, int last)

　　{

　　int mid = 0;

　　if(first

　　{

　　mid = (first+last)/2;

　　MergeSort(array, first, mid);

　　MergeSort(array, mid+1,last);

　　Merge(array,first,mid,last);

　　}

　　}

　　以下示例代码实现了归并操作。array[]是元素序列，其中从索引p开始到q位置，按照升序排列，同时，从(q+1)到r也已经按照升序排列，merge()函数将把这两个已经排序好的子序列合并成一个排序序列。结果放到array中。

　　/**

　　* 0 <= p <= q < r, subarray array[p..q] and array[q+1..r] are already sorted.

　　* the merge() function merges the two sub-arrays into one sorted array.

　　*/

　　void Merge(int array[], int p, int q, int r)

　　{

　　int i,k;

　　int begin1,end1,begin2,end2;

　　int* temp = (int*)malloc((r-p+1)*sizeof(int));

　　begin1= p;

　　end1 = q;

　　begin2 = q+1;

　　end2 = r;

　　k = 0;

　　while((begin1 <= end1)&&( begin2 <= end2))

　　{

　　if(array[begin1] < array[begin2])

　　{ temp[k] = array[begin1];

　　begin1++;

　　}

　　else

　　{

　　temp[k] = array[begin2];

　　begin2++;

　　}

　　k++;

　　}

　　while(begin1<=end1)

　　{

　　temp[k++] = array[begin1++];

　　}

　　while(begin2<=end2)

　　{

　　temp[k++] = array[begin2++];

　　}

　　for (i = 0; i < (r - p + 1); i++)

　　array[p+i] = temp[i];

　　free(temp);

　　}

　　非递归算法（C++）：

　　

　　#include

　　#include

　　#include

　　using namespace std;

　　/** 将a开头的长为length的数组和b开头长为right的数组 合并 n为数组长度，用于最后一组 */

　　void Merge(int* data, int a, int b, int length, int n){

　　int right;

　　if(b+length-1 >= n-1) right = n-b;

　　else right = length;

　　int* temp = new int[length+right];

　　int i = 0, j = 0;

　　while(i<=length-1&&j<=right-1){

　　if(data[a+i] <= data[b+j]){

　　temp[i+j] = data[a+i]; i++; }

　　else{ temp[i+j] = data[b+j]; j++; }

　　}

　　if(j == right){// a中还有元素，且全都比b中的大,a[i]还未使用

　　memcpy(data+a+i+j, data+a+i,(length-i)*sizeof(int));

　　}

　　memcpy(data+a, temp, (i+j)*sizeof(int) );

　　delete temp;

　　}

　　void MergeSort(int* data, int n){

　　int step = 1;

　　while(step < n){

　　for(int i = 0; i <= n-step-1; i += 2*step)

　　Merge(data, i, i+step, step, n);

　　// 将i和i+step这两个有序序列进行合并

　　// 序列长度为step

　　// 当i以后的长度小于或者等于step时，退出

　　step *= 2;

　　}

　　}

　　int main(){

　　int n;

　　cin >> n;

　　int *data = new int[n];

　　if(!data) exit(1);

　　int k = n;

　　while(k --){

　　cin >> data[n-k-1];

　　}

　　clock_t s = clock();

　　MergeSort(data, n);

　　clock_t e = clock();

　　k = n;

　　while(k --){

　　cout << data[n-k-1] << ' ';

　　}

　　cout << endl;

　　cout << "the algrothem used " << e-s << " miliseconds."

　　<< endl;

　　delete data;

　　return 0; }

 

from: