java歸并排序算法代碼

歸并排序的時間復雜度是：nlogn
主要是用到二路歸并排序，也就是把兩個有序集合合并為一個有序集合.
下面是我寫的一個遞歸二路歸并排序的算法：

public class MergeSort {
 // private static long sum = 0;

/**

<pre>
二路歸并
原理：將兩個有序表合并和一個有序表
</pre>
*
@param a
@param s
第一個有序表的起始下標
@param m
第二個有序表的起始下標
@param t
第二個有序表的結束小標
/
private static void merge(int[] a, int s, int m, int t) {
int[] tmp = new int[t - s + 1];
int i = s, j = m, k = 0;
while (i < m && j <= t) {
if (a[i] <= a[j]) {
tmp[k] = a[i];
k++;
i++;
} else {
tmp[k] = a[j];
// sum += (j - i) - (j - m);
j++;
k++;
}
}
while (i < m) {
tmp[k] = a[i];
i++;
k++;
}
while (j <= t) {
tmp[k] = a[j];
j++;
k++;
}
System.arraycopy(tmp, 0, a, s, tmp.length);
}
/*

@param a
@param s
@param len
每次歸并的有序集合的長度
*/
public static void mergeSort(int[] a, int s, int len) {
int size = a.length;
int mid = size / (len << 1);
int c = size & ((len<<1) - 1);
// -------歸并到只剩一個有序集合的時候結束算法-------//
if (mid == 0)
return;
// ------進行一趟歸并排序-------//
for (int i = 0; i < mid; ++i) {
s = i  2  len;
merge(a, s, s + len, (len << 1) + s - 1);
}
// -------將剩下的數和倒數一個有序集合歸并-------//
if (c != 0)
merge(a, size - c - 2 * len, size - c, size - 1);
//
// for (int i = 0; i < a.length; ++i) {
// System.out.print(a[i] + " ");
// }
// System.out.println();
// -------遞歸執行下一趟歸并排序------//
mergeSort(a, 0, 2 * len);
}
public static void main(String[] args) {
// merge(new int[] { 4, 3, 6, 1, 2, 5 }, 0, 3, 5);
int[] a = new int[] { 4, 3, 6, 1, 2, 5};
mergeSort(a, 0, 1);
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
// System.out.println("/n" + sum);
}


}</pre>