二路归并排序

快来打我* 2023-02-17 11:18 15阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    
    typedef int DataType;
    
    //一次二路归并排序
    void Merge(DataType a[], int n, DataType swap[], int k)
    {
    	int m = 0, u1, l2, i, j, u2;
    	int l1 = 0;
    	while(l1+k<=n-1)
    	{
    		l2 = l1 + k;
    		u1 = l2 - 1;
    		u2 = (l2+k-1<= n-1)? l2+k-1:n-1;
    		for(i=l1, j=l2; i<=u1&&j<=u2;m++)
    		{
    			if(a[i]<=a[j])
    			{
    				swap[m] = a[i];
    				i++;
    			}
    			else
    			{
    				swap[m] = a[j];
    				j++;
    			}
    		}
    		while(i<=u1)
    		{
    			swap[m] = a[i];
    			m++;
    			i++;
    		}
    		while(j<=u2)
    		{
    			swap[m] = a[j];
    			m++;
    			j++;
    		}
    		l1 = u2 +1;
    	}
    	for(i=l1;i<n;i++,m++) swap[m] = a[i];
    }
    
    void MergeSort(DataType a[], int n)
    {
    	int i, k = 1;
    	DataType *swap;
    	swap = (DataType *)malloc(sizeof(DataType)*n);
    	while(k<n)
    	{
    		Merge(a,n,swap,k);
    		for(i=0;i<n;i++)
    		    a[i] = swap[i];
    		k = 2 * k;
    	}
    	free(swap);
    }
    
    
    int main()
    {
    	DataType a[]={72,73,71,23,94,16,5,68,64};
    	MergeSort(a, 9);
    	for(int i=0;i<9;i++){
    		printf("%d ",a[i]);
    	}
    	return 0;
     }

发表评论取消回复

表情：

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

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

相关阅读

相关归并排序（二路、递归）

归并排序排序策略将两个有序表归并为一个新的有序表排序过程 `i`与`j`分别是两个有序表的所索引 ①当`i`和`j` 都在两个表的表长内

深碍√TFBOYSˉ_/ 2023年05月22日 06:37/ 0 赞/ 22 阅读

相关归并排序-自顶向下的二路归并

自顶向下二路归并排序算法实现如下： include <stdio.h> include <malloc.h> define MaxSize 20

╰+攻爆jí腚メ/ 2023年03月13日 03:02/ 0 赞/ 23 阅读

相关归并排序-自底向上的二路归并

自底向上二路归并算法的实现： include <stdio.h> include <malloc.h> define MaxSize 20 t

柔情只为你懂/ 2023年03月13日 03:02/ 0 赞/ 19 阅读

相关二路归并排序

include<stdio.h> include<stdlib.h> typedef int DataType; //一次二

快来打我*/ 2023年02月17日 11:18/ 0 赞/ 16 阅读

相关【数据结构与算法】二路归并排序

空间复杂度由于辅助空间刚好要占用那个单元，但每一趟归并后这些空间就被释放了，所以归并排序的空间复杂度是O(n)。时间复杂度每趟归并的时间复杂度是O(n)

灰太狼/ 2022年08月11日 00:41/ 0 赞/ 179 阅读

相关数据结构-二路归并及归并排序

一、介绍：归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已

谁借莪１个温暖的怀抱￠/ 2022年06月04日 07:48/ 0 赞/ 379 阅读

相关归并排序——二路归并排序

/ 归并：指将两个或者两个以上的有序表合并成一个新的有序表二路归并算法思想：将长度为n的待排序数据表看

分手后的思念是犯贱/ 2022年03月20日 02:54/ 0 赞/ 355 阅读

相关归并排序算法（二路）——C/C++

归并排序（二路） 1. 算法思想归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再

r囧r小猫/ 2022年01月17日 01:35/ 0 赞/ 263 阅读

相关排序——二路归并排序

> 算法思想：将无序序列拆分至只有一个关键字的子序列；然后两两归并，直至归并成一个序列 > > 时间复杂度分析：共需进行log2n趟排序，每趟排序执行n次归并操作，因此时间复

素颜马尾好姑娘i/ 2021年11月05日 15:06/ 0 赞/ 353 阅读

相关多路归并排序

雪压枝头低，虽低不着泥今天准备放假，无聊看到一个场景题，问题如下：有一个文件里面存储着很多很多很多的无序的数，然后要求进行一个排序，内存限定，磁盘足够

我就是我/ 2021年09月25日 04:16/ 0 赞/ 326 阅读