public classMergeSort
{// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
private static void
merge
( Comparable [ ]arr,
intl,
intmid,
intr
) {Comparable [ ]
aux
= Arrays.
copyOfRange (arr, l, r
+ 1 ) ;// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
int
i
=l, j
=mid
+ 1 ;for ( int
k
=l
;k
<=r
;k
++ ) {if (
i
>mid
) {// 如果左半部分元素已经全部处理完毕
arr
[k
] =aux
[j
-l
] ;j
++;} else if (
j
>r
) {// 如果右半部分元素已经全部处理完毕
arr
[k
] =aux
[i
-l
] ;i
++;} else if (
aux
[i
-l
].
compareTo (aux
[j
-l
] ) < 0 ) {// 左半部分所指元素 < 右半部分所指元素
arr
[k
] =aux
[i
-l
] ;i
++;} else {
// 左半部分所指元素 >= 右半部分所指元素
arr
[k
] =aux
[j
-l
] ;j
++;}
}
}
// 递归使用归并排序,对arr[l...r]的范围进行排序
private static void
sort
( Comparable [ ]arr,
intl,
intr
) {if (
l
>=r
) {return ;
}
int
mid
= (l
+r
) / 2 ;sort
(arr, l, mid
) ;sort
(arr, mid
+ 1, r
) ;// 对于arr[mid] <= arr[mid+1]的情况,不进行merge
// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
if (
arr
[mid
].
compareTo (arr
[mid
+ 1 ] ) > 0 )merge
(arr, l, mid, r
) ;}
public static void
sort
( Comparable [ ]arr
) {int
n
=arr.
length ;sort
(arr,
0, n
- 1 ) ;}
// 测试MergeSort
public static void
main
( String [ ]args
) {int
N
= 1000 ;Integer [ ]
arr
=SortTestHelper.
generateRandomArray (N,
0,
) ;sort
(arr
) ;//打印数组
SortTestHelper.
printArray (arr
) ;}
}
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/6787.html