Posted on 2012-11-25 21:23
hoshelly 阅读(3741)
评论(0) 编辑 收藏 引用 所属分类:
DS && Algorithm
归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
例如，有数列{6，202，100，301，38，8，1}
1. 刚开始的分组如下：
i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 比较次数为3次
2. 第二次，两两分组合并
i=2 [ 6 100 202 301 ] [ 1 8 38 ] 比较次数为4
3. 第三次，继续合并
i=3 [ 1 6 8 38 100 202 301 ] 比较次数为4
总计的比较次数为11次
归并排序具体工作原理如下（假设序列共有n个元素）：
1. 将序列每相邻两个数字进行归并操作，形成floor(n / 2)个序列，排序后每个序列包含两个元素
2. 将上述序列再次归并，形成floor(n / 4)个序列，每个序列包含四个元素
3. 重复步骤2，直到所有元素排序完毕
归并操作的过程如下：
1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾
自底向上归并，如图所示：
递归实现代码：
#include <iostream>
using namespace std;
void merge(int*arr, int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
int* L = new int[n1];
int* R = new int[n2];
for(int i = 0; i < n1; i++)
{
L[i] = arr[p + i];
}
for(int j = 0; j < n2; j++)
{
R[j] = arr[q + j + 1];
}
int i = 0;
int j = 0;
int k = p;
while((i < n1) && (j < n2))
{
if(L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
if (i < n1)
{
for(; i < n1; i++, k++)
{
arr[k] = L[i];
}
}
if (j < n2)
{
for(; j < n2; j++, k++)
{
arr[k] = R[j];
}
}
}
void mergesort(int* arr, int p, int r)
{
int q = 0;
if(p < r)
{
q = (p + r) / 2;
mergesort(arr, p, q);
mergesort(arr, q + 1, r);
merge(arr, p, q, r);
}
}
int main()
{
int a[] = {5, 2, 4, 7, 1, 3, 2, 6};
mergesort(a, 0, 7);
for(int i = 0; i < 8; i++)
{
cout << a[i] << " ";
}
cout << endl;
return 0;
}
非递归代码实现：
/**
* merge_sort: 非递归实现 --迭代
* 非递归思想: 将数组中的相邻元素两两配对。用merge函数将他们排序，
* 构成n/2组长度为2的排序好的子数组段，然后再将他们排序成长度为4的子数组段，
* 如此继续下去，直至整个数组排好序。
**/ #include <stdio.h>
#include <stdlib.h>
// merge_sort(): 非递归实现-自底向上
// 将原数组划分为left[min
max] 和 right[minmax]两部分
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)
// i为步长，1,2,4,8……
{
for (left_min = 0; left_min < length - i; left_min = right_max)
{
right_min = left_max = left_min + i;
//right_min取left_max的值，以下要用到left_max的值才不会改变left_max原先值
right_max = left_max + i;
if (right_max > length)
//如果right_max超出了数组长度，则right_max等于数组长度
right_max = length;
next = 0;
while (left_min < left_max && right_min < right_max)
//tmp[next]存储子数组中的最小值
tmp[next++] = list[left_min] > list[right_min] ? list[right_min++] : list[left_min++];
while (left_min < left_max)
//如果left_min小于left_max，则将最小值原封不动地赋给list[--right_min]，right_min 要先减1
list[--right_min] = list[--left_max];
while (next > 0)
//将tmp[next]存储的最小值放入list[--right_min]中
list[--right_min] = tmp[--next];
}
if(i == 1)
//打印第一次归并后的数字排列
{
for(
int j=0;j<length;j++)
printf("%d ",list[j]);
printf("\n");
}
}
free(tmp);
}
int main()
{
int a[1000],t,i;
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d",&a[i]);
}
merge_sort(a, t);
// print array
for (i = 0; i < t; i++)
printf("%d ", a[i]);
return 0;
}