淺析java 合並排序算法。本站提示廣大學習愛好者：（淺析java 合並排序算法）文章只能為提供參考，不一定能成為您想要的結果。以下是淺析java 合並排序算法正文
合並排序（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);
}
}
運轉成果：
以上就是本文的全體內容了，願望小同伴可以或許愛好。
