二路归并排序（迭代）——ANSI C实现

我就是我 2022-05-18 03:13 164阅读 0赞

typedef int ElementType;

/*
     * 将两个数组有序归并到一个数组中
     *
     * 输入参数1：第一个数组
     * 输入参数2：第一个数组的尺寸
     * 输入参数3：第二个数组
     * 输入参数4：第二个数组的尺寸
     *
     * 返回类型：有序归并后的新数组
     *
     * */
    void MergeArray(ElementType *arr1, int size1, ElementType *arr2, int size2, ElementType *newArr) {
    	// 检查输入参数
    	if (newArr == NULL) {
    		return;
    	}
    	if ((arr1 == NULL || size1 == 0) && (arr2 == NULL || size2 == 0)) {
    		return;
    	}
    	if (arr1 == NULL || size1 == 0) {
    		for (int index = 0; index < size2; index++)
    			newArr[index] = arr2[index];
    		return;
    	}
    	if (arr2 == NULL || size2 == 0) {
    		for (int index = 0; index < size1; index++)
    			newArr[index] = arr1[index];
    		return;
    	}
    
    	// 比较arr1与arr2中每个元素的大小，依次插入到newArr中
    	int i = 0, j = 0, k = 0;
    	while (i < size1 && j < size2) {
    		if (arr1[i] <= arr2[j]) {
    			newArr[k] = arr1[i];
    			i++;
    			k++;
    		}
    
    		if (arr1[i] > arr2[j]) {
    			newArr[k] = arr2[j];
    			j++;
    			k++;
    		}
    	}
    
    	// 插入arr1中的剩余元素
    	while (i < size1) {
    		newArr[k] = arr1[i];
    		i++;
    		k++;
    	}
    
    	// 插入arr2中的剩余元素
    	while (j < size2) {
    		newArr[k] = arr2[j];
    		j++;
    		k++;
    	}
    }

// 填充符号
    #define FILLER_CHAR -1
    ElementType *Sort(ElementType *arr, int size) {
    	// 检查参数，若arr为NULL或size为0，则说明是空表，返回NULL
    	if (arr == NULL || size <= 0)
    		return NULL;
    
    	// 求需要迭代的轮数，以及大于size，且是2的整数次幂的整数
    	int round = 0, compSize = 1;
    	while (compSize < size) {
    		round++;
    		compSize *= 2;
    	}
    
    	// 为辅助数组申请空间
    	ElementType *assist1 = (ElementType *) malloc(compSize * sizeof(ElementType));
    	ElementType *assist2 = (ElementType *) malloc(compSize * sizeof(ElementType));
    
    	// 将arr内的元素拷贝到assist1中，多于空位用填充符号补齐
    	for (int index = 0; index < compSize; index++) {
    		if (index < size)
    			assist1[index] = arr[index];
    		else
    			assist1[index] = FILLER_CHAR;
    	}
    
    	// 进行round轮二路归并排序
    	int subSize = 1;
    	int *temp = NULL;
    	for (int k = 1; k <= round; k++) {
    		for (int i = 0; i < compSize; i += 2 * subSize) {
    			MergeArray(assist1 + i, subSize, assist1 + i + subSize, subSize, assist2 + i);
    		}
    
    		// 求出下一轮归并时，每个子序列的大小
    		subSize *= 2;
    
    		// 交换assist1与assist2
    		temp = assist1;
    		assist1 = assist2;
    		assist2 = temp;
    	}
    
    	// 将排序后的assist1中的元素拷贝回arr
    	for (int i = size - 1, j = compSize - 1; i >= 0; i--, j--)
    		arr[i] = assist1[j];
    
    	return arr;
    }

int main() {
    
    	int size = 10;
    	int max = 300;
    	int *array = GetRandomArray(size, max);
    	printf("Original ");
    	PrintArray(array, size);
    	Sort(array, size);
    	printf("Sorted   ");
    	PrintArray(array, size);
    
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关归并排序的思想与实现（递归与迭代）

归并排序的思想核心思想：归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案”

怼烎@/ 2022年12月06日 15:55/ 0 赞/ 122 阅读

相关 rust 归并排序迭代

Rust 归并排序迭代参考大佬们的写法写了一个rust版。这个迭代（非递归）妙就妙在它创建啦一个栈来保存左右两个边界，类似模拟了递归的操作。实际上开销肯定是低于递

以你之姓@/ 2022年10月05日 09:45/ 0 赞/ 135 阅读

相关归并排序代码实现【递归实现+迭代实现】

1、归并排序--递归实现 2、归并排序--迭代实现 1、归并排序--递归实现 package aa; import java

野性酷女/ 2022年05月26日 12:58/ 0 赞/ 197 阅读

相关快速排序（迭代）——ANSI C实现

typedef int ElementType; / 分区信息结点（组成单链表） / typed

女爷i/ 2022年05月18日 06:40/ 0 赞/ 137 阅读

相关二路归并排序（迭代）——ANSI C实现

typedef int ElementType; / 将两个数组有序归并到一个数组中输入参数1：第一个

我就是我/ 2022年05月18日 03:13/ 0 赞/ 165 阅读

相关折半查找（迭代）——ANSI C实现

typedef int ElementType; int Search(ElementType arr, int size, ElementType

╰半夏微凉°/ 2022年05月16日 22:06/ 0 赞/ 119 阅读

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

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

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

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

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

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

相关【数据结构】排序：归并排序（2路归并排序算法）详解，递归实现与迭代实现（C++）

\笔记整理内部排序分类目录： - [插入排序][Link 1] \- [交换排序][Link 2] \- [选择排序][Link 3] -[\->归并排序]

野性酷女/ 2021年12月05日 03:49/ 0 赞/ 352 阅读

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

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

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