歸并排序介紹:
歸并排序（MERGE-SORT）是利用歸并的思想實現(xiàn)的排序方法政溃，該算法采用經典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解唠叛，而治(conquer)的階段則將分的階段得到的各答案"修補"在一起，即分而治之)已卷。
歸并排序示意圖
歸并排序示意圖
說明:
可以看到這種結構很像一棵完全二叉樹，本文的歸并排序我們采用遞歸去實現(xiàn)（也可采用迭代的方式去實現(xiàn)）露戒。分階段可以理解為就是遞歸拆分子序列的過程占哟。
歸并排序思想示意圖-合并相鄰有序子序列:
再來看看治階段，我們需要將兩個已經有序的子序列合并成一個有序序列翩迈，比如上圖中的最后一次合并持灰，要將[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]负饲，來看下實現(xiàn)步驟
歸并
歸并
代碼實現(xiàn)
package cn.icanci.datastructure.sort;
import javax.swing.*;
import java.util.Arrays;
/**
* @Author: icanci
* @ProjectName: AlgorithmAndDataStructure
* @PackageName: cn.icanci.datastructure.sort
* @Date: Created in 2020/3/7 10:47
* @ClassAction: 歸并排序
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = {8, 4, 5, 7, 1, 3, 6, 2,123,324,546,457,234,1234,534,12,313,1345,346,3};
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 1, temp);
System.out.println("歸并排序之后");
System.out.println(Arrays.toString(arr));
}
//分+合的方法
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;
//向左遞歸分解
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
//合并
merge(arr,left,mid,right,temp);
}
}
/**
* 合并的方法
*
* @param arr 排序的原始數(shù)組
* @param left 左邊
* @param mid 中間
* @param right 右邊
* @param temp 臨時數(shù)組
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
//初始化 i ,左邊有序序列的索引
int i = left;
//初始化節(jié)點 j 右邊有序序列的初始索引
int j = mid + 1;
//指向 temp的當前索引
int t = 0;
//先把所有的兩邊(有序)的數(shù)據 填充到temp數(shù)組
//知道有一方處理完畢則結束
while (i <= mid && j <= right) {
//繼續(xù)
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t++;
i++;
} else {
temp[t] = arr[j];
t++;
j++;
}
}
//再把剩余數(shù)據的一般的數(shù)據依次填充到temp
while (i <= mid) {
//左邊有剩余 全部填充到temp
temp[t] = arr[i];
t++;
i++;
}
while (j <= right) {
//左邊有剩余 全部填充到temp
temp[t] = arr[j];
t++;
j++;
}
//最有把temp的數(shù)組元素拷貝到arr
//最后一次拷貝
t = 0;
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t++;
tempLeft++;
}
}
}
測試8000000條數(shù)據
package cn.icanci.datastructure.sort;
import cn.icanci.datastructure.utils.GetNumberArray;
import javax.swing.*;
import java.util.Arrays;
/**
* @Author: icanci
* @ProjectName: AlgorithmAndDataStructure
* @PackageName: cn.icanci.datastructure.sort
* @Date: Created in 2020/3/7 10:47
* @ClassAction: 歸并排序
*/
public class MergeSort {
public static void main(String[] args) {
// int[] arr = {8, 4, 5, 7, 1, 3, 6, 2,123,324,546,457,234,1234,534,12,313,1345,346,3};
System.out.println("排序之前");
int[] numberArray = GetNumberArray.getNumberArray(8000000);
int[] temp = new int[numberArray.length];
long start = System.currentTimeMillis();
mergeSort(numberArray, 0, numberArray.length - 1, temp);
System.out.println(System.currentTimeMillis() - start + ":ms");
System.out.println("歸并排序之后");
}
//分+合的方法
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;
//向左遞歸分解
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
//合并
merge(arr,left,mid,right,temp);
}
}
/**
* 合并的方法
*
* @param arr 排序的原始數(shù)組
* @param left 左邊
* @param mid 中間
* @param right 右邊
* @param temp 臨時數(shù)組
*/
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
//初始化 i ,左邊有序序列的索引
int i = left;
//初始化節(jié)點 j 右邊有序序列的初始索引
int j = mid + 1;
//指向 temp的當前索引
int t = 0;
//先把所有的兩邊(有序)的數(shù)據 填充到temp數(shù)組
//知道有一方處理完畢則結束
while (i <= mid && j <= right) {
//繼續(xù)
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t++;
i++;
} else {
temp[t] = arr[j];
t++;
j++;
}
}
//再把剩余數(shù)據的一般的數(shù)據依次填充到temp
while (i <= mid) {
//左邊有剩余 全部填充到temp
temp[t] = arr[i];
t++;
i++;
}
while (j <= right) {
//左邊有剩余 全部填充到temp
temp[t] = arr[j];
t++;
j++;
}
//最有把temp的數(shù)組元素拷貝到arr
//最后一次拷貝
t = 0;
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t++;
tempLeft++;
}
}
}
打印
排序之前
1424:ms
歸并排序之后
