mergesortmerge sort 怎么排序奇数的数组?

c语言的归并排序的完整程序

这个不难: #include<stdio.h> // 一个递归函数 void mergesort(int *num,int start,int end); // 这个函数用来将两个排好序的数组进行合并 void merge(int *num,int start,int middle,int end); int main() { // 测试数组 int num[10]= {12,54,23,67,86,45,97,32,14,65}; int i; // 排序之前 printf("Before sorting: "); for (i=0; i<10; i++) { printf("%3d",num[i]); } printf(" "); // 进行合并排序 mergesort(num,0,9); printf("After sorting: "); // 排序之后 for (i=0; i<10; i++) { printf("%3d",num[i]); } printf(" "); return 0; } //这个函数用来将问题细分 void mergesort(int *num,int start,int end) { int middle; if(start<end) { middle=(start+end)/2; // 归并的基本思想 // 排左边 mergesort(num,start,middle); // 排右边 mergesort(num,middle+1,end); // 合并 merge(num,start,middle,end); } } //这个函数用于将两个已排好序的子序列合并 void merge(int *num,int start,int middle,int end) { int n1=middle-start+1; int n2=end-middle; // 动态分配内存，声明两个数组容纳左右两边的数组 int *L=new int[n1+1]; int *R=new int[n2+1]; int i,j=0,k; //将新建的两个数组赋值 for (i=0; i<n1; i++) { *(L+i)=*(num+start+i); } // 哨兵元素 *(L+n1)=1000000; for (i=0; i<n2; i++) { *(R+i)=*(num+middle+i+1); } *(R+n2)=1000000; i=0; // 进行合并 for (k=start; k<=end; k++) { if(L[i]<=R[j]) { num[k]=L[i]; i++; } else { num[k]=R[j]; j++; } } delete [] L; delete [] R; }

跪求归并排序的程序

我刚好有，还有解释，希望有帮助。

可以加分，谢谢 例3归并排序 合并排序（MERGE SORT）是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。

它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个 N/2 个长度为2或1的有序子序列，再两两合并，如此重复，值得得到一个长度为N的有序数据序列为止，这种排序方法称为2—路合并排序。

例如数组A有7个数据，分别是： 49 38 65 97 76 13 27，那么采用归并排序算法的操作过程如图7所示： 初始值 [49] [38] [65] [97] [76] [13] [27] 看成由长度为1的7个子序列组成 第一次合并之后 [38 49] [65 97] [13 76] [27] 看成由长度为1或2的4个子序列组成 第二次合并之后 [38 49 65 97] [13 27 76] 看成由长度为4或3的2个子序列组成 第三次合并之后 [13 27 38 49 65 76 97] 合并算法的核心操作就是将一维数组中前后相邻的两个两个有序序列合并成一个有序序列。

合并算法也可以采用递归算法来实现，形式上较为简单,但实用性很差。

合并算法的合并次数是一个非常重要的量,根据计算当数组中有3到4个元素时,合并次数是2次,当有5到8个元素时,合并次数是3次,当有9到16个元素时,合并次数是4次，按照这一规律,当有N个子序列时可以推断出合并的次数是X(2 >=N,符合此条件的最小那个X)。

其时间复杂度为：O(nlogn).所需辅助存储空间为：O(n) 归并排序实际上就是二分法在排序中的应用。

它的的基本思想是：将待排序的数列分成两个小的数集，先对两个子集进行排序，然后进行两个有序子集的合并，形成排序后的数列（称为序列）。

而对子集的排序方法与刚才的处理方法是一致的，直到子集中只存在一个整数为止，结束分解。

参考程序 program pxgb; type arr=array[1..100000]of integer; var a:arr; p,q,i,j,k,r,n:integer; procedure merge(p,q,r:integer); var i,j,k:integer; temp:arr; begin i:=p; j:=q+1; k:=p; while (k<=r) do begin if (i<=q) and ( (j>r) or (a[i]<a[j] ) ) then begin temp[k]:=a[i]; inc(i); end else begin temp[k]:=a[j]; inc(j); end; inc(k); end; for i:=p to r do a[i]:=temp[i]; end; procedure merge_sort(a:arr; p, r:integer); var q:integer; begin if p<>r then begin q:=(p+r-1)div 2; merge_sort(a,p,q); merge_sort(a,q+1,r); merge(p,q,r); end; end; begin readln(n); for i:=1 to n do read(a[i]); merge_sort(a,1,n); for i:=1 to n do write(a[i]，‘ ’); readln; readln; end.

JAVA中的Merge Sort 求debug 帮看为什么不行 一直有问题 急 在线等

第一你定义了public static pareTo(String s1, String s2){ 但实际你根本没用它，你调用的是l[i]pareTo(r[i]) < 0 ,字符串类自带pare方法， 这不重要，因为你的自定义函数想要达到的效果和他一样 ，这是一个失误，但不会构成错误 第二 while (k < l.length + r.length) { if ((i < l.length) && (j < r.length)) { if(l[i]pareTo(r[i]) < 0) { finalresult[k] = l[i]; 这里面的 if(l[i]pareTo(r[i]) < 0) 这是错误 改成 pareTo(l[i], r[j]) < 0) 就对了 因为你是两个下标对应两个数组 ，肯定不是总比较同下标的字符串，所以一定是i和j的比较 而不是两个i 改完就o排在p前面了

归并排序:8和15行递归调用了mergesort方法，18行什么意思？是2和9会传进去吗？那其他4

程序执行顺序在图中从左至右的，不是你想的三次拆分再三次合并，图如果从上往下看，是问题的分析过程，不是执行过程。

从2954 执行到2459，左边完毕。

8167执行到1678，右边完毕。

最后merge上面结果。

归并排序算法

两种归并排序算法的实现：二路归并排序和基本归并排序（虚拟消除递归的二路归并排序） #define ARRAY_SIZE 1024 int B[1024]; //使用一个全局变e69da5e887aa7a686964616f31333236366238量，避免归并排序中每次都重新申请和释放空间造成的开销 template <typename T> void Merge(T A[], int l, int m, int h) { int i = l; int j = m+1; int k = 0; while(i<=m&&j<=h) { if(A[i]<A[j]) { B[k++] = A[i]; i++; } else { B[k++] = A[j]; j++; } } while(i<=m) { B[k++] = A[i++]; } while(j<=h) { B[k++] = A[j++]; } for(i=l; i<=h; i++) { A[i] = B[i-l]; } } //二路归并排序的实现 template <typename T> void MergeSort(T a[], int l, int h) { int m = (h+l)/2; if(l>=h) { return; } if(l+1==h) { if(a[l]>a[h]) { std::swap(a[l], a[h]); } return; } MergeSort(a, l, m); MergeSort(a, m+1, h); Merge(a, l, m, h); } //将a经过步长s归并到b中，n表示数组的大小 template <typename T> void Merge2(T a[], T b[], int s, int n) { int m = 0; //从头至尾按照步长s进行相邻数据的合并 for(int i=0; i<n; i+=2*s) { int j = i; //合并的第一组数的起始位置 int k = i+s; //合并的第二组数的起始位置 int jE = i+s; //合并的第一组数的起始位置 int kE = i+2*s; //合并的第二组数的起始位置 while((j<jE)&&(k<kE)&&j<n && k<n) { if(a[j]<a[k]) { b[m++] = a[j]; j++; } else { b[m++] = a[k]; k++; } } while((j<jE)&&(j<n)) { b[m++] = a[j++]; } while((k<kE)&&(k<n)) { b[m++] = a[k++]; } } } //基本归并排序，虚拟消除递归 template <typename T> void MergeSort2(T a[], int n) { int s = 1; //merge 的步长 T* b = new T[n]; while(s<n) { Merge2(a, b, s, n); //由a合并到b s += s; Merge2(b, a, s, n); //由b合并到a s += s; } delete[] b; } //使用如下代码在VS2005中可以对两种归并排序进行性能比较， //基本归并排序的时间性能稍微好一点，基本归并排序直接对数据按步长Merge， //而二路归并排序需要将数据先不断的分层，到为一个或者两个元素时再进行Merge void main() { int * p = new int[ARRAY_SIZE]; int i = 0; for(i=0; i<ARRAY_SIZE; i++) { *(p+i) = rand()%ARRAY_SIZE; } MergeSort(p, 0, ARRAY_SIZE-1); for(i=0; i<ARRAY_SIZE; i++) { *(p+i) = rand()%ARRAY_SIZE; } MergeSort2(p, ARRAY_SIZE); delete[] p; }

merge sort 怎么排序奇数的数组?

int[]?arr?=?{5,7,9,1,3,4,8,6,2}; int[]?left?=?new?int[arr.length?/?2?+?1]; int[]?right?=?new?int[arr.length?/?2]; System.arraycopy(arr,0,left,0,left.length); System.arraycopy(arr,arr.length-left.length?+?1,right,0,right.length);