综述
归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序.
若将两个有序表合并成一个有序表,称为2-路归并.
算法描述
把长度为n的输入序列分成两个长度为n/2的子序列;对这两个子序列分别采用归并排序;将两个排序好的子序列合并成一个最终的排序序列.
示意图
归并排序动态示意图
归并排序静态示意图
原理
归并排序采用分而治之的原理
1.将一个序列从中间位置分成两个序列;
2.在将这两个子序列按照第一步继续二分下去;
3.直到所有子序列的长度都为1,也就是不可以再二分截止.
4.最后将两两合并成一个有序序列即可.
性质
排序类别:非交换排序
是否是稳定排序:稳定
是否是原地排序:否
时间复杂度:O(n*log2^n)
空间复杂度:递归方式为O(n), 非递归方式为O(1)
归并排序:递归方式牺牲空间换取时间的算法
详细分析
分组
归并
详解
补充说明
对于归并排序有几点说明:
- 归并排序的时间复杂度是O(NLogN),空间复杂度是O(N).
- 辅助数组是一个共用的数组.如果在每个归并的过程中都申请一个临时数组会造成比较大的时间开销.
- 归并的过程需要将元素复制到辅助数组,再从辅助数组排序复制回原数组,会拖慢排序速度.
优化方式
1.和快速排序一样,对于小数组可以使用插入排序或者选择排序,避免递归调用.
2.在merge()调用之前,可以判断一下a[mid]是否小于等于a[mid+1].如果是的话那么就不用归并了,数组已经是有序的.原因很简单,既然两个子数组已经有序了,那么a[mid]是第一个子数组的最大值,a[mid+1]是第二个子数组的最小值.当a[mid]<=a[mid+1]时,数组整体有序.
3.为了节省将元素复制到辅助数组作用的时间,可以在递归调用的每个层次交换原始数组与辅助数组的角色.
4.在merge()方法中的归并过程需要判断i和j是否已经越界,即某半边已经用尽.可以用另一种方式,去掉检测是否某半边已经用尽的代码.具体步骤是将数组a[]的后半部分以降序的方式复制到aux[],然后从两端归并.对于数组{1,2,3}和{2,3,5},第一个子数组照常复制,第二个则从后往前复制,最终aux[]中的元素为{1,2,3,5,3,2}.这种方法的缺点是使得归并排序变为不稳定排序.
Python实现方式
def merge_sort1(lists):
if len(lists) <= 1:
return lists
num = len(lists) // 2
temp_left = lists[:num]
temp_right = lists[num:]
print('temp_left:', temp_left, '--', 'temp_right:', temp_right)
left = merge_sort1(temp_left)
right = merge_sort1(temp_right)
return merge1(left, right)
def merge1(left, right):
left_index, right_index = 0, 0
result = []
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
result += list(left[left_index:])
result += list(right[right_index:])
return result
dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = merge_sort1(dest)
print('最后的结果是:', result)
'''
temp_left: [5, 2, 7, 4] -- temp_right: [8, 1, 6, 3]
temp_left: [5, 2] -- temp_right: [7, 4]
temp_left: [5] -- temp_right: [2]
temp_left: [7] -- temp_right: [4]
temp_left: [8, 1] -- temp_right: [6, 3]
temp_left: [8] -- temp_right: [1]
temp_left: [6] -- temp_right: [3]
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''
"""
非递归版本
非递归版本不需要额外的空间.直接在原数组上进行切割合并
"""
def merge2(seq, low, mid, high):
left = seq[low: mid]
right = seq[mid: high]
left_index = right_index = 0
result = []
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
result += left[left_index:]
result += right[right_index:]
seq[low: high] = result
def merge_sort2(seq):
i = 1 # i是步长
while i < len(seq):
low = 0
while low < len(seq):
mid = low + i # mid前后均为有序
high = min(low + 2 * i, len(seq))
if mid < high:
merge2(seq, low, mid, high)
low += 2 * i
i *= 2
dest = [5, 2, 7, 4, 8, 1, 6, 3]
result = merge_sort2(dest)
print('最后的结果是:', dest)
'''
最后的结果是: [0, 1, 2, 3, 4, 5, 6, 7, 8]
'''
C语言实现
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
//分组归并
void _Merge(int *a, int begin1, int end1, int begin2, int end2, int *tmp)
{
int index = begin1;
int i = begin1, j = begin2;
//注意:当划分的区间足够小时,begin1==end1,begin2==end2
while (i <= end1&&j <= end2){
if (a[i]<=a[j])
tmp[index++] = a[i++];
else
tmp[index++] = a[j++];
}
//将左边元素填充到tmp中
while (i <= end1)
tmp[index++] = a[i++];
//将右边元素填充的tmp中
while (j <= end2)
tmp[index++] = a[j++];
//将tmp中的数据拷贝到原数组对应的序列区间
//注意:end2-begin1+1
memcpy(a + begin1, tmp + begin1, sizeof(int)*(end2 - begin1 + 1));
}
//归并排序
void MergeSort(int *a, int left, int right, int *tmp)
{
if (left >= right)
return;
assert(a);
//mid将数组二分
int mid = left + ((right - left) >> 1);
//左边归并排序,使得左子序列有序
MergeSort(a, left, mid, tmp);
//右边归并排序,使得右子序列有序
MergeSort(a, mid + 1, right, tmp);
//将两个有序子数组合并
_Merge(a, left, mid, mid + 1, right, tmp);
}
//打印数组
void PrintArray(int *a, int len)
{
assert(a);
for (int i = 0; i < len; i++)
printf("%d ", a[i]);
printf("\n");
}
int main()
{
int a[] = { 10, 6, 7, 1, 3, 9, 4, 2 };
int *tmp = (int *)malloc(sizeof(int)*(sizeof(a) / sizeof(int)));
memset(tmp, -1, sizeof(a) / sizeof(int));
MergeSort(a, 0, sizeof(a) / sizeof(int)-1, tmp);
PrintArray(a, sizeof(a) / sizeof(int));
return 0;
}
// 递归方式
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
函数功能：合并
函数参数：
arr: 目标数组
start: 待合并段开始下标
mid: 待合并段中间下标
end: 待合并段结束下标
*/
void merge(int* arr, int start, int mid, int end)
{
int len_l, len_r; //左右待合并区间的长度
len_l = mid - start + 1;
len_r = end - mid;
int l[len_l], r[len_r]; //gcc, 两个临时数组，分别保存待合并的两个区间
//int l[100], r[100]; //vc
memcpy(l, arr + start, sizeof(int) * len_l);
memcpy(r, arr + mid + 1, sizeof(int) * len_r);
int i = 0, j = 0, k = start;
while(i < len_l && j < len_r)
{
arr[k++] = l[i] < r[j] ? l[i++] : r[j++];
}
while(i < len_l)
{
arr[k++] = l[i++];
}
}
/*
函数功能：归并排序
函数参数：
arr: 待排序的数组
start: 待排序数组开始下标
end: 待排序数组结束下标
*/
void merge_sort(int* arr, int start, int end)
{
if(start < end)
{
int mid = (start + end) / 2;
//归
merge_sort(arr, start, mid);
merge_sort(arr, mid + 1, end);
//并
merge(arr, start, mid, end);
}
}
int main()
{
int arr[11] = {-1, 2, 4, -12, 4, 0, 0, 12, 23, -4, 7000};
merge_sort(arr, 0, 10);
for(int i = 0; i < 11; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
// 非递归方式
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
函数功能：归并排序
函数参数：
arr: 待排序的数组
length: 该数组的长度
*/
void merge_sort(int* arr, int length)
{
int step = 1; //归并区间步长
int l[length], r[length]; //gcc, 两个临时数组，分别保存待归并的两个区间
//int l[100], r[100]; //vc
while(step < length)
{
int start = 0; //归并区间的开始下标
while(start < length - step)
{
//归
int len_l, len_r; //左右待归并区间的长度
len_l = len_r = step;
memcpy(l, arr + start, sizeof(int) * len_l);
if(start + 2 * step > length)
{
len_r = length - start - step;
}
memcpy(r, arr + start + step, sizeof(int) * len_r);
//并
int i = 0, j = 0, k = start;
while(i < len_l && j < len_r)
{
arr[k++] = l[i] < r[j] ? l[i++] : r[j++];
}
while(i < len_l)
{
arr[k++] = l[i++];
}
start += 2 * step;
}
step *= 2;
}
}
int main()
{
int arr[11] = {-1, 2, 4, -12, 4, 0, 0, 12, 23, -4, 7000};
merge_sort(arr, 11);
for(int i = 0; i < 11; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
网友评论