【原】排序算法 --- 歸并排序

貪挽懶月 2022-06-20 發(fā)布于廣東

展開全文

一、排序思想

歸并排序是采用分治算法，即將一個(gè)大問題切分成一些小問題然后遞歸求解。歸并排序的圖解如下：

分的過程簡(jiǎn)單，就是將數(shù)組拆開來，拆到每組只有一個(gè)元素為止。治的過程是怎么排序的呢？以最后一次治為例，即將4 5 7 8和1 2 3 6合并成最終的有序序列為例，看看如何實(shí)現(xiàn)。

首先創(chuàng)建一個(gè)新的數(shù)組tempArr，長(zhǎng)度為要進(jìn)行“治”的兩個(gè)數(shù)組長(zhǎng)度之和；
然后用i指向4，即第一個(gè)數(shù)組的最左邊，j指向1，即第二個(gè)數(shù)組的最左邊；
發(fā)現(xiàn)4比1大，那么就將1存入tempArr，同時(shí)指針j后移；
繼續(xù)比較指針i和j所指元素的大小，發(fā)現(xiàn)2比4小，將2存入tempArr，同時(shí)j繼續(xù)后移；
繼續(xù)比較，將3存入tempArr，j繼續(xù)后移；
此時(shí)發(fā)現(xiàn)6比4大，就將4存入tempArr，同時(shí)i后移；
5比6小，將5存入tempArr，i繼續(xù)后移；
7比6大，將6存入tempArr，此時(shí)j已經(jīng)處于最后了，不能后移了；
接著就將i所指的剩余元素都存入tempArr，這個(gè)tempArr就是有序的了。

二、代碼實(shí)現(xiàn)

1. 第一種方式：

這種方式很容易懂，我們先不是要拆分?jǐn)?shù)組嗎？那就拆唄，拆到什么時(shí)候?yàn)橹鼓?？拆出來的?shù)組只有一個(gè)元素了那就不用拆了。

拆分：

public static int[] sort(int[] arr) {
 if (arr == null || arr.length == 1) {
  return arr;
 }
 // 拆分?jǐn)?shù)組
 int mid = arr.length / 2; // 中間指針，利用該指針將數(shù)組拆分
 int[] left = Arrays.copyOfRange(arr, 0, mid);
 int[] right = Arrays.copyOfRange(arr, mid, arr.length);
 // 調(diào)用合并方法，因?yàn)閘eft和right可能可以再拆分，所以傳進(jìn)去的left和right再遞歸調(diào)用當(dāng)前方法
 return merge(sort(left), sort(right));
}

合并：該方法傳入兩個(gè)數(shù)組，對(duì)數(shù)組進(jìn)行合并上面已經(jīng)講了思路，按照思路來寫就好了：

public static int[] merge(int[] left, int[] right) {
 // 定義臨時(shí)數(shù)組
 int[] tempArr = new int[left.length + right.length];
 // 定義兩個(gè)指針
 int i = 0; // left的指針
 int j = 0; // right的指針
 // 進(jìn)行合并操作
 for(int index=0; index < tempArr.length; index ++) {
  // 如果left的遍歷完了，那么將right中的剩余元素全部依次放入tempArr中
  if (i >= left.length) {
   tempArr[index] = right[j];
   j++; // 指針后移
  } else if(j >= right.length) {
   // 如果right遍歷完了，那么將left中剩余的元素全部依次放入tempArr中
   tempArr[index] = left[i];
   i++; // 指針后移
  } else if (left[i] < right[j]) {
   // 如果i所指的數(shù)更小，就將該數(shù)存入tempArr
   tempArr[index] = left[i];
   i++; // 指針后移
  } else {
   // 如果j所指的數(shù)大于等于i所指的數(shù)，就將j所指的數(shù)存入tempArr
   tempArr[index] = right[j];
   j++; // 指針后移
  }
 }
 return tempArr;
}

沒錯(cuò)，這樣就搞定了，這就是完全按照上面案例分析來做的，不過缺點(diǎn)就是，拆分的時(shí)候，是真正的拆除兩個(gè)數(shù)組來了，會(huì)浪費(fèi)空間，優(yōu)點(diǎn)就是容易理解。

2. 第二種方式：

第二種方式就是不真正的將數(shù)組拆成兩部分，而是通過一個(gè)中間索引mid，將數(shù)組標(biāo)識(shí)成兩部分。這樣就不需要真正的拆分，不會(huì)浪費(fèi)空間，但是代碼相對(duì)來說更難理解。

合并：先看合并部分，除了原始數(shù)組外，還有三個(gè)參數(shù)，left和mid構(gòu)成左邊的數(shù)組，mid+1和right構(gòu)成右邊的數(shù)組，只要理解了這一點(diǎn)，下面的代碼就容易理解了。

public static void merge(int[] arr, int left, int mid, int right) {
 // 定義臨時(shí)數(shù)組
 int[] tempArr = new int[right - left + 1]; 
 int i = left; // 左邊數(shù)組的指針
 int j = mid + 1; // 右邊數(shù)組的指針
 int k = 0; // 臨時(shí)數(shù)組的指針
 // 當(dāng)左邊數(shù)組和右邊數(shù)組都還沒遍歷完的時(shí)候
 while(i <= mid && j <= right) {
  // 如果i所指的元素更小，就其放入tempArr，同時(shí)i后移
  if (arr[i] <= arr[j]) {
   tempArr[k++] = arr[i++];
  } else {
   // 如果j所指的更小，就將其放入tempArr，同時(shí)j后移
   tempArr[k++] = arr[j++];
  }
 }
 // 如果左邊的數(shù)組還沒遍歷完，就將左邊數(shù)組剩余元素依次放入tempArr中
 while (i <= mid) {
  tempArr[k++] = arr[i++];
 }
 // 如果右邊的數(shù)組還沒遍歷完，就將右邊數(shù)組剩余元素依次放入tempArr中
 while (j <= right) {
  tempArr[k++] = arr[j++];
 }
 // 將tempArr中排好序的添加到原數(shù)組中
 for(int x=0; x<tempArr.length; x++) {
  arr[left + x] = tempArr[x];
 }
}

拆分：拆分到什么時(shí)候?yàn)橹鼓?，如?code style="font-size: 14px;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(71, 193, 168);">left和right相等了，表示只有一個(gè)元素，那就不用拆了，否則就對(duì)左邊和右邊的都進(jìn)行遞歸拆分，拆到不可再拆就合并。

public static void sort(int[] arr, int left, int right) {
 // 如果左指針和右指針相等，表示只有一個(gè)元素，那就不需要拆分了
 if (left == right) {
  return;
 }
 // 否則就進(jìn)行拆分
 int mid = left + (right - left) / 2; // 找到中間值進(jìn)行拆分
 // 對(duì)左邊再進(jìn)行拆分
 sort(arr, left, mid);
 // 對(duì)右邊再進(jìn)行拆分
 sort(arr, mid+1, right);
 // 進(jìn)行合并
 merge(arr, left, mid, right);
}