java 归并排序的实例详解

时间:2021-12-14 16:52:51

java 归并排序的实例详解

归并排序

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

归并操作的过程如下:

  •  申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  •  设定两个指针,最初位置分别为两个已经排序序列的起始位置
  •  比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  •  重复步骤3直到某一指针到达序列尾
  •  将另一序列剩下的所有元素直接复制到合并序列尾

Java代码 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * 归并排序
 *
 * @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的通用排序算中的上好的选择。

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

原文链接:http://flyouwith.iteye.com/blog/2178209#bc2394113