三门峡高端网站开发,高中文凭能学做网站吗,在阿里云做的网站怎么移动,上海网站推荐文章目录 1 题目2 思路2.1 思路1#xff08;直接插入法#xff09;2.2 思路2#xff08;归并#xff09; 3 实现3.1 思路13.2 思路2 1 题目
设mn个元素顺序存放在数组A[1…mn]中#xff0c;前m个元素递增有序#xff0c;后n个元素递增有序#xff0c;试设计一个在时间和… 文章目录 1 题目2 思路2.1 思路1直接插入法2.2 思路2归并 3 实现3.1 思路13.2 思路2 1 题目
设mn个元素顺序存放在数组A[1…mn]中前m个元素递增有序后n个元素递增有序试设计一个在时间和空间两方面都尽可能高效的算法使得整个顺序表递增有序。
2 思路
2.1 思路1直接插入法
把数组A看作是两个长度分别为m和n的有序表L1、L2把L2的每个元素依次插入到L1中的合适位置即可。
1取表L2中第一个元素A[m1]暂存为tmp把tmp插入到L1中合适的位置L[i]tmpL1[i1]2重复操作1把A[m2]、A[m3]…A[mn]依次插入到L1中直至整个数组有序。
时间复杂度O(mn) 空间复杂度O1
2.2 思路2归并
1把数组A前m个元素和后n个元素视为两个归并段L1、L2增加一个辅助数组B[1…mn]存储临时归并的结果。设k1、k2、k3分别指向L1L2的首位和数组B的下一个结果位置。2当k1m并且k2mn时执行3否则执行4: 3比较两个归并段指针所指元素的大小若A[k1]A[k2]那么B[k3]A[k1]否则B[k3]A[k2]执行2 4若k1m则把第二归并段剩余的元素复制到数组B末尾若k2mn,则把第一个归并段剩余的元素复制到数组B最后把数组B复制到数组A。
时间复杂度O(mn) 空间复杂度O(mn)
3 实现
3.1 思路1
#includecstdiovoid solution1(int *A, int m, int n){int tmp, j;for(int i m1; i mn;i){tmp A[i];//暂存元素防止后面移动元素时元素丢失for(j i-1;j 0 A[j] tmp;j--)//当L1中的元素大于tmp时就是插入tmp的位置A[j1] A[j];A[j1] tmp;}
}void print(int* A, int n){for(int i 0;i n;i){printf(%d , A[i]);}printf(\n);
}int main(){int A[] {0, 1,4,7,2,3,6};solution(A, 3, 3);print(A, sizeof(A)/sizeof(A[0]));return 0;
}3.2 思路2
#includecstdiovoid solution2(int *A, int m, int n){int B[mn1];int k1 1, k2 m1, k3 1;//三个指针while(k1m k2 m n){//归并把较小的元素复制到B中if(A[k1] A[k2]) B[k3] A[k1];else B[k3] A[k2];}if(k1 m) //把没有比较完的归并段的剩余元素复制到B中while(k2 mn) B[k3] A[k2];if(k2 mn)while(k1 m) B[k3] A[k1];for(int i 1;i mn;i){//把数组B复制到数组A中A[i] B[i];}
} void print(int* A, int n){for(int i 0;i n;i){printf(%d , A[i]);}printf(\n);
}int main(){int A[] {0, 1,4,7,2,3,6};solution2(A, 3, 3);print(A, sizeof(A)/sizeof(A[0]));return 0;
}
