本文概述：

• 文章以歸并排序?yàn)轭}，向讀者介紹了其整體思路、時(shí)間復(fù)雜度分析、核心代碼算法思路，并提供了完整實(shí)現(xiàn)代碼(C++ & Java)。

樣例展示：

創(chuàng)新互聯(lián)專注于耿馬企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站,商城建設(shè)。耿馬網(wǎng)站建設(shè)公司,為耿馬等地區(qū)提供建站服務(wù)。全流程按需規(guī)劃網(wǎng)站，專業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務(wù)整體思路：先分治，再合并

• 算法整體上：

  • 將原數(shù)組，以數(shù)組下標(biāo)中點(diǎn)為分界點(diǎn)，一分為二

• 遞歸的每一層：

  • 數(shù)據(jù)來(lái)源：nums[left,right]，分出的兩部分nums[left,mid]，nums[mid + 1,right]

  • 排序操作：遍歷兩部分，按照大小，將其放入臨時(shí)數(shù)組temp[]，注意下標(biāo)從0 開始；

  • 放回操作：將排好序的臨時(shí)數(shù)組元素放回本層原數(shù)組

    • 遍歷的區(qū)間的對(duì)應(yīng)關(guān)系應(yīng)為

      • nums：[left,right]
      • temp：從零開始，因?yàn)樵诿恳粚拥呐判驎r(shí)，temp 都是從0 開始的

時(shí)間復(fù)雜度分析

• 歸并是穩(wěn)定的，在遞歸排序時(shí)，每一趟會(huì)將原數(shù)組劃分為兩份，對(duì)于N 個(gè)數(shù)據(jù)，總計(jì)為logN層；
• 對(duì)每一層，均會(huì)進(jìn)行合并(掃描一遍，每一次會(huì)掃描right - left + 1個(gè)數(shù))，因此總體為N * logN

核心代碼算法思路：一共四步

• 第一步：確定分界點(diǎn)下標(biāo)

  int mid = (left + right) >>1;

• 第二步：向下遞歸，將本層數(shù)據(jù)以分界點(diǎn)為線，一分為二

  merge_sort(nums,left,mid),merge_sort(nums,mid + 1,right);

• 第三步：將由本層分裂出的左右兩部分?jǐn)?shù)組按照大小進(jìn)行合并

  • 注意：第二步是遞歸向下的過(guò)程，此時(shí)遞歸深度不斷加深，第三步是遞歸向上，此時(shí)為遞歸回溯操作

  //開始合并兩個(gè)數(shù)組
  int k = 0,startA = left,startB = mid + 1;
  while(startA<= mid && startB<= right)
  {if(nums[startA]< nums[startB]) temp[k++] = nums[startA++];
      else(temp[k++] = nums[startB++]);
  }
  ?
  while(startA<= mid)    temp[k++] = nums[startA++];
  while(startB<= right)    temp[k++] = nums[startB++];

• 第四步：將本層存放在臨時(shí)數(shù)組中的元素，放回原數(shù)組

  • 注意：此時(shí)，處理的是遞歸中的某一層，且臨時(shí)數(shù)組中保存的數(shù)據(jù)是排好序的；

  • 因此，遍歷的區(qū)間的對(duì)應(yīng)關(guān)系應(yīng)為

    • nums：[left,right]
    • temp：從零開始，因?yàn)樵诿恳粚拥呐判驎r(shí)，temp 都是從0 開始的

  for(int startA = left,startB = 0;startA<= right;startA++,startB++) nums[startA] = temp[startB];

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

#include?
using namespace std;
?
const int N  = 1e6 + 10;
?
int n;
int nums[N], temp[N];
?
void merge_sort(int nums[],int left,int right)
{if(left >= right)   return;//遞歸出口
?
    //本層遞歸邏輯
    int mid = (left + right) >>1;//確定分界點(diǎn)下標(biāo)
    merge_sort(nums,left,mid),merge_sort(nums,mid + 1,right);//向下遞歸
?
    //開始合并兩個(gè)數(shù)組
    int k = 0,startA = left,startB = mid + 1;
    while(startA<= mid && startB<= right)
    {if(nums[startA]< nums[startB]) temp[k++] = nums[startA++];
        else(temp[k++] = nums[startB++]);
    }
?
    while(startA<= mid)    temp[k++] = nums[startA++];
    while(startB<= right)    temp[k++] = nums[startB++];
?
    //將本段區(qū)間的有序結(jié)果放回原數(shù)組
    for(int startA = left,startB = 0;startA<= right;startA++,startB++) nums[startA] = temp[startB];
?
    //for (int i = 0;i< n;i++)   nums[i] = temp[i];注意，放回的是本段區(qū)間[left,right] 不是整個(gè)區(qū)間
?
}
?
int main()
{scanf("%d",&n);
    for(int i = 0;i< n;i++) scanf("%d",&nums[i]);//處理IO
?
    merge_sort(nums,0,n - 1);//進(jìn)行歸并排序
?
    for(int i = 0;i< n;i++)    printf("%d ",nums[i]);
?
}
?
?
?
作者：WAsbry
鏈接：https://www.acwing.com/activity/content/code/content/353277/
來(lái)源：AcWing
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

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

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Scanner;
?
public class MergeSort {?
    //核心函數(shù)：使用歸并排序?qū)o定數(shù)組的指定區(qū)間進(jìn)行升序排序
    public void merge_sort(int[] nums, int left, int right){//遞歸出口
        if (left >= right)  return;
?
        //本層遞歸邏輯
        int mid = (left + right) >>1;//選擇本層遞歸數(shù)組下標(biāo)中點(diǎn)作為分界
        merge_sort(nums,left,mid);
        merge_sort(nums,mid + 1,right);//向下遞歸
?
        //將本層原數(shù)組分裂出的兩部分升序合并在臨時(shí)數(shù)組中
        int startA = left,startB = mid + 1;//確定兩部分起點(diǎn)
        ArrayListtemp = new ArrayList<>();//臨時(shí)集合
?
        while (startA<= mid &&startB<= right){if(nums[startA]< nums[startB]){temp.add(nums[startA++]);
            }else {temp.add(nums[startB++]);
            }
        }
        while (startA<= mid){temp.add(nums[startA++]);
        }
        while (startB<= right){temp.add(nums[startB++]);
        }
?
        //將臨時(shí)數(shù)組中的升序序列放回原數(shù)組
        for(startA = left,startB = 0;startA<= right;startA++,startB++){nums[startA] = temp.get(startB);
        }
    }
?
    //輔助函數(shù)：打印給定數(shù)組所有元素
    public void printArray(int[] nums){for (int i = 0;i< nums.length;i++){System.out.print(nums[i] + " ");
        }
    }
?
    //輔助函數(shù)：根據(jù)鍵盤輸入初始化數(shù)組nums,并返回nums;輸入：1,2,3;返回nums{1,2,3}
    public int[] dealIO(){Scanner sc = new Scanner(new BufferedInputStream(System.in));
        String str = sc.next();
        String[] strArray = str.split(",");
?
        int[] nums = new int[strArray.length];
        for (int i = 0;i< strArray.length;i++){nums[i] = Integer.valueOf(strArray[i]);
        }
?
        return nums;
    }
?
?
    public static void main(String[] args) {MergeSort ma = new MergeSort();
        int[] nums = ma.dealIO();
        ma.merge_sort(nums,0,nums.length - 1);
        ma.printArray(nums);
    }
}
?

運(yùn)行截圖：Java

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：算法基礎(chǔ)之歸并排序-創(chuàng)新互聯(lián)
分享路徑：http://weahome.cn/article/jsegc.html