归并排序算法思想
所谓归并，就是将两个或两个以上的有序表合并成一个新的有序表。有两个已经排好序的有序表A[1]A[n]和B[1]B[m]，通过归并把它们合成一个有序表C[1]~C[m+n]。
基本思想：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序算法实现
private static int[] copy;
public static void main(String[] args) {
int[] arr = {3, 3, 3, 3, 3, 3, 4, 3};
int lo = 0;
int hi = arr.length - 1;
//create copy array
copy = new int[arr.length];
mergeSortToTop(arr, lo, hi);
mergeSortToButtom(arr);
for (int i : arr) {
System.out.print(i + " ");
}
}
/**
* 自顶而上的归并排序
*
* @param arr
* @return
*/
private static void mergeSortToButtom(int[] arr) {
int N = arr.length;
for (int sz = 1; sz < N; sz = sz + sz) {
for (int lo = 0; lo < N - sz; lo += sz + sz) {
merge(arr, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
}
}
}
/**
* 自顶而下的归并排序
*
* @param arr
* @param lo
* @param hi
* @return
*/
private static void mergeSortToTop(int[] arr, int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) / 2;
mergeSortToTop(arr, lo, mid);
mergeSortToTop(arr, mid + 1, hi);
merge(arr, lo, mid, hi);
}
/**
*其实就是两个数组合并
*
* @param arr
* @param lo
* @param mid
* @param hi
*/
private static void merge(int[] arr, int lo, int mid, int hi) {
int i = lo;
int j = mid + 1;
// 将原数组copy到新的数组里
for (int k = lo; k <= hi; k++) {
copy[k] = arr[k];
}
//分成两半进行排序
for (int k = lo; k <= hi; k++) {
if (i > mid) arr[k] = copy[j++];
else if (j > hi) arr[k] = copy[i++];
else if (arr[i] > arr[j]) arr[k] = copy[j++];
else arr[k] = copy[i++];
}
}
算法复杂度
1.平均时间复杂度： O(NLogN)
2.最好情况时间复杂度： O(NLogN)
3.最差情况时间复杂度： O(NLogN)
4.所需要额外空间： O(N)
算法稳定性
1.归并排序算法是稳定的
想看完整版算法请点击：归并排序
