首页 > 数据算法> 详细内容
归并排序
日期:2020-03-16 

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

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

  • 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
  • 自下而上的迭代;

完整过程

用一张动图来展示整个归并排序的过程。图中,开始每个柱子的颜色都不同,代表所有数字被分解成了各自一组,红色的柱子代表归并后的数列。

基本思想

归并排序的主要思想是分治法。主要过程是:

  1. 将n个元素从中间切开,分成两部分。(左边可能比右边多1个数)
  2. 将步骤1分成的两部分,再分别进行递归分解。直到所有部分的元素个数都为1。
  3. 从最底层开始逐步合并两个排好序的数列。


思考

考虑一个问题,如何将两个有序数列合并成一个有序数列?

很简单,由于两个数列都已经有序,我们只需从两个数列的低位轮番拿出各自最小的数来PK就就行了,输的一方为小值,将这个值放入临时数列,然后输的一方继续拿出一个值来PK,直至有一方没有元素后,将另一方的所有元素依次接在临时数列后面即可。此时,临时数列为两个数列的有序合并。归并排序中的归并就是利用这种思想。对应的代码如下:

/*归并排序*/
#include <stdio.h>
#include <stdlib.h>
 void mergeAdd(int arr[], int left, int mid, int right, int *temp){//实现“治”
int i = left;
int j = mid + 1;
int k = left;//临时下标
while (i <= mid&&j <= right){
if (arr[i] < arr[j]){
temp[k++] = arr[i++];
}
else{
temp[k++] = arr[j++];
}
}
while (i <= mid){
temp[k++] = arr[i++];
}
while (j <= right){
temp[k++] = arr[j++];
}
//把temp中的内容拷给arr数组中
//进行归并的时候,处理的区间是arr[left,right),对应的会把
//这部分区间的数组填到tmp[left,right)区间上
memcpy(arr + left, temp + left, sizeof(int)*(right - left+1));
}
void mergeSort(int arr[],int left,int right,int *temp){//实现“分”
int mid = 0;
if (left < right){
mid = left + (right - left) / 2;
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
mergeAdd(arr, left, mid, right, temp);
}

}
int main(){
int arr[] = { 8,4,5,7,1,3,6,2},i;
int len = sizeof(arr)/sizeof(arr[0]);
int *temp = (int*)malloc(sizeof(int)*len);
mergeSort(arr, 0, len - 1, temp);
free(temp);
for (i = 0; i < len; i++){
printf("%d ", arr[i]);
}

}


递归归并排序性质

时间复杂度:O(NlogN)

空间复杂度:O(N)

稳定性:稳定排序

非递归实现归并排序

void mergeAdd1(int arr[], int left, int mid, int right, int *temp){
int i = left;
int j = mid + 1;
int k = left;//临时下标
while (i <= mid&&j <= right){
if (arr[i] < arr[j]){
temp[k++] = arr[i++];
}
else{
temp[k++] = arr[j++];
}
}
while (i <= mid){
temp[k++] = arr[i++];
}
while (j <= right){
temp[k++] = arr[j++];
}
//把temp中的内容拷给arr数组中
//进行归并的时候,处理的区间是arr[left,right),对应的会把
//这部分区间的数组填到tmp[left,right)区间上
memcpy(arr + left, temp + left, sizeof(int)*(right - left + 1));
}
void mergeSort2(int arr[], int len,int* temp){
if (len <= 1){
return;
}
//定义一个步长gap,初始值为1,相当于每次只合并两个长度为1的元素
int gap = 1;
for (; gap <= len; gap *= 2){
int i = 0;
for (; i <= len; i += 2 * gap){
int beg = i;
int mid = (gap - 1) + i;
if (mid >= len){
mid = len;
}
int end = mid + gap;
if (end >= len){
end = len;
}
mergeAdd1(arr, beg, mid, end, temp);
}
}
}




int main(){
int arr[] = { 8,4,5,7,1,3,6,2},i;
int len = sizeof(arr)/sizeof(arr[0]);
int *temp = (int*)malloc(sizeof(int)*len);
mergeSort2(arr,len-1,temp);
free(temp);
for (i = 0; i < len; i++){
printf("%d ", arr[i]);
}

}