【数据结构】归并排序

心已赠人 2023-02-26 04:21 5阅读 0赞

**1 基本思想**  
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。  
**2 算法步骤**  
**2.1 递归版归并排序**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]  
先对区间进行均分，均分成左右两半侧，递归排左半侧，递归排右半侧，将左右两半侧归并起来。  
**归并是指将两个有序区间合并成一个有序区间。**  
**2.2 循环版归并排序**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 1]  
类似于将平衡二叉树倒置，每层设置gap将数据划分好（gap=1,2,4…），然后进行合并排序。假如有10个数据，当gap=2时，会剩下一组（两个）数据无法匹配，这时无需任何操作，往下照搬就行了。  
**3 代码实现**  
**递归版归并排序**

//两个数组合并成一个有序数组
    void MergeData(int array[], int left, int mid, int right, int temp[])
    {
        
    	int index1 = left, index2 = mid, index = left;
    	while (index1 < mid&&index2 < right)
    	{
        
    		if (array[index1] <= array[index2])
    			temp[index++] = array[index1++];
    		else
    			temp[index++] = array[index2++];
    	}
    	//[left,mid)区间中的数据还没有搬移完
    	while (index1 < mid)
    	{
        
    		temp[index++] = array[index1++];
    	}
    	//[mid,right)区间中的数据还没有搬移完
    	while (index2 < right)
    	{
        
    		temp[index++] = array[index2++];
    	}
    }
    //设置_MergeSort函数是因为往后调用MergeSort函数时可减少参数的输入，方便使用者
    void _MergeSort(int array[], int left, int right, int temp[])
    {
        
    	if (right - left>1)
    	{
        
    		int mid = left + ((right - left) >> 1);
    		//[left,mid)
    		_MergeSort(array, left, mid, temp);
    		//[mid,right)
    		_MergeSort(array, mid, right, temp);
    		//将[left,mid)和[mid,right)有序区间进行归并
    		MergeData(array, left, mid, right, temp);
    		//归并好之后，转移到array中
    		memcpy(array + left, temp + left, (right - left)*sizeof(array[left]));
    	}
    }
    void MergeSort(int array[], int size)
    {
        
    	int* temp = (int*)malloc(size*sizeof(array[0]));
    	if (NULL == temp)
    		return;
    	_MergeSort(array, 0, size, temp);
    	free(temp);
    }

**循环版归并排序**

void MergeData(int array[], int left, int mid, int right, int temp[])
    {
        
    	int index1 = left, index2 = mid, index = left;
    	while (index1 < mid&&index2 < right)
    	{
        
    		if (array[index1] <= array[index2])
    			temp[index++] = array[index1++];
    		else
    			temp[index++] = array[index2++];
    	}
    	//[left,mid)区间中的数据还没有搬移完
    	while (index1 < mid)
    	{
        
    		temp[index++] = array[index1++];
    	}
    	//[mid,right)区间中的数据还没有搬移完
    	while (index2 < right)
    	{
        
    		temp[index++] = array[index2++];
    	}
    }
    void MergeSortNor(int array[],int size)
    {
        
    	int gap = 1;
    	int* temp = (int*)malloc(size*array[0]);
    	if (NULL == temp)
    		return;
    	while (gap<size)
    	{
        
    		for (int i = 0; i < size;i+=2*gap)
    		{
        
    			int left = i;
    			int mid = left + gap;
    			int right = mid + gap;
    			//出现落单的数据，注意边界的设置，防止越界访问
    			if (mid>size)
    			{
        
    				mid = size;
    			}
    			//同上
    			if (right>size)
    			{
        
    				right = size;
    			}
    			//[left,mid)和[mid,right)每个分组中有gap个数据
    			MergeData(array, left, mid, right, temp);
    		}
    		memcpy(array, temp, size*sizeof(array[0]));
    		gap *= 2;
    	}
    	free(temp);
    }

**4 特性**

1.  归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2.  时间复杂度：O(N\*logN)
3.  空间复杂度：O(N)
4.  稳定性：稳定

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70]: /images/20230209/971c59bfbfe0439ebbf2ad9dab7d7b42.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fbGVpbGVp_size_16_color_FFFFFF_t_70 1]: /images/20230209/6df40562e8b347c788a17c683d102d81.png