基本思想

歸并排序是由遞歸實現的，主要是分而治之的思想，也就是通過將問題分解成多個容易求解的局部性小問題來解開原本的問題的技巧。

歸并排序在合并兩個已排序數組時，如果遇到了相同的元素，只要保證前半部分數組優先于后半部分數組， 相同元素的順序就不會顛倒。所以歸并排序屬于穩定的排序算法。

每次分別排左半邊和右半邊，不斷遞歸調用自己，直到只有一個元素遞歸結束，開始回溯，調用 merge 函數，合并兩個有序序列，再合并的時候每次給末尾追上一個最大 int 這樣就不怕最后一位的數字不會被排序。

歸并排序的效率是比較高的，設數列長為N，將數列分開成小數列一共要logN步，每步都是一個合并有序數列的過程，時間復雜度可以記為O(N)，故一共為O(N log N)。因為歸并排序每次都是在相鄰的數據中進行操作，所以歸并排序在O(N*logN)的幾種排序方法（快速排序，歸并排序，希爾排序，堆排序）也是效率比較高的。

排序過程

?

算法流程：

1、將一個數組拆分為兩個，從中間點拆開，通過遞歸操作來實現一層一層拆分。

2、從左右數組中選擇小的元素放入到臨時空間，并移動下標到下一位置。

3、重復步驟2直到某一下標達到尾部。

4、將另一序列剩下的所有元素依次放入臨時空間。

5、將臨時空間的數據依次放入原數據數組。

基礎代碼

package Sort; //針對 一個數組 左右兩部分已經排好序 public class 歸并排序基礎 {public static void main(String[] args) {int[] arr = {1,4,7,8,3,6,9};merge(arr);} // 把數組arr = {1,4,7,8,3,6,9} 分成兩部分 分別為1,4,7,8 和 3,6,9static void merge(int[] arr) {int mid = arr.length / 2;int[] temp = new int[arr.length];int i = 0; //i是數組arr前部分的第一位int j = mid+1; //j是數組arr后部分的第一位int k = 0; //k是 新數組temp的第一位//當 arr數組兩邊都還有數 時while (i <= mid && j < arr.length) {if (arr[i] <= arr[j]) {temp[k] = arr[i];i++;k++;} else {temp[k] = arr[j];j++;k++;}}//將右邊剩余的歸并while (i <= mid) {temp[k++] = arr[i++];}//將左邊剩余的歸并while (j < arr.length) {temp[k++] = arr[j++];}print(temp);}//排序static void swap(int[] arr,int i,int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}//打印static void print(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}} }

加入歸并的代碼

package Sort;public class 歸并排序遞歸 {public static void main(String[] args) { // int[] arr = {1,4,7,8,3,6,9};int[] arr = {3,0,6,4,1,3,7,8,5,9};sort(arr,0,arr.length-1);print(arr);}public static void sort(int[] arr,int left,int right) {if (left == right) {return;}//分成兩半int mid = left +(right-left)/2;//左邊排序sort(arr, left, mid);//右邊排序sort(arr, mid +1, right);merge(arr, left, mid+1, right);}//leftPtr 指數組最左邊//rightPtr 指數組中間//rightBound 數組最右邊static void merge(int[] arr,int leftPtr,int rightPtr,int rightBound) {int mid = rightPtr - 1; int[] temp = new int[rightBound - leftPtr + 1];int i = leftPtr; int j = rightPtr; int k = 0; while (i <= mid && j <= rightBound) {if (arr[i] <= arr[j]) {temp[k] = arr[i];i++;k++;} else {temp[k] = arr[j];j++;k++;}}// 將右邊剩余的歸并while (i <= mid) {temp[k++] = arr[i++];}//將左邊剩余的歸并while (j <= rightBound) {temp[k++] = arr[j++];}for(int m = 0; m < temp.length;m++) arr[leftPtr+m] = temp[m];}//排序static void swap(int[] arr,int i,int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}//打印static void print(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}} }

總結

以上是生活随笔為你收集整理的归并排序算法（java实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。