合并排序
合并算法,指的是将两个已经排序的序列合并成一个序列的操作
操作步骤:
1. 建立一个数组C用来存放合并后的数
2. 从数组A和数组B的首端开始比较,将大的元素放入C中
3. 重复2操作,直至其中一个数组的元素被用完,则将另一个数组中剩余的元素拷贝到C中
比较复杂度:n㏒n
交换(赋值)复杂度:n㏒n
优点:比较快速的排序算法
缺点:需要额外的空间存放临时数组
private static void merge(Integer[] array,final int left,final int leftEnd, final int rightEnd){
Integer[] mergeResult = new Integer[rightEnd-left+1];
int i = 0; //mergeResult的下标
int j = left; //left 的下标
int k = leftEnd+1; //right 的下标
//将两个数组中较小的元素拷贝到mergeResult中
while(j<=leftEnd&&k<=rightEnd){
if(array[j]<array[k]){
mergeResult[i++] = array[j++];
}else{
mergeResult[i++] = array[k++];
}
}
//将另一个数组中剩余的元素拷贝到mergeResult中
while(j<=leftEnd){
mergeResult[i++] = array[j++];
}
while(k<=rightEnd){
mergeResult[i++] = array[k++];
}
//copy mergeResult to array
int leftPos = left;
for(int m=0;m<mergeResult.length;m++,leftPos++){
array[leftPos] = mergeResult[m];
}
}
private static void mergeSort(Integer[] array,final int left,final int leftEnd, final int rightEnd){
if(left>=rightEnd){
return;
}
mergeSort(array,left,(left+leftEnd)/2,leftEnd);
mergeSort(array,leftEnd+1,(leftEnd+1+rightEnd)/2,rightEnd);
merge(array,left,leftEnd,rightEnd);
}
public static void mergeSort(Integer[] array){
mergeSort(array,0,(array.length)/2,array.length-1);
}
分享到:
相关推荐
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...
合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序的C语言实现,原创。
自然合并排序是对合并排序的非递归形式的一种改进,很好很有用
/************合并排序算法的实现******************/ int main() { int p,q,r; printf("合并排序算法的实现:\n"); printf("请输入p、q、r的值(输入格式1,12,13):"); scanf("%d,%d,%d",&p,&q,&r); printf("p=%...
c++实现的合并排序算法 用递归和非递归两种方式实现的
这是用c++编写的一个合并排序的程序……
这些代码是对算法导论上对排序部分的总结,实现了以下排序方法:插入排序,合并排序,堆排序,快速排序,计数排序,每种实现都有详细的注释和相应的测试程序,可查找http://blog.csdn.net/china8848<br>中对相关问题...
针对200000长度的数组,采用插入排序和合并排序,对比两种算法的时间复杂度
这是我写的一个合并排序 用c语言实现 的,
C语言实现的排序算法,包括快排和合并排序,测试通过
经典排序算法的合并排序算法的C语言实现,适合初学者
c++ 分治法合并排序 merge sort c语言 分治法合并排序 merge sort(将cout修改printf 加头文件include "stdio.h")
通过动态规划来实现快速排序和合并排序!使我们更能很好的应用于实际中!!
实现并验证合并排序算法; 实现并验证快速排序算法(参考习题5.2第7a题,P140); 用递归与分治的方法设计并实现寻找第k小元素算法
分治策略 合并排序 快速排序 代码 C语言 是自己写的程序,还请各位指教
C#写的合并排序
利用分治法的合并排序实现数组的排序,根据算法导论第二章编写
java语言实现合并排序
合并排序的递归调用和合并排序的非递归调用的对比,可以让人感受到选择递归调用可以提高工作作业效率,只要得到递归公式和递归出口就可以了,问题解决起来会很省力
自底向上合并排序算法 ,望对大家有帮助,谢谢!