歸并排序（Merge）是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。 將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。
歸并排序算法穩(wěn)定，數(shù)組需要O(n)的額外空間，鏈表需要O(log(n))的額外空間，時(shí)間復(fù)雜度為O(nlog(n))，算法不是自適應(yīng)的，不需要對(duì)數(shù)據(jù)的隨機(jī)讀取。
工作原理：
1、申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列
2、設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
3、比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
4、重復(fù)步驟3直到某一指針達(dá)到序列尾
5、將另一序列剩下的所有元素直接復(fù)制到合并序列尾
運(yùn)行代碼
復(fù)制代碼代碼如下:
package com.zc.manythread;
import java.util.Random;
/**
* 歸并排序
* @author 偶my耶
*
*/
public class MergeSort {
public static void mergeSort(int[] data) {
sort(data, 0, data.length - 1);
}
public static void sort(int[] data, int left, int right) {
if (left >= right)
return;
// 找出中間索引
int center = (left + right) / 2;
// 對(duì)左邊數(shù)組進(jìn)行遞歸
sort(data, left, center);
// 對(duì)右邊數(shù)組進(jìn)行遞歸
sort(data, center + 1, right);
// 合并
merge(data, left, center, right);
print(data);
}
/**
* 將兩個(gè)數(shù)組進(jìn)行歸并，歸并前面2個(gè)數(shù)組已有序，歸并后依然有序
*
* @param data
* 數(shù)組對(duì)象
* @param left
* 左數(shù)組的第一個(gè)元素的索引
* @param center
* 左數(shù)組的最后一個(gè)元素的索引，center+1是右數(shù)組第一個(gè)元素的索引
* @param right
* 右數(shù)組最后一個(gè)元素的索引
*/
public static void merge(int[] data, int left, int center, int right) {
// 臨時(shí)數(shù)組
int[] tmpArr = new int[data.length];
// 右數(shù)組第一個(gè)元素索引
int mid = center + 1;
// third 記錄臨時(shí)數(shù)組的索引
int third = left;
// 緩存左數(shù)組第一個(gè)元素的索引
int tmp = left;
while (left <= center && mid <= right) {
// 從兩個(gè)數(shù)組中取出最小的放入臨時(shí)數(shù)組
if (data[left] <= data[mid]) {
tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
// 剩余部分依次放入臨時(shí)數(shù)組（實(shí)際上兩個(gè)while只會(huì)執(zhí)行其中一個(gè)）
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
// 將臨時(shí)數(shù)組中的內(nèi)容拷貝回原數(shù)組中
// （原left-right范圍的內(nèi)容被復(fù)制回原數(shù)組）
while (tmp <= right) {
data[tmp] = tmpArr[tmp++];
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();
}
/**
* 產(chǎn)生隨機(jī)數(shù)組
* @param count
* @return
*/
private static int[] createDate(int count) {
int[] data=new int[count];
Random rand = new Random();
boolean[] bool = new boolean[100];
int num = 0;
for (int i = 0; i < count; i++) {
do {
// 如果產(chǎn)生的數(shù)相同繼續(xù)循環(huán)
num = rand.nextInt(100);
} while (bool[num]);
bool[num] = true;
data[i]=num;
}
return data;
}
public static void main(String[] args) {
int[] data = createDate(10);
print(data);
mergeSort(data);
System.out.println("排序后的數(shù)組：");
print(data);
}
}
運(yùn)行結(jié)果：
以上就是本文的全部?jī)?nèi)容了，希望小伙伴能夠喜歡。
