java 归并排序的实例详解
java归并排序的实例详解
归并排序
归并排序，指的是将两个已经排序的序列合并成一个序列的操作。
归并操作的过程如下：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
Java代码
/**
*归并排序
*
*@paramts
*/
@SuppressWarnings("unchecked")
publicstatic>voidmergeSort(T[]ts){
//辅助空间
T[]tempArray=(T[])newComparable[ts.length];
mergeSort(ts,tempArray,0,ts.length-1);
}
/**
*递归
*/
privatestatic>voidmergeSort(T[]ts,T[]tempArray,intleft,intright){
if(left>voidmerge(T[]ts,T[]tempArray,intleftPos,intrightPos,intrightEnd){
intleftEnd=rightPos-1;
inttemPos=leftPos;
intnumElements=rightEnd-leftPos+1;
while(leftPos<=leftEnd&&rightPos<=rightEnd)
//比较放到辅助空间
if(ts[leftPos].compareTo(ts[rightPos])<=0)
tempArray[temPos++]=ts[leftPos++];
else
tempArray[temPos++]=ts[rightPos++];
while(leftPos<=leftEnd)
tempArray[temPos++]=ts[leftPos++];
while(rightPos<=rightEnd)
tempArray[temPos++]=ts[rightPos++];
//考回原数组,此处最好用System.arraycopy优化
for(inti=0;i
复杂度：O(nlogn)
比较操作的次数介于(nlogn)/2和nlogn-n+1。赋值操作的次数是(2nlogn)。
归并算法的空间复杂度为：Θ(n)
稳定性：稳定
扩展：
在java中，当执行一次泛型排序时，进行一次元比较可能是昂贵的，但是移动元素则是省时间的。归并排序使用所有的流行的排序算法中最少的比较次数，因此是使用java的通用排序算中的上好的选择。
以上使用java使用归并排序的简单实例，有关java算法知识本站还有很多，大家可以搜索，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！