怎么在java 项目中使用归并排序算法

怎么在java 项目中使用归并排序算法？很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。

归并排序

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

归并操作的过程如下：

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

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

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

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

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

Java代码 

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

看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注编程网精选频道，感谢您对编程网的支持。