-
两个有序数组归并排序
2014-08-11 15:34:41给定两个有序数组a b 使合并后的数组仍然有序 归并算法的事件复杂度为O logn -
将有序数组 归并排序 最多与最少比较次数
2017-12-05 13:22:09今天偶尔看到了归并排序的算法复杂度证明,对于将几个有序数组合并成一个有序数组的比较次数产生了兴趣。 设有两个有序数组 arr1 与 arr2,数组长度分别为 m 与 n, 要合并成一个长度位 m+n 的有序数组 arr3. ...今天偶尔看到了归并排序的算法复杂度证明,对于将几个有序数组合并成一个有序数组的比较次数产生了兴趣。
设有两个有序数组 arr1 与 arr2,数组长度分别为 m 与 n, 要合并成一个长度位 m+n 的有序数组 arr3.
最差情况下:比较次数为 m+n-1
此时,将数组 arr1 与数组 arr2 中的元素两两比较,将值小的放进数组 arr3, 直到数组 arr3 填满为止。
因为 arr3 有 m+n 个空位,每次两两比较就放进去一个数,而最后一个剩下的元素可以不用比较直接放进去,所以一共两两比较了 m+n-1 次。
最好情况下:比较次数为 min{m, n}
有个疑问: 若一个数组为 1, 2,3 ; 另一个数组为 4, 5, 6, 7; 则直接将后一个数组最小的与前一个数组最大的比较,仅需一次比较就行了
一定要注意,这是简单归并排序,必须从第一个元素比。
因此,最好情况下,至少需要两两比较一个数组的长度,比较次数为 min{m,n}
java 代码:
import java.util.Arrays; public class HelloWorld { static int[] mergeArray(int[] a, int[] b) { int k = a.length + b.length; int[] c = new int[k]; int m = 0; int n = 0; for (int i = 0; i < k; i++) { c[i] = a[m] > b[n] ? b[n++] : a[m++]; // 一共比较了 k-1 次 // 最后一个数单独处理 if (m == a.length) { c[k-1] = b[n]; break; } if (n == b.length) { c[k-1] = a[m]; break; } } return c; } public static void main(String[] args) { int[] a = {3, 6, 8, 10}; int[] b = {1, 2, 6, 9}; int[] c = mergeArray(a, b); System.out.println(Arrays.toString(c)); } }
-
有序数组归并和有序单链表归并
2017-10-26 17:12:35学归并排序算法的时候,先要了解归并有序数组。 顺便写个有序单链表的归并 /*有序数组的归并*/ function mergeArr(arr1, arr2) { var result = [], arr1_index = 0, arr2_index = 0; while(arr1_index ...学归并排序算法的时候,先要了解归并有序数组。
顺便写个有序单链表的归并
/*有序数组的归并*/ function mergeArr(arr1, arr2) { var result = [], arr1_index = 0, arr2_index = 0; while(arr1_index < arr1.length && arr2_index < arr2.length) { if(arr1[arr1_index] < arr2[arr2_index]) { result.push(arr1[arr1_index]); arr1_index++; } else { result.push(arr2[arr2_index]); arr2_index++; } } while(arr1_index < arr1.length) { result.push(arr1[arr1_index]); arr1_index++; } while(arr2_index < arr2.length) { result.push(arr2[arr2_index]); arr2_index++; } return result; } var arr1 = [1, 2, 4, 20, 30]; var arr2 = [0, 9]; //console.log(mergeArr(arr1, arr2)); /*有序单链表的归并*/ function LinkedList() { var Node = function (value) { this.value = value; this.next = null; } var head = null; var length =0; this.append = function (value) { var node = new Node(value); if(head == null) { head = node; length++; return; } else { appendNode(head, node); } } function appendNode(root, node) { if(root.next == null) { root.next = node; } else { appendNode(root.next, node); } length++; } this.toString = function () { var result = []; var temp = head; while(temp != null) { result.push(temp.value); temp = temp.next; } return result.join(" "); } this.getHead = function () { return head; } this.getLength = function () { return length; } } function linkedTest() { var arr1 = [2, 6, 9, 18, 25]; var arr2 = [0, 10, 30]; var linked_list1 = new LinkedList(); var linked_list2 = new LinkedList(); for(var i=0; i<arr1.length; ++i) { linked_list1.append(arr1[i]); } for(var i=0; i<arr2.length; ++i) { linked_list2.append(arr2[i]); } console.log("linked list1 ", linked_list1.toString()); console.log("linked list2 ", linked_list2.toString()); var merge_list = mergeLinkedList(linked_list1, linked_list2); console.log(merge_list.toString()); } /*单链表合并*/ function mergeLinkedList(list1, list2) { var result_list = new LinkedList(), list1_node = list1.getHead(); list2_node = list2.getHead(); while(list1_node && list2_node) { if(list1_node.value < list2_node.value) { result_list.append(list1_node.value); list1_node = list1_node.next; } else { result_list.append(list2_node.value); list2_node = list2_node.next; } } while(list1_node) { result_list.append(list1_node.value); list1_node = list1_node.next; } while(list2_node) { result_list.append(list2_node.value); list2_node = list2_node.next; } return result_list; } linkedTest();
-
Java下两个有序数组归并思想排序
2017-08-17 16:28:59现省略,具体后边再写,只要熟悉归并算法就不太难。 代码 package FileTest; public class Test { public static int[] arrayMerge(int[] a, int[] b) { int[] am = new int[a.length + b.length]; int ai = 0;解题思路
现省略,具体后边再写,只要熟悉归并算法就不太难。代码
package FileTest; public class Test { public static int[] arrayMerge(int[] a, int[] b) { int[] am = new int[a.length + b.length]; int ai = 0; int bj = 0; while ((ai<a.length) && (bj<b.length)) { if(a[ai] < b[bj]) { am[ai + bj] = a[ai]; ai++; } else { am[ai + bj] = b[bj]; bj++; } } while (ai < a.length) { am[ai + bj] = a[ai]; ai++; } while (bj < b.length) { am[ai + bj] = b[bj]; bj++; } return am; } public static void main(String[] args) { int[] a = {0,1,2,3,4,5,6,6}; int[] b = {1,2,3,4,5,6,7,8,9}; int[] am = new int[a.length + b.length]; am = arrayMerge(a, b); for (int i=0;i < am.length;i++) { System.out.print(am[i] + " "); } } }
-
c++ 数组 有序数组插入 归并排序思想
2017-08-02 22:01:32对于两个有序数组arr1和arr2,arr1的末尾有足够的空间可以容纳arr2。 把arr2的所有数组插入arr1中,使得插入后的数组仍然是个有序数组。 解决思路是从尾到头比较arr1和arr2中的数字的大小,然后将较大的数字插入到...对于两个有序数组arr1和arr2,arr1的末尾有足够的空间可以容纳arr2。
把arr2的所有数组插入arr1中,使得插入后的数组仍然是个有序数组。
解决思路是从尾到头比较arr1和arr2中的数字的大小,然后将较大的数字插入到相应的位置。
具体代码参考如下:
#include <iostream> using namespace std;
/*template<class T> 测试模板函数,可以忽略 int getArrayLen(T& arr) { return (sizeof(arr)/sizeof(arr[0])); }*/ void insertArray(int arr1[],int arr2[],int lastIndexOfArr1, int lastIndexOfArr2) //传输两个数组以及数组的末尾元素的下标 { if(lastIndexOfArr1<0 || lastIndexOfArr2<0) { return; } int newIndex=lastIndexOfArr1+lastIndexOfArr2+1; //两个数组合并到同一个数组之后的尾元素的下标 int len=newIndex+1; while(newIndex>0) //循环比较,较大的数字向后插入 { if(arr1[lastIndexOfArr1]>=arr2[lastIndexOfArr2]) { arr1[newIndex--]=arr1[lastIndexOfArr1]; if(lastIndexOfArr1!=0) lastIndexOfArr1--; } else { arr1[newIndex--]=arr2[lastIndexOfArr2]; if(lastIndexOfArr2!=0) lastIndexOfArr2--; } if(newIndex==0) //比较到最后,最小的数字,插入到数组的0下标位置 { arr1[0]=arr1[0]<arr2[0]?arr1[0]:arr2[0]; } } for(int i=0;i<len;i++) cout << arr1[i] << " "; cout << endl; } int main() { int arr1[30]={2,7,9,10,13,18,23,26,30,33}; int arr2[]={1,3,5,7,9,11,13,15,23,29,31}; insertArray(arr1,arr2,9,10); //cout << getArrayLen(arr1) << endl; 测试template函数模板,可以忽略 //cout << getArrayLen(arr2) << endl; return 0; }
上述代码主要的思路是从尾向头进行比较,降低复杂度的同时,避免了多次复制同一个数字的情况。 -
合并有序数组(归并排序)
2020-02-06 15:55:07合并有序数组 题:给定两个排序后的数组A和数组B,其中A的末端有足够的缓冲空间容纳B,编写一个方法,将B合并到A并排序 思路:参照归并排序 对A数组进行从后往前进行填充 A和B数组两两比较,大的数填到A中 public... -
数组归并排序
2013-08-11 10:18:21A和B是两个有序数组(假设为递增序列),而且A的长度足以放下A和B中所有的元素, 写一个函数将数组B融入数组A,并使其有序。 oid merge(int a[], int b[], int n, int m) { int k = m+n-1; int p = n-1; int q = m-... -
有序数组归并(C语言)
2020-02-28 15:54:10源码如下: #include <stdio.h> #define M 5 ...//归并排序 int main() { int a[M] = {2,3,5,7,9}; int b[N] = {2,4,6}; int c[M+N]; int x = 0,y = 0,t = 0; while(x<M && ... -
字符数组归并排序操作
2014-03-15 21:42:36两个排序好的字符数组,归并排序依然得到有序字符数组数组 char * cmp(char* s1,char* s2) { char *s= (char*)malloc(sizeof(char*)*20); char *ss=s; assert(s1); assert(s2); while(*s1!='\0'&&*s -
Scala数组归并排序
2016-06-06 17:49:26归并排序,思想是分而治之,然后合并得出结果。 分为两个阶段: 1.拆分(这里以拆分为两个部分为示例) 将一个数据集合分为A,B两个部分,分别对A,B排序, 而对A,B排序的方法,同样是将之分为两个部分然后排序。... -
二分求两个有序数组归并后第k小的数
2019-08-19 21:36:46显然按照归并排序的方式可以O(n)求,可是这样顺便把所有的k对应的答案都求出来了,浪费了时间,如何在O(logn)的复杂度求出? 首先我们令 x=在a数组取出的个数 y=在b数组取出的个数 总共取出了从小到大的k个,显然... -
LeetCode——合并两个有序数组(归并排序变形实例)
2021-02-12 08:48:46归并排序是将两个排好序的数组合并到一个新的数组中去, 而此题是将后一个小数组归并到前面一个大数组中去,仅此差异。 void merge(int *nums1, int nums1Size, int m, int *nums2, int nums2Size, int n) { //... -
合并两个有序数组(归并排序)
2017-03-16 19:10:51package com.zyt.interview;public class MergeSortArray { public static int[] sort(int[] a,int[] b){//a,b数组必须有序 int merge[]=new int[a.length+b.length]; int lenA=0,lenB=0,lenMer=0; -
归并排序和无序数组的归并排序
2018-11-21 21:47:36一、将两个有序数组归并排序 #include <stdio.h> #include <stdlib.h> int main() { int a[5],b[8],c[13]; //不失一般性,两个数组的长度不一样长 int i,j,k,flag=0; for(i=0;i&... -
第 2 题:合并二维有序数组成一维有序数组,归并排序的思路
2020-11-29 16:15:45<div><p>欢迎在下方发表您的优质见解</p><p>该提问来源于开源项目:lgwebdream/FE-Interview</p></div> -
归并排序C++代码实现(将两个有序数组元素依次比较合并为一个新的有序数组)
2019-06-13 10:54:02@归并排序C++代码实现(将两个有序数组元素依次比较合并为一个新的有序数组) 归并排序分为两个大的步骤,分为划分和归并。归并是将两个有序数组分别为数组A和数组B合并成为一个有序数组,首先取数组A和数组B的第一... -
面试题:在O(1)空间复杂度范围内对一个数组中前后连段有序数组进行归并排序...
2012-05-08 16:42:00面试题:在O(1)空间复杂度范围内对一个数组中前后连段有序数组进行归并排序 题目:数组al[0,mid-1]和al[mid,num-1]是各自有序的,对数组al[0,num-1]的两个子有序段进行merge,得到al[0,num-1]整体... -
面试算法篇-合并两个有序数组 (快速排序、归并排序)
2020-05-11 10:33:31package main import "fmt" func main() { arr := []int{2,1,4,3, 5, 6,7, 9} quickSort(arr, 0, len(arr)) ...合并两个有序数组 */ func dealSortOrderArrs() { arr1 := []int{1, 3, 5, 7} arr2 := []int. -
归并排序、合并两个有序数组
2020-04-22 21:01:12今天写个简简单单的归并排序。顺带个合并两个有序数组。 先来合并两个有序数组 #include<iostream> #include<vector> vector<int> mergeTwoArray(vector<int> arr1, vector<int> arr... -
百度:在O(1)空间复杂度范围内对一个数组中前后连段有序数组进行归并排序
2014-12-18 16:56:00题目:数组al[0,mid-1]和al[mid,num-1]是各自有序的,对数组al[0,num-1]的两个子有序段进行merge,得到al[0,num-1]整体有序。要求空间复杂度为O(1)。注:al[i]元素是支持'<'运算符的。 数据结构第一章就讲了... -
Algs4-2.2.8证明改进的归并排序对有序数组排序是线性级别的
2018-10-27 09:07:00=a[mid+1]就不调用merge()方法,请证明用归并排序处理一个已经有序的数组所需的比较次数是线性级别的。public static void sort(Comparable[] a,int lo,int hi) { if (hi<=lo) return; int mid=lo+(hi-lo)/... -
部分有序数组就地排序,要求时间复杂度为O(n)
2013-10-06 10:26:45思路:可以使用归并排序的思想,不过这里要求空间复杂度为O(1),所以可以转换为一个循环有序数组和一个有序数组的归并; 1,i,j分别指向带合并的两个数组的首元素,初始值i=0;j=mid;l1,l2代表待合
收藏数
3,557
精华内容
1,422