目錄
前言
學習目標：
學習內(nèi)容：
一、介紹歸并排序
1.1 歸并排序的思路
1.2 歸并排序的代碼
1.2.1 mergesort函數(shù)部分?
1.2.2 process函數(shù)部分?
1.2.3 merge函數(shù)部分?
二、AC兩道經(jīng)典的OJ題目
題目一：逆序?qū)栴}
題目二：小和問題?
三、練習一道LeetCode的題目
四、總結(jié)在什么情況下使用歸并排序的算法
學習產(chǎn)出：
前言
??作者簡介： 加油，旭杏，目前大二，正在學習C++，數(shù)據(jù)結(jié)構(gòu)等??
??作者主頁：加油，旭杏的主頁???本文收錄在：再識C進階的專欄??
??代碼倉庫：旭日東升 1??
??歡迎大家點贊 ?? 收藏 ? 加關注哦！????
學習目標：
???????在這一篇博客中，我們要學習排序算法中比較重要的三個排序中的其中一個，就是歸并排序，并學會使用代碼進行編寫歸并排序，之后能夠AC兩道經(jīng)典的OJ題目，最后是刷幾道LeetCode的題目，這就是本博客的學習目標！
學習內(nèi)容：
通過上面的學習目標，我們可以列出要學習的內(nèi)容：
- 學習歸并排序的思想
- 使用代碼進行編寫歸并排序
- AC兩道經(jīng)典的OJ題目
- 練習幾道LeetCode的題目
- 總結(jié)在什么情況下使用歸并排序的算法
一、介紹歸并排序
???????在之前的學習中，我們可能或多或少的接觸過排序算法，也知道一些排序算法：冒泡排序、選擇排序、插入排序等。不過這些排序有共同點——時間復雜度為O(N * N)，時間上不是那么有效，我們需要進行進一步的優(yōu)化，從而就有了我們這一篇博客講述的歸并排序，其時間復雜度為：O(N * logN)，空間復雜度為：O(N)。
1.1 歸并排序的思路
???????歸并排序，顧名思義，“歸并”的含義是將兩個或兩個以上的有序表合并為一個新的有序表。假設待排序數(shù)表有N個記錄，則可將其視為N個有序的子表，每一個子表的長度是1，然后兩兩歸并，得到[ N / 2 ]個長度為2或1的有序表；繼續(xù)兩兩歸并……如此重復，直到合并成一個長度為N有序表為止。下面小編將畫圖帶大家理解：
???????而這個排序剛開始有點像這個相反的做法，其思路是：先將這一大長串數(shù)組分割，因為其是一個遞歸的過程，就是將數(shù)組一直分割，直到每一個數(shù)組長度為1，此時每一個數(shù)組都是有序的；之后要開始合并數(shù)組，合并數(shù)組時將進行比較，看需要來判斷是升序或降序，合并的時候就如同上方的合并一樣，最后能夠得出一個有序的數(shù)組。
1.2 歸并排序的代碼
這個算法有三個部分組成，請看下面我一一為大家進行講解：
1.2.1 mergesort函數(shù)部分?
void mergesort(int arr[], int left, int right)
{
int sz = right - left + 1; //計算數(shù)組的長度
if(arr == NULL || sz < 2) //如果數(shù)組的首元素不存在，則不用排序；
return ; //如果數(shù)組的長度只有一個，則也不用排序
process(arr, left, right); //進入process函數(shù)部分
}1.2.2 process函數(shù)部分?
void process(int arr[], int left, int right)
{
int sz = right - left + 1; //與mergesort函數(shù)的部分作用是一樣的
if(arr == NULL || sz < 2)
return ;
//分割數(shù)組
int mid = left + ((right - left) >> 1); //計算出這段數(shù)組中正中心的位置坐標
process(arr, left, mid); //遞歸過程中，將數(shù)組分為左右部分，這是左部分
process(arr, mid + 1, right);//這是右部分
merge(arr, left, mid, right);
}1.2.3 merge函數(shù)部分?
void merge(int arr[], int left, int mid, int right)
{
int sz = right - left + 1;
int* help = (int*)malloc(sizeof(int) * sz); //構(gòu)造輔助數(shù)組
int i = 0;
int p1 = left; //建立指針
int p2 = mid + 1;
while(p1 <= mid && p2 <= right) //如果左指針與右指針都不越界，則進入循環(huán)
{
help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++]; //進行比較，交換數(shù)據(jù)
}
while(p1 <= mid) //將左邊剩余的數(shù)據(jù)拷貝到輔助數(shù)組中
{
help[i++] = arr[p1++];
}
while(p2 <= right) //將右邊剩余的數(shù)據(jù)拷貝到輔助數(shù)組中
{
help[i++] = arr[p2++];
}
for(int i = 0; i < sz; i++) //最后將輔助數(shù)組中的數(shù)據(jù)轉(zhuǎn)移到原數(shù)組中
{
arr[left + i] = help[i];
}
}二、AC兩道經(jīng)典的OJ題目
題目一：逆序?qū)栴}
題目：
???????在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)?。輸入一個數(shù)組，求出這個數(shù)組中的逆序?qū)Φ目倲?shù)。
思路：
???????在這道題中，我們要注意題目中標紅的描述，這個逆序?qū)τ肋h都是前一個數(shù)字的坐標位置永遠小于后一個數(shù)字的坐標位置。這一點就和歸并排序不謀而合，歸并排序算法總是將左邊的數(shù)字與右邊的數(shù)字進行比較，然后進行排序。而這道題要求的是逆序?qū)Φ膫€數(shù)，我們可以在進行比較的時候進行計數(shù)，這就是大致思路。
???????將這個數(shù)組進行降序排序還是逆序排序呢？如果是降序排序時，我們將左邊有右邊進行比較，如果左邊大于右邊，則大于右邊所有的數(shù)字，進行計數(shù)即可；如果是升序排序可能會出現(xiàn)漏項的情況，自然排除升序，采用降序。
代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-712983.html
int merge(int arr[], int left, int mid, int right) { int sz = right - left + 1; int* help = (int*)malloc(sizeof(int) * sz); int p1 = left; int p2 = mid + 1; int i = 0; int ret = 0; while(p1 <= mid && p2 <= right) { ret += arr[p1]>arr[p2]?(right - p2 + 1):0; //如果左邊的數(shù)字大于右邊的數(shù)字，則計算右邊 //一共有多少數(shù)字 help[i++] = arr[p1] > arr[p2]?arr[p1++]:arr[p2++]; } while(p1 <= mid) { help[i++] = arr[p1++]; } while(p2 <= right) { help[i++] = arr[p2++]; } for(int i = 0; i < sz; i++) { arr[left + i] = help[i]; } return ret; } int process(int arr[], int left, int right) { int sz = right - left + 1; if(arr == NULL || sz < 2) return 0; int mid = left + ((right - left) >> 1); return process(arr, left, mid) + process(arr, mid + 1, right) + merge(arr, left, mid, right); } int revOrder(int arr[], int left, int right) { int sz = right - left + 1; if(arr == NULL || sz < 2) return 0; return process(arr, left, right); } int reversePairs(int* nums, int numsSize){ int left = 0; int right = numsSize - 1; int ans = revOrder(nums, left, right); return ans; }
題目二：小和問題?
題目：
???????在一個數(shù)組中，每一個數(shù)左邊比當前的數(shù)小進行累加起來，叫做這個數(shù)組的小和，求一個數(shù)組的小和。
思路：
???????同理，看題目中被標紅的描述，進行降序排序，如果左邊的數(shù)字小于右邊的數(shù)字，則將左邊的數(shù)字乘右邊有多少個大于他的個數(shù)，進行累加即可。
代碼：
int merge(int arr[], int left, int mid, int right) { int sz = right - left + 1; int* help = (int*)malloc(sizeof(int) * sz); int i = 0; int p1 = left; int p2 = mid + 1; int count = 0; while (p1 <= mid && p2 <= right) { count += arr[p1] < arr[p2] ? (right - p2 + 1)*arr[p1] : 0; help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]; } while (p1 <= mid) { help[i++] = arr[p1++]; } while (p2 <= right) { help[i++] = arr[p2++]; } for (int i = 0; i < sz; i++) { arr[left + i] = help[i]; } return count; } int process(int arr[], int left, int right) { int sz = right - left + 1; if (arr == NULL || sz < 2) return 0; int mid = left + ((right - left) >> 1); return process(arr, left, mid) + process(arr, mid + 1, right) + merge(arr, left, mid, right); } int reverseOrder(int arr[], int left, int right) { int sz = right - left + 1; if (arr == NULL || sz < 2) return 0; return process(arr, left, right); } int main() { int arr[] = { 1,3,4,2,5 }; int sz = sizeof(arr) / sizeof(arr[0]); int left = 0; int right = sz - 1; int ans = reverseOrder(arr, left, right); printf("%d\n", ans); return 0; }
三、練習一道LeetCode的題目
題目：
???????給定一個數(shù)組?
nums?，如果?i < j?且?nums[i] > 2*nums[j]?我們就將?(i, j)?稱作一個重要翻轉(zhuǎn)對。你需要返回給定數(shù)組中的重要翻轉(zhuǎn)對的數(shù)量。思路：
???????前面的操作基本一樣，只需將merge函數(shù)部分進行修改即可，將左邊的指針不動，一一右邊的數(shù)字進行比較，如果條件成立，就將指針向右移動一位，如果不成立跳出，結(jié)果加上右指針減去初始位置的個數(shù)。
代碼：
int process(int arr[], int left, int right) { int sz = right - left + 1; if(arr == NULL || sz < 2) return 0; int mid = left + ((right - left) >> 1); int n1 = process(arr, left, mid); int n2 = process(arr, mid + 1, right); int ret = n1 + n2; int p1 = left; int p2 = mid + 1; int i = 0; while(p1 <= mid) { while(p2 <= right && (long long)arr[p1]>2*(long long)arr[p2]) p2++; ret += (p2 - mid - 1); p1++; } p1 = left; p2 = mid + 1; int* help = (int*)malloc(sizeof(int) * sz); while(p1 <= mid && p2 <= right) { help[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++]; } while(p1 <= mid) { help[i++] = arr[p1++]; } while(p2 <= right) { help[i++] = arr[p2++]; } for(int i = 0; i < sz; ++i) { arr[left + i] = help[i]; } return ret; } int mergeSort(int arr[], int left, int right) { int sz = right - left + 1; if(arr == NULL || sz < 2) return 0; return process(arr, left, right); } int reversePairs(int* nums, int numsSize){ int left = 0; int right = numsSize - 1; return mergeSort(nums, left, right); }
四、總結(jié)在什么情況下使用歸并排序的算法
???????小編覺得在數(shù)組對問題可能使用歸并排序，尤其是一個數(shù)組對中滿足一定條件，左邊的左邊小于右邊的坐標時，可以考慮考慮歸并排序算法的思想。文章來源地址http://www.zghlxwxcb.cn/news/detail-712983.html
學習產(chǎn)出：
- 學習歸并排序的思想
- 使用代碼進行編寫歸并排序
- AC兩道經(jīng)典的OJ題目
- 練習幾道LeetCode的題目
- 總結(jié)在什么情況下使用歸并排序的算法
到了這里，關于【初階算法4】——歸并排序的詳解，及其歸并排序的擴展的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
![①歸并排序、快速排序 、堆排序、計數(shù)排序[算法、代碼模板、面試題]](https://imgs.yssmx.com/Uploads/2024/02/767138-1.png)
![[排序算法]:歸并排序(Merge Sort)(遞歸與非遞歸實現(xiàn)詳解)](https://imgs.yssmx.com/Uploads/2024/01/807941-1.png)
