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

妖狐艹你老母 2022-08-11 00:43 125阅读 0赞

//将两排列有序的字符串进行有序合并
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    char *hb(char *dest, char *s1, char *s2)
    {
    	int i, j , k;
    	i = j = k = 0;
    	while( s1[i]  && s2[j] ){
    		if(s1[i] < s2[j]){
    			dest[k++] = s1[i++];
    		}else{
    			dest[k++] = s2[j++];
    		}
    	}
    
    	dest[k] = '\0';
    
    	if(s1[i] != '\0'){
    		strcat(dest, s1+i);
    	}
    	if(s2[j] != '\0'){
    		strcat(dest, s2+j);
    	}
    
    	return dest;
    }
    
    int main(void)
    {
    
    	char src1[] = "13579",  src2[] = "2468", *dest;
    
    	dest =(char *) malloc(strlen(src1) + strlen(src2) + 1);
    //	dest = hb(dest,src1, src2);
    
    	printf("%s\n", hb(dest, src1, src2));
    	return 0;
    
    }
    
    /*
    akaedu@akaedu-G41MT-D3:~/lin/lb$ ./a.out 
    123456789
    */
    
    
    
    
    <pre name="code" class="cpp">
    
    
    
    
    
    /***********************************/
    //归并排序函数和二分查找（折半查找）
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <time.h>
    #define N 10
    
    void init_num(int num[])
    {
    	int i;
    	srand(time(NULL));
    	for(i = 0; i < N; i++){
    		num[i] = rand()%50;
    	}
    
    }
    void print_num(int num[])
    {
    	int i;
    	for(i = 0; i < N; i++){
    		printf("%d ", num[i]);
    	}
    	printf("\n");
    }
    
    void merge(int num[], int start, int end)
    {
    //N[5] = { 1 , 2 , 3, 5, 8 }; 			mid: (0 + 4)/2 = 2   1,2,3  5,8
    //N[6] = { 1 , 2 , 3, 5, 8, 15 }; 		mid: (0 + 5)/2 = 2   1,2,3  5,8,15
    //lenl为截断的左边长度 lenr为右端长度
    //pl为　lenl开辟的空间的指针　 
    	int i, j, k, lenl, lenr;
    	int *pl, *pr;
    	int mid = (start + end)/2;
    	lenl = mid - start + 1; //lenl = mid + 1;
    	lenr = end - mid;
    
    	pl = (int *)malloc(lenl * sizeof(int));
    	pr = (int *)malloc(lenr * sizeof(int));
    
    //检查pl pr 开辟空间是否成功
    	if(!pl || !pr){
    		printf("malloc fali\n");
    		exit(1);
    	}
    
    //将mid左边的数据copy到pl所指向的空间　右边的数据copy到pr所指向的空间
    	memcpy(pl, num + start, lenl * sizeof(int));
    	memcpy(pr, num + mid + 1, lenr * sizeof(int));
    
    
    	i = j = 0, k = start;
    //	i = j = k = 0;
    //merge 是把左右两段已经有序的数列进行有序合并，
    //ｋ从start开始,比如mid的右边数组下标(3, 4)的值和左边数组下标(0,1,2)的值的进行比较合并的
    
    	while(i < lenl && j < lenr){
    		if(pl[i] < pr[j]){
    			num[k++] = pl[i++];
    		}else{
    			num[k++] = pr[j++];
    		}
    	}
    
    
    //判断mid的左右两个数组中，其中的一个已经比较完毕，另
    //一个数组里面的数肯定是大于比较完毕的数组中的值,所以直接copy即可
    	if(i < lenl){
    		memcpy(num + k, pl + i, (lenl - i) * sizeof(int));
    	}
    	//num要加k
    	if(j < lenr){
    		memcpy(num + k, pr + j, (lenr - j) * sizeof(int));
    	}
    
    //释放malloc
    	free(pl);
    	free(pr);
    
    }
    
    
    
    
    //折半查找，前提必须是一个有序的数列
    //N[5] = { 1 , 2 , 3, 5, 8 }; 			mid: (0 + 4)/2 = 2   1,2,3  5,8
    //N[6] = { 1 , 2 , 3, 5, 8, 15 }; 		mid: (0 + 5)/2 = 2   1,2,3  5,8,15
    
    int binary_search(int num[],int key) 
    {
    	int mid, start = 0, end = N - 1; //mid, start, end 为数组的下标
    	while(start <= end){
    		mid = (start + end) / 2;
    		if(num[mid] < key){
    			start = mid + 1;
    		}else if(num[mid] > key){
    			end = mid - 1;
    		}else
    //			return num[mid];
    			return mid;
    	}
    	return -1;
    }
    
    void merge_sort(int num[], int start, int end)
    {	//start = 0   end = N -1
    	int mid;
    	if(start >= end) //判断语句，返回值
    		return;
    	mid = (start + end)/2; 
    	merge_sort(num, start, mid);
    	merge_sort(num, mid + 1, end);
    	merge(num, start, end);
    }
    
    int main(void)
    {
    	int num[N];
    	int key, x;
    	init_num(num);
    	print_num(num);
    	merge_sort(num, 0, N - 1);
    	printf("after sort...\n");
    
    	print_num(num);
    	scanf("%d", &key);
    	x = binary_search(num, key);
    	if(x == -1){
    		printf("no find\n");
    	}
    	if(x != -1)
    		printf("%d is %dth element in array\n", key, x + 1);
    	return 0;
    }
    
    
    /*
    akaedu@akaedu-G41MT-D3:~/lin/20140827_exam$ ./6
    16 32 47 0 38 4 32 13 16 48 
    after sort...
    0 4 13 16 16 32 32 38 47 48 
    16
    16 is 5th element in array
    
    */

![20140811205445876][]

[20140811205445876]: /images/20220810/fc04614eaa704b509d9786da27d0a1af.png