八大排序之归并排序

柔情只为你懂 2022-04-22 06:30 161阅读 0赞

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

我们可以这样简单的理解：将一个数组分为两个数组arr1 arr2，假如这两个数组有序，再将这两个数组归并为一个数组，并确保归并后的数组也有序。关键就是如何让arr1 arr2有序，我们可以对这两个数组分别采用归并算法。以此类推

int arr[10] = { 5, 2, 6, 8, 1, 9, 0, 3, 7, 4 };

步骤：

*  申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
 *  设定两个指针，最初位置分别为两个已经排序序列的起始位置
 *  比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
 *  重复上一步直到某一指针到达序列尾
 *  将另一序列剩下的所有元素直接复制到合并序列尾  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70]  
    代码如下：

void MergeSort(int arr[], int left, int mid, int right, int extra[])
    	{ 
    		int left_i = left;
    		int right_i = mid;
    		int extra_i = left;
    		//开始合并两个有序数组
    		while (left_i < mid && right_i < right)
    		{ 
    			if (arr[left_i] <= arr[right_i])
    			{ 
    				extra[extra_i++] = arr[left_i++];
    			}
    			else
    			{ 
    				extra[extra_i++] = arr[right_i++];
    			}
    		}
    		//将还有元素的数组的剩余元素放入extra中
    		while (left_i < mid)
    		{ 
    			extra[extra_i++] = arr[left_i++];
    		}
    		while (right_i < right)
    		{ 
    			extra[extra_i++] = arr[right_i++];
    		}
    	
    		for (int i = left; i < right; i++)
    		{ 
    			arr[i] = extra[i];
    		}
    	}
    	
    	void __MergeSort(int arr[], int left, int right, int extra[])
    	{ 
    		//分组的时候，最终小组只能有1个或0个元素就一定是有序的
    		if (left == right - 1)
    		{ 
    			return;
    		}
    		if (left >= right)
    		{ 
    			return;
    		}
    	
    		//mid是中间元素的下标，因为分为是根据中间元素下标开始分的
    		int mid = (left & right) + ((left ^ right) >> 1);
    		__MergeSort(arr, left, mid, extra);
    		__MergeSort(arr, mid, right, extra);
    		MergeSort(arr, left, mid, right, extra);
    	}
    	
    	void Merge(int arr[], int size)
    	{ 
    		//extra用于存放两个数组合并后的有序数组
    		int *extra = (int *)malloc(sizeof(int) * size);
    		__MergeSort(arr, 0, size, extra);
    		free(extra);
    	}

## 非递归写法 ##

void MergeLoop(int arr[], int size)
    { 
    	int *extra = (int *)malloc(sizeof(int) * size);
    	//i表示每个分组最多有几个元素，也表示一共循环了log(size)次
    	for (int i = 1; i < size; i *= 2) 
    	{ 
    		//j表示一个分组到下一个元素最多要跨越的元素个数
    		for (int j = 0; j < size; j += 2 * i)
    		{ 
    			int left = j;
    			int mid = i + j;
    			int right = mid + i;
    
    			if (mid >= size)
    			{ 
    				continue;
    			}
    			if (right > size)
    			{ 
    				right = size;
    			}
    			MergeSort(arr, left, mid, right, extra);
    		}
    	}
    	free(extra);
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70]: /images/20220422/002a5fc91c484bf29ca490e0f82f0610.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpeGlhb2Rlc2h1c2h1_size_16_color_FFFFFF_t_70 1]: /images/20220422/3e0fd78aa8754f0ea90580427bed7b74.png