java 归并排序的实例详解

java 归并排序的实例详解

java 归并排序的实例详解

归并排序

归并排序，指的是将两个已经排序的序列合并成一个序列的操作。

归并操作的过程如下：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

 设定两个指针，最初位置分别为两个已经排序序列的起始位置

 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

 重复步骤3直到某一指针到达序列尾

 将另一序列剩下的所有元素直接复制到合并序列尾

Java代码

/**

* 归并排序

*

* @param ts

*/

@SuppressWarnings("unchecked")

public static > void mergeSort(T[] ts) {

// 辅助空间

T[] tempArray = (T[]) new Comparable[ts.length];

mergeSort(ts, tempArray, 0, ts.length - 1);

}

/**

* 递归

*/

private static > 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 > 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的通用排序算中的上好的选择。

以上使用java 使用归并排序的简单实例，有关java算法知识本站还有很多，大家可以搜索，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。