并归排序

妖狐艹你老母 2022-08-10 16:00 106阅读 0赞

/***************
    并归排序
    ***************/
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <time.h>
    #define LEN 5
    
    void arr_init(int num[], int len)
    {
    	int i;
    
    	srand(time(NULL));
    	for(i = 0; i < len; i++){
    		num[i] = rand()%50;
    	}
    
    }
    
    void arr_print(int num[], int len)
    {
    	int i;
    
    	for(i = 0; i < len; i++){
    		printf("%d ", num[i]);
    	}
    	printf("\n");
    
    }
    
    void merge(int num[], int start, int end)
    {
    	int mid, lenl, lenr, i, j, k;
    	int *pl, *pr;
    
    	mid = (start + end) / 2;
    	lenl = mid - start + 1;
    	lenr = end - mid;
    
    	pl = (int *)malloc(lenl * sizeof(int));
    	pr = (int *)malloc(lenr * sizeof(int));
    
    	if(!pl || !pr){
    		printf("malloc fail\n");
    		exit(1);
    	}
    
    	memcpy(pl, num + start, lenl * sizeof(int));
    	memcpy(pr, num + mid + 1, lenr *  sizeof(int));
    
    	i = j = 0, k = start;
    
    	while(i < lenl && j < lenr){
    		if(pl[i] < pr[j]){
    			num[k++] = pl[i++];
    		}else{
    			num[k++] = pr[j++];
    		}
    	}
    
    	if(i < lenl){
    		memcpy(num + k, pl + i, (lenl - i) * sizeof(int));
    	}
    	if(j < lenr){
    		memcpy(num + k, pr + i, (lenl - i) * sizeof(int));
    	}
    	free(pl);
    	free(pr);
    }
    void merge_sort(int num[], int start, int end)
    {
    	if(start >= end)
    		return;
    	int mid = (start + end ) / 2;
    	merge_sort(num, start, mid);
    	merge_sort(num, mid + 1, end);
    	merge(num, start, end);
    }
    
    int main(void)
    {
    	int num[LEN];
    	arr_init(num, LEN);
    	arr_print(num, LEN);
    	merge_sort(num, 0, LEN - 1);
    	arr_print(num, LEN);
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，106人围观）

还没有评论，来说两句吧...

相关阅读

相关归并排序(递归和非递归)

归并排序一.递归二.非递归 1.基础 2.改进一.递归 > 归并实际上就是把一个数组每次二分，分别排序每个子数组再将有

ゝ一纸荒年。/ 2024年03月24日 17:10/ 0 赞/ 40 阅读

相关用你最喜欢的语言写一个并归排序

我最喜欢的语言是中文，这是一个并归排序的例子：输入：\[ 8, 4, 5, 3, 7, 6, 1, 2 \]步骤1：\[ \[ 8, 4 \], \[ 5, 3 \], \[

快来打我*/ 2023年09月25日 16:48/ 0 赞/ 44 阅读

相关 Data Structure--排序--归并排序(递归/非递归)--计数排序(非比较排序)

排序归并排序(递归+非递归) 计数排序(非比较排序) 归并排序(递归+非递归) ![在这里插入图片描述][watermark_type_ZmFuZ3

àì夳堔傛蜴生んèń/ 2022年11月03日 11:19/ 0 赞/ 183 阅读

相关 c语言选择排序递归,数据结构：选择排序（递归）

Description 排序，顾名思义，是将若干个元素按其大小关系排出一个顺序。形式化描述如下：有n个元素a\[1\]，a\[2\]，…，a\[n\]，从小到大排序就是将它们

绝地灬酷狼/ 2022年10月15日 05:53/ 0 赞/ 204 阅读

相关快速排序递归与非递归

递归法快排的思想设当前需要排序的数组为int A\[bt...ed\] 分解：在A\[\]中任选一个记录作为基准（pivot

素颜马尾好姑娘i/ 2022年09月18日 01:59/ 0 赞/ 221 阅读

相关并归排序的实现和简单分析

//将两排列有序的字符串进行有序合并 include <stdio.h> include <stdlib.h> include <string.

妖狐艹你老母/ 2022年08月11日 00:43/ 0 赞/ 101 阅读

相关并归排序

/ 并归排序 / include <stdio.h> include <stdlib.h> include <string.h>

妖狐艹你老母/ 2022年08月10日 16:00/ 0 赞/ 107 阅读

相关快速排序（递归）

include <stdio.h> include <stdlib.h> define NUM_OF_ARRAY 100 void quick_

刺骨的言语ヽ痛彻心扉/ 2022年06月09日 01:20/ 0 赞/ 179 阅读

相关 php实现并归排序

废话不多说，上完整代码： <?php / Created by PhpStorm. User: KeenSting Dat

╰+哭是因爲堅強的太久メ/ 2022年06月04日 10:13/ 0 赞/ 124 阅读

相关归并排序（递归和非递归）

学习之后，自己练习手写一下排序算法，加深印象原理：假设初始序列含有n个记录，则可以看做是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的子序

水深无声/ 2022年05月28日 01:44/ 0 赞/ 248 阅读