详解java 归并排序的实例
来源：爱站网时间：2019-10-14编辑：网友分享
今天爱站技术频道小编为大家带来详解java 归并排序的实例，其实我们初学者要多多接触不同类型的程序知识，才能进行不断的进步，下面就跟随爱站技术频道小编的步伐来学习吧！
今天爱站技术频道小编为大家带来详解java 归并排序的实例，其实我们初学者要多多接触不同类型的程序知识，才能进行不断的进步，下面就跟随爱站技术频道小编的步伐来学习吧！
详解java 归并排序的实例
归并排序
归并排序，指的是将两个已经排序的序列合并成一个序列的操作。
归并操作的过程如下：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
Java代码
/**
* 归并排序
*
* @param ts
*/
@SuppressWarnings("unchecked")
public static <T extends Comparable<? super T>> void mergeSort(T[] ts) {
// 辅助空间
T[] tempArray = (T[]) new Comparable[ts.length];
mergeSort(ts, tempArray, 0, ts.length - 1);
}
/**
* 递归
*/
private static <T extends Comparable<? super T>> void mergeSort(T[] ts, T[] tempArray, int left, int right) {
if (left < right) {
int center = (left + right) / 2;
mergeSort(ts, tempArray, left, center);
mergeSort(ts, tempArray, center + 1, right);
// 左右合并
merge(ts, tempArray, left, center + 1, right);
}
}
/**
* 合并
*/
private static <T extends Comparable<? super T>> void merge(T[] ts, T[] tempArray, int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1;
int temPos = leftPos;
int numElements = 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 (int i = 0; i < numElements; i++, rightEnd--)
ts[rightEnd] = tempArray[rightEnd];
}
复杂度：O(n log n)
比较操作的次数介于(n log n)/2和n log n - n + 1。 赋值操作的次数是(2nlogn)。
归并算法的空间复杂度为：Θ(n)
稳定性：稳定
以上就是详解java 归并排序的实例介绍，本站有很多关于java方面的知识，您可以搜索查阅，希望对您有所帮助，同时也感谢大家对爱站技术频道的支持。
