用自己的计算机做服务器建网站,阿里云自助建站模板,优化公司网站,网站维护要多久时间数组合并 假设有 n 个长度为 k 的已排好序#xff08;升序#xff09;的数组#xff0c;请设计数据结构和算法#xff0c; 将这 n 个数组合并到一个数组#xff0c;且各元素按升序排列。即实现函数#xff1a; void merge_arrays(const int* arr, int n, int k, int* out…数组合并 假设有 n 个长度为 k 的已排好序升序的数组请设计数据结构和算法 将这 n 个数组合并到一个数组且各元素按升序排列。即实现函数 void merge_arrays(const int* arr, int n, int k, int* output); 其中 arr 为按行优先保存的 n 个长度都为 k 的数组output 为合并后的按升序排列的数组大小为 n×k。
时间要求(评分规则)当 n k 时 满分时间复杂度不超过 O(n×k×log(n)) 75分时间复杂度不超过 O(n×k×log(n)×k) 59分其它如时间复杂度为 O(n2×k2) 时。
参考代码如下:(别抄理解下哈哈)
#includestdio.h
#includestdlib.h
//建立大根堆(大的在上面)
void build_bigroot(int *a, int i, int size){
//参数说明:a传入的数组,i待排序元素开始位置,size数组元素个数(长度)int j, s;//j是i的孩子指针,s暂存排序的元素//不设监视哨,所以从0(i)开始排序,孩子为2*i1 j 2 * i 1;s a[i];while(j size){//不可以取等哈 ,0开始的//存在右子树并且右子树更大,那么筛选右子树 if(j 1 size a[j1] a[j])j; if(s a[j])break;else{//如果大的记录在下,那么上浮 a[i] a[j];i j;j 2 * i 1;} }//最后把筛选完成后的数据放在合适位置a[i] s;
}void merge_arrays(const int *arr, int n, int k, int* output){//说明一下arr为const int类型,不能改动,所以只好浪费时空复制出来在变动int i, size, x;size n * k;int a[size];//const int 变化为intfor(i 0; i size; i)a[i] arr[i];//大堆化for(i size / 2 -1; i 0; i--)build_bigroot(a, i , size);//正式堆排, 前提是大堆for(i size - 1; i 1; i--){x a[0];a[0] a[i];a[i] x;build_bigroot(a, 0, i);}
//最后复制到outputfor(i 0; i size; i)output[i] a[i];
} 其实我不明白的是为什么不用辅助数组a,直接复制到output里面不行.......
以下不是参考代码!
请教大佬!!!
另外,我最初的考虑是希尔排序
主函数能运行, 但是写为子函数就有问题了: 主函数如下: //icoding测试貌似只有几十分
#includestdio.h
#includestdlib.h
void merge_arrays(const int *arr, int row, int col, int* output){int i, j, x;int d[10]; int delta;for(i 1; i 10; i)d[i] 0;for(i 0; i col * row; i)output[i] arr[i];x col; for(i 0; x; i, xx/ 2)d[i] x;for(i 0, delta d[i]; d[i]! 0; delta d[i], i){for(i delta; i row * col; i){if(output[i] output[i - delta]){//如果前面的元素更大,就需要改变元素的位置 x output[i];for(j i - delta; j 0 output[j] x; j - delta)output[j delta] output[j]; // 大的复制到后面的对应位置output[j delta] x; }}
}for(i 1; i row * col; i){x output[i];j i -1;while(x output[j]){output[j 1] output[j];j j -1;output[j1] x;}}
} 子函数类型的:
#includestdio.h
#includestdlib.h
void shellinsert(int *output, int length, int delta){//arr 待排序数组, 内部元素可以看为row个长度为col的升序数组以此首尾连接//length为数组整体总长度, delta为增量int i, j;int x;for(i delta; i length; i){if(output[i] output[i - delta]){//如果前面的元素更大,就需要改变元素的位置 x output[i];for(j i - delta; j 0 output[j] x; j - delta)output[j delta] output[j]; // 大的复制到后面的对应位置output[j delta] x; }}for(i0; i9 ;i)printf(%d , output[i]);printf(\n);
} void merge_arrays(const int *arr, int row, int col, int* output){
//数组长度为col, 总共有row个升序数组int i;int d[10];for(i 0; i col * row; i)output[i] arr[i];for(i 0; col; i, col / 2)d[i] col;for(i 0; d[i]; i)shellinsert(output, row * col, d[i]);
}int main(){int a[9] {12, 15, 16, 1, 2, 3, 4, 8, 10};int output[9];merge_arrays(a, 3, 3, output);int i 0;for(;i 9; i)printf(%d , output[i]);return 0;
}
