歸并排序（Merge）是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。 將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。
歸并排序算法穩定，數組需要O(n)的額外空間，鏈表需要O(log(n))的額外空間，時間復雜度為O(nlog(n))，算法不是自適應的，不需要對數據的隨機讀取。
工作原理：
1、申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
2、設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
3、比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
4、重復步驟3直到某一指針達到序列尾
5、將另一序列剩下的所有元素直接復制到合并序列尾
運行代碼
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;
// 對左邊數組進行遞歸
sort(data, left, center);
// 對右邊數組進行遞歸
sort(data, center + 1, right);
// 合并
merge(data, left, center, right);
print(data);
}
/**
* 將兩個數組進行歸并，歸并前面2個數組已有序，歸并后依然有序
*
* @param data
* 數組對象
* @param left
* 左數組的第一個元素的索引
* @param center
* 左數組的最后一個元素的索引，center+1是右數組第一個元素的索引
* @param right
* 右數組最后一個元素的索引
*/
public static void merge(int[] data, int left, int center, int right) {
// 臨時數組
int[] tmpArr = new int[data.length];
// 右數組第一個元素索引
int mid = center + 1;
// third 記錄臨時數組的索引
int third = left;
// 緩存左數組第一個元素的索引
int tmp = left;
while (left <= center && mid <= right) {
// 從兩個數組中取出最小的放入臨時數組
if (data[left] <= data[mid]) {
tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
// 剩余部分依次放入臨時數組（實際上兩個while只會執行其中一個）
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
// 將臨時數組中的內容拷貝回原數組中
// （原left-right范圍的內容被復制回原數組）
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();
}
/**
* 產生隨機數組
* @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 {
// 如果產生的數相同繼續循環
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("排序后的數組：");
print(data);
}
}
運行結果：
以上就是本文的全部內容了，希望小伙伴能夠喜歡。
