什么是歸并排序？

歸并排序是利用遞歸與分治的技術(shù)將數(shù)據(jù)序列劃分為越來越小的半子表，再對半子表排序，最后再用遞歸方法將排好序的半子表合并成越來越大的有序序列。

核心思想

將兩個(gè)有序的數(shù)列合并成一個(gè)大的有序的序列。通過遞歸，層層合并，即為歸并。

（推薦教程：java快速入門）

實(shí)現(xiàn)代碼：

import java.util.Arrays;  /**  * @author god-jiang  * @date 2020/1/13  */ //歸并排序，時(shí)間復(fù)雜度為O(N*logN)，空間復(fù)雜度為O(N) public class MergeSort {     public static void MergeSort(int[] arr, int start, int end) {         //分治的結(jié)束條件         if (start >= end) {             return;         }         //保證不溢出取start和end的中位數(shù)         int mid = start + ((end - start) >> 1);         //遞歸排序并且合并         MergeSort(arr, start, mid);         MergeSort(arr, mid + 1, end);         Merge(arr, start, mid, end);     }      //合并     public static void Merge(int[] arr, int start, int mid, int end) {         int[] temp = new int[end - start + 1];         int p1 = start;         int p2 = mid + 1;         int p = 0;         while (p1 <= mid && p2 <= end) {             if (arr[p1] > arr[p2]) {                 temp[p++] = arr[p2++];             } else {                 temp[p++] = arr[p1++];             }         }         while (p1 <= mid) {             temp[p++] = arr[p1++];         }         while (p2 <= end) {             temp[p++] = arr[p2++];         }         for (int i = 0; i < temp.length; i++) {             arr[i + start] = temp[i];         }     }      public static void main(String[] args) {         int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};         MergeSort(a, 0, a.length - 1);         System.out.println(Arrays.toString(a));     } }

運(yùn)行結(jié)果：

相關(guān)視頻教程推薦：java視頻教程