如何實(shí)現(xiàn)歸并排序
歸并排序的時(shí)間復(fù)雜度是：nlogn，如何實(shí)現(xiàn)歸并排序呢?下面是小編給大家提供的算法，大家可以參考閱讀，更多詳情請(qǐng)關(guān)注應(yīng)屆畢業(yè)生考試網(wǎng)。
歸并排序的時(shí)間復(fù)雜度是：nlogn,主要是用到二路歸并排序，也就是把兩個(gè)有序集合合并為一個(gè)有序集合.
遞歸二路歸并排序的算法：
代碼片段(1)
view sourceprint;
package algorithm;
public class MergeSort {
/pic/p>
/**
* <pre>
* 二路歸并
* 原理：將兩個(gè)有序表合并和一個(gè)有序表
* </pre>
*
* @param a
* @param s
* 第一個(gè)有序表的起始下標(biāo)
* @param m
* 第二個(gè)有序表的起始下標(biāo)
* @param t
* 第二個(gè)有序表的結(jié)束小標(biāo)
*
*/
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];
/pic/p>
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
* 每次歸并的有序集合的長(zhǎng)度
*/
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);
/pic/pic/p>
if (mid == 0)
return;
/pic/pic/p>
for (int i = 0; i < mid; ++i) {
s = i * 2 * len;
merge(a, s, s + len, (len << 1) + s - 1);
}
/pic/pic/p>
if (c != 0)
merge(a, size - c - 2 * len, size - c, size - 1);
/pic/p>
/pic/p>
/pic/p>
/pic/p>
/pic/p>
/pic/pic/p>
mergeSort(a, 0, 2 * len);
}
public static void main(String[] args) {
/pic/p>
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] + " ");
}
/pic/n" + sum);
}
}
【如何實(shí)現(xiàn)歸并排序】相關(guān)文章：
C語(yǔ)言實(shí)現(xiàn)歸并排序算法02-04
C語(yǔ)言實(shí)現(xiàn)歸并排序算法實(shí)例07-13
C語(yǔ)言實(shí)現(xiàn)歸并排序算法實(shí)例分析01-25
C++實(shí)現(xiàn)自底向上的歸并排序算法03-14
C++實(shí)現(xiàn)自頂向下的歸并排序算法12-21
C++歸并排序算法實(shí)例02-09