归并排序就是将2个有序的序列合并起来,其时间复杂度为O(nlgn),而且它是一种稳定的排序,它的缺点是需要额外n的空间来辅助排序。
java实现">接下来看其Java实现
java">public class MergeSort {
public static void main(String[] args) {
Integer[] arr = {1, 6, 9, 3, 2, 11, 15, 4};
mergeSort(arr);
Arrays.sort(arr);
}
public static void mergeSort(Integer[] arr) {
sort(arr, 0, arr.length - 1);
}
public static void sort(Integer[] arr, int left, int rigth) {
if (left >= rigth) {
return;
}
int center = (left + rigth) / 2;
//对左边的进行递归排序
sort(arr, left, center);
//右边进行递归排序
sort(arr, center + 1, rigth);
//两边排序好的进行合并
merge(arr, left, center, rigth);
print(arr);
}
javadoc">/**
* 合并
*javadoctag"> @param arr
*javadoctag"> @param left
*javadoctag"> @param center
*javadoctag"> @param right
*/
public static void merge(Integer[] arr, int left, int center, int right) {
//辅助数组
Integer[] aux = new Integer[arr.length];
//辅助数组下标
int auxIndex = left;
//存储左边下标
int temp = left;
//中间的位置
int mid = center;
center += 1;
//遍历比较直到有一边的数组比较完成
while (left <= mid && center <= right) {
if (arr[left] <= arr[center]) {
aux[auxIndex++] = arr[left++];
} else {
aux[auxIndex++] = arr[center++];
}
}
//下面2个while是将没有合并完成的一边放入数组
while (left <= mid) {
aux[auxIndex++] = arr[left++];
}
while (right >= (center)) {
aux[auxIndex++] = arr[center++];
}
//将排序好的数组放回原数组中
while (temp <= right) {
arr[temp] = aux[temp++];
}
}
javadoc">/**
* 打印数组
*javadoctag"> @param arr
*/
public static void print(Integer[] arr) {
for (Integer a : arr) {
System.out.print(a + ", ");
}
System.out.println();
}
}
过程就是递归排序两边的序列,然后将排序好的两边序列进行合并。
归并排序">JDK中改进过的归并排序
jdk中的工具类对数组和list进行的排序便是改进过的归并排序
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off) {
int length = high - low;
// 数组小于7时将使用插入排序
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
//从中间分两部分进行递归
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);
//如果一边最大的小于另一边最小的,直接合并
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}
// 将两边的序列进行合并
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}