mergesortjava编程合并排序算法

二路归并排序的算法及例子

#include<stdio.h> #include<stdlib.h> typedef int RecType;//要排序元素类型 void Merge(RecType *R,int low,int m,int high) {//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high] int i=low,j=m+1,p=0; //置初始值 RecType *R1; //R1是局部向量 R1=(RecType *)malloc((high-low+1)*sizeof(RecType)); if(!R1)return; //申请空间失败 while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上 R1[p++]=(R[i]<=R[j])?R[i++]:R[j++]; while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中 R1[p++]=R[i++]; while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中 R1[p++]=R[j++]; for(p=0,i=low;i<=high;p++,i++) R[i]=R1[p];//归并完成后将结果复制回R[low..high] } void MergeSort(RecType R[],int low,int high) {//用分治法对R[low..high]进行二路归并排序 int mid; if(low<high){//区间长度大于1 mid=(low+high)/2;//分解 MergeSort(R,low,mid);//递归地对R[low..mid]排序 MergeSort(R,mid+1,high); //递归地对R[mid+1..high]排序 Merge(R,low,mid,high);//组合，将两个有序区归并为一个有序区 } } void main() { int a[8]={21,34,56,43,99,37,78,10};//这里对8个元素进行排序 int low=0,high=7;//初始化low和high的值 MergeSort(a,low,high); for(int i=low;i<=high;i++)printf("%d ",a[i]);//输出测试 printf(" "); }

在快速排序、堆排序、归并排序中，什么排序是稳定的？

归并排序是稳定的 “快速排序和堆排序都不稳定 不稳定：就是大小相同的两个数，经过排序后，最终位置与初始位置交换了。

快速排序： 27 23 27 3 以第一个27作为pivot中心点，则27与后面那个3交换，形成 3 23 27 27，排序经过一次结束，但最后那个27在排序之初先于初始位置3那个27，所以不稳定。

堆排序： 比如：3 27 36 27， 如果堆顶3先输出，则，第三层的27（最后一个27）跑到堆顶，然后堆稳定，继续输出堆顶，是刚才那个27，这样说明后面的27先于第二个位置的27输出，不稳定。

” “2 归并排序（MergeSort） 归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。

合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。

” 参考资料：

java编程合并排序算法

package?p1; import?java.util.Arrays; public?class?Guy { /** ?*?归并排序 ?*/ private?static?void?mergeSort?(?int[]?array,?int?start,?int?end,?int[]?tempArray?) { if?(end?<=?start) { return; } int?middle?=?(?start?+?end?)?/?2; mergeSort?(array,?start,?middle,?tempArray); mergeSort?(array,?middle?+?1,?end,?tempArray); int?k?=?0,?leftIndex?=?0,?rightIndex?=?end?-?start; System.arraycopy?(array,?start,?tempArray,?0,?middle?-?start?+?1); for?(?int?i?=?0;?i?<?end?-?middle;?i++?) { tempArray[end?-?start?-?i]?=?array[middle?+?i?+?1]; } while?(k?<?end?-?start?+?1) { if?(tempArray[rightIndex]?>?tempArray[leftIndex])?//?从小到大 { array[k?+?start]?=?tempArray[leftIndex++]; } else { array[k?+?start]?=?tempArray[rightIndex--]; } k++; } } public?static?void?main?(?String[]?args?) { int[]?array?=?new?int[]?{?11,?213,?134,?65,?77,?78,?23,?43?}; mergeSort?(array,?0,?array.length?-?1,?new?int[array.length]); System.out.println?(Arrays.toString?(array)); } }