算法学习笔记（5.0）-基于比较的高效排序算法-归并排序

##时间复杂度O(nlogn)

目录

##时间复杂度O(nlogn)

##递归实现归并排序

##原理

##图例

##代码实现

##非递归实现归并排序

##释

#代码实现

---

##递归实现归并排序

##原理

是一种基于分治策略的基础排序算法。

1.划分阶段：通过不断递归地将数组从中点处分开，将长数组的排序问题转化成段数组的排序问题。

2.合并阶段：当子数组的长度为1时终止划分，开始合并，持续不断地将左右两个较短的有序数组合并为一个较长的有序数组，直到结束。

##图例

##代码实现

1.向下递归，对半分割

2.递归返回条件：递归到最小，1个就是有序【控制的是范围，归并的是区间】

3.递归到最深处，最小时，就递归回去，开始分割按对半分割出的范围，将已有子序列合并，在tmp里面进行合并

4.再将tmp里形成的有序序列，拷贝回原数组【因下一次递归回去上一层的归并过程中，会将数据在tmp中进行归并，会将tmp中的数据覆盖，因此要及时，拷】

//python代码示例
def Merge(a, start, mid, end) :
    tmp = [] #创建一个临时列表，用来存储合并的值
    #两段起点的开始
    l = start
    r = mid + 1
    #当两段都没到达末尾，则继续循环，将其添加到tmp
    while l <= mid and r <= end :
        if a[l] <= a[r] :
            tmp.append(a[l])
            l += 1
        else :
            tmp.append(a[r])
            r += 1
    #此时肯定只剩下，单一的一个值，即将剩余元素塞入到tmp中
    tmp.extend(a[l:mid+1])
    tmp.extend(a[r:end+1])
    #将合并完成的元素，赋值到a原数组中
    for i in range(start,end+1):
        a[i] = tmp[i - start]
    print(start,end,tmp)
 
def MergeSort(a,start,end) :
    #利用递归来实现归并排序，将大的问题分解成小的子问题
    if start == end : #当递归到数组只有一个元素时，直接返回
        return
    mid = (start + end) // 2 #计算出mid，找到递归点
    MergeSort(a,start,mid) #左递归
    MergeSort(a,mid+1,end) #右递归
 
    Merge(a,start,mid,end)
    #左递归，左合并，右递归，右合并，类似于树的后序遍历
 
a = [7,3,2,6]
MergeSort(a,0,3)

//c++代码实现示例
#include<iostream>
#include<vector>
using namespace std;
//c++代码实现示例
void merge(vector<int> &a, int left, int mid, int right)
{
    int i = left ;
    int j = mid + 1 ;
    int k = left ;
    vector<int> tmp(right - mid + 1) ;
    while ( i <= mid && j <= right )
    {
        if ( a[i] <= a[j] )
        {
            tmp[k++] = a[i++] ;
        }
        else
        {
            tmp[k++] = a[j++] ;
        }
    }
    while ( i <= mid )
    {
        tmp[k++] = a[i++] ;
    }
    while ( j <= right )
    {
        tmp[k++] = a[j++] ;
    }
    for (int m = left ; m <= right ; m++)
    {
        a[m] = tmp[m - left] ;
    }
    cout << left << right << " " ;
    for (int n = 0 ; n < tmp.size() ; ++n)
    {
    	
    	cout << tmp[n] << " " ;
	}
}
 
 
void mergeSort(vector<int> &a, int left, int right)
{
    if (left >= right)
    {
        return ;
    }
    int mid = (left + right) / 2 ;
    mergeSort(a,left,mid) ;
    mergeSort(a,mid+1,right) ;
    merge(a,left,mid,right) ;
}
 
int main()
{
//	vector<int> arr = {1,2,3,4,5};
//	
	vector<int> arr;
    arr.push_back(7);
    arr.push_back(3);
    arr.push_back(2);
    arr.push_back(6);
//    arr.push_back(5);
	mergeSort(arr,0,3) ;
	
	return 0 ;
 
}

void _MergerSort(DataType* a ,DataType* tmp, int begin,int end)
{
	//递归返回条件，不正常的范围，或只剩下一个数 
	if (begin >= end)
	{
		return ;
	}
	int mid = (begin + end) / 2 ;
	//递归过程 
	_MergeSort(a,tmp,begin,mid) ;
	_MergeSort(a,tmp,mid+1,end) ;
	
	//合并过程 
	//归并到tmp数组中，再拷贝回去 
	int begin1 = begin ;
	int end1 = mid ;
	int begin2 = mid + 1 ;
	int end2 = end ;
	//指向tmp,=begin是 根据要进行比较插入的数组的位置 找到其对应在tmp中所对应的位置，则不会覆盖前面已经排好序的数据
	int index = begin ;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin++] ;
		}
		else
		{
			tmp[index++] = a[begin2++] ;
		}
	}
	//剩下还没有插入进去的 
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++] ;
	}
	
	//拷贝回去原数组a中
	memcpy(a+begin,tmp+begin,sizeof(DataType)*(end-begin+1)) ; 
}
 
void MergeSort(DataType* a, int n)
{
	DataType* tmp = (DataType*)malloc(sizeof(DataType)*n) ;
	if (tmp == NULL)
	{
		perror("malloc fail") ;
		return ;
	}
	_MergeSort(a,tmp,0,n-1) ;
	free(tmp) ;
}

对于链表，归并排序相较于其他排序算法具有显著优势，可以将链表排序任务的空间复杂度优化至 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/608403