6、 归并排序
归并算法稳定,数组需要O(n)的额外空间,链表需要O(log(n))的额外空间,时间复杂度为O(nlog(n)),算法不是自适应的,不需要对数据的随机读取。
public void mergeSort(){
long[] workSpace = new long[nElems];
recMergeSort(workSpace,0,nElems-1);
}
private void recMergeSort(long[] workSpace, int lowerBound, int upperBound){
if(lowerBound == upperBound){
return;
}
else{
int mid=(lowerBound+upperBound)/2;
recMergeSort(workSpace, lowerBound, mid);
recMergeSort(workSpace, mid+1, upperBound);
merge(workSpace, lowerBound, mid+1, upperBound);
}
}
private void merge(long[] workSpace, int lowPtr, int highPtr, int upperBound){
int j = 0;
int lowerBound = lowPtr;
int mid = highPtr - 1;
int n = upperBound-lowerBound+1;
while(lowPtr<=mid&&highPtr<=upperBound){
if(theArray[lowPtr]<theArray[highPtr]){
workSpace[j++]=theArray[lowPtr++];
}
else{
workSpace[j++]=theArray[highPtr++];
}
}
while(lowPtr<=mid){
workSpace[j++] = theArray[lowPtr++];
}
while(highPtr<=upperBound){
workSpace[j++] = theArray[highPtr++];
}
for(j=0;j<n;j++){
theArray[lowerBound+j]=workSpace[j];
}
}
分享到:
相关推荐
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
java排序算法使用及场景说明 文档后面有一些别人的链接,多在google上搜索Java排序算法,及维基百科上面也有很全的算法介绍。
java实现的常用的几种基本排序算法,插入、交换、选择、归并
JAVA排序算法总结,对常用的算法进行了总结,可以看看哦!!
Java排序算法实现 Java排序算法实现 Java排序算法实现
关于八种常见的排序算法的总结,里面有可运行的Java代码,方便打印
Java排序算法代码.
java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
Java常用8大排序算法,包含每种算法详细介绍,及代码如何实现。
Java所有排序算法大全 Java所有排序算法大全 Java所有排序算法大全 Java所有排序算法大全
尚硅谷Java排序算法PPT
Java排序算法 Java排序算法.rar
排序算法总结.doc 排序算法总结.doc 排序算法总结.doc
排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际...
java最常见的八种排序算法
Java各种排序算法代码.rar
几种内部排序算法总结!(冒泡排序、快速排序、直接插入排序、拆半插入排序、简单选择排序)
java产生多个随机数写入文件中,比较四种排序算法的效率
Java排序算法 Java排序算法 Java排序算法