合并排序

柔情只为你懂 2022-03-31 04:54 158阅读 0赞

### 什么是合并排序算法 ###

**合并排序是用分治策略实现对n个元素进行排序的算法，其基本思想是：将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好序的子集合合并成要求的集合。**

**思路：****对集合不断进行拆分，直至集合中只剩一个元素为止。再调用合并排序算法，将每一个子集合的元素进行排序，并将排序后的结果保存在临时数组中，再将临时数组赋值给初始数组即可。**

#include <stdio.h>
    #include <stdlib.h>
    #define size 7 
    void mergesort(int arr[],int left,int right);
    void merge(int arr[],int left,int middle,int right);
    int main(){
    	int arr[size];
    	printf("请输入数字:\n"); 
    	for(int i=0;i<size;i++){
    		scanf("%d",&arr[i]);
    	}
    	printf("排序前:\n");
    	for(int i=0;i<size;i++){
    		printf("%d\t",arr[i]);
    	}
    	mergesort(arr,0,size-1);     //执行排序算法 
    	printf("\n排序后:\n");
    	for(int i=0;i<size;i++){
    		printf("%d\t",arr[i]);
    	}
    	return 0;	
    }
    void mergesort(int arr[],int left,int right){
    	int middle = 0;     				//定义中间值 
    	if(left<right){
    		middle = (left+right)/2;    	//取左右值的中间值 
    		mergesort(arr,left,middle);	 	//递归调用 
    		mergesort(arr,middle+1,right);	//递归调用
    		merge(arr,left,middle,right);	//合并排序 
    	}
    }
    void merge(int arr[],int left,int middle,int right){
    	int k;	
    	int left_min = left;
    	int left_max = middle;
    	int right_min = middle+1;
    	int right_max = right; 
    	int *b = (int *)malloc((right-left+1)*sizeof(int));		//定义临时数组，并申请内存空间 
    	for(k=0;left_min<=left_max&&right_min<=right_max;k++){ 	 
    		if(arr[left_min]<arr[right_min]){ 					//如果数组左边的值比右边的小，就把值添加到b中，反之添加右边的值 
    			b[k] = arr[left_min++];
    		}else{
    			b[k] = arr[right_min++];
    		}
    	}
    	if(left_min<=left_max){            						//如果比较完，左边还有剩余，就把剩余的值复制到数组后边 
    		for(int i=left_min;i<=left_max;i++){
    			b[k] = arr[i];
    			k++;
    		}
    	}
    	if(right_min<=right_max){							 	//如果比较完，右边还有剩余，就把剩余的值复制到数组后边 
    		for(int i=right_min;i<=right_max;i++){
    			b[k] = arr[i];
    			k++;
    		}
    	}
    	for(int i=0;i<right-left+1;i++){					     
    		arr[left+i] = b[i];
    	}
    	free(b);
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70][]

**先对所要进行排序的序列进行分解，直到分为单个元素为止，然后将其进行两两合并。由于最终分解成单个元素，因此在合并的时候.将小数放在前面，大数放在后面，得到一个有序序列。接下来对两个相连的有序序列进行排序，先比较有序序列中的第一个元素，将较小的元素放入临时数组中，接着将较小元素所在数组的下一个元素与另一个数组中的较小元素比较，同样将较小元素放入临时数组中，依次进行，直到两个数组的所有元素都放入临时数组中，最后再将临时数组的元素放入原始数组中的对应位置**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70]: /images/20220331/cb27608bdf08451594d5f7d704018745.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1]: /images/20220331/b1bdf79b1b514c70bed24e1751a6659c.png