再談歸并排序
在我以前的資料結構專欄中已經對歸并排序做了介紹，這里我們開始先復習一下歸并排序的思路與代碼
歸并排序用到了分治的思想，將陣列不斷細分成小的幾個區間，將每個區間排成有序后，再將大區間排為有序
代碼實作：（非遞回實作）
void _MergeSort(vector<int>&arr,int l,int m,int r);//歸并操作的函式
void MergeSort(vector<int>&arr)
{
int n=arr.size();
int gap=1;//每次歸并的小區間
while(gap<n)
{
int l=0;
while(l<n)
{
int m=l+gap-1;//左區間的末尾
if(m>=n)
{
break;//左區間不存在（沒有對應的右區間），直接不進行歸并
}
int r=min(n-1,m+gap);//判斷右區間是否越界，右區間不夠其實可以繼續歸并
_MergeSort(arr,l,m,r);//進行歸并操作的函式
l=r+1;//歸并完后繼續更新下一個區間
}
if(gap>n/2)
{
break;//防止溢位
}
gap<<=1;//每次將gap*2，擴大區間
}
}
void _MergeSort(vector<int>&arr,int l,int m,int r)
{
int help=(int*)malloc(sizeof(int)*(r-l+1));//歸并輔助陣列
int p1=l;
int p2=m+1;
while (p1 <= m && p2 <= r)
{
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m)
{
help[i++] = arr[p1++];
}
while (p2 <= r)
{
help[i++] = arr[p2++];
}
for (i = 0; i < (r - l + 1); i++)
{
arr[l + i] = help[i];
}
free(help);
}
小和問題
問題描述
有一個陣列arr，設有一個指標i指向某一個元素，將i左邊所有比i小的數字加起來求和，將i遍歷整個陣列求出最終答案
圖例
思路
我們可以直接用暴力的方法，用兩個指標遍歷來找小數，當然，不是不可以，但是復雜度是O(n2)我們一般不考慮，下面介紹一種轉化方法
我們可以把問題轉化為求右邊有多少個數比i大
比如在上面這個陣列
1比2,3，4都大，所以2,3，4在算的時候一定會加一個1，所以我們可以在遍歷1的時候加上1*右邊有多少個數比1大
但是我們拿到的陣列不一定有序，就像這樣
[2,3,5,4,6,8,9,7];
所以我們需要排序來完成，因為排序完再算復雜度較高，所以我們可以邊排序邊計算
在歸并的時候可以一個區間區間的計算
在歸并到右區間的時候不計算的，歸并左區間時計算右區間有多少數比它大，答案加上右區間長度*這個數本身
相等時歸并右區間：相等歸并左區間右區間究竟大還是小不清楚
代碼實作
int Process1(vector<int>& arr, int l, int m, int r)
{
int ans = 0;
int* help = (int*)malloc(sizeof(int) * (r - l + 1));
int i = 0;
int p1 = l;
int p2 = m + 1;
while (p1 <= m && p2 <= r) {
ans += arr[p1] < arr[p2] ? (arr[p1] * (r - p2 + 1)) : 0;//對答案進行操作
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < (r - l + 1); i++) {
arr[l + i] = help[i];
}
free(help);
return ans;
}
int smallSum(vector<int>& arr,int l,int r)
{
if (l == r)
{
return 0;
}
int mid = l + ((r - l) >> 1);
return smallSum(arr, l, mid) + smallSum(arr, mid + 1, r) + Process1(arr, l, mid, r);//process是歸并函式
}
逆序對問題
我們把(x,y)二元組叫做一個對，逆序對滿足右邊的數字比左邊小
給你一個陣列，判斷它有多少個逆序對
思路求解
與上一題差不多，但這題我們從右往左歸并，我們轉化為數右區間有多少個數比左區間小即可
如果從左往右歸并的話，我們就不能確定右區間比左區間大了，也不能確定有序
int Process2(vector<int>& arr, int l, int m, int r)
{
int ans = 0;
int* help = (int*)malloc(sizeof(int) * (r - l + 1));
int i = (r - l + 1) - 1;
int p1 = m;
int p2 = r;
while (p1 >= l && p2 > m) {
ans += arr[p1] > arr[p2] ? (p2 - m) : 0;
help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
}
while (p1 >= l) {
help[i--] = arr[p1--];
}
while (p2 > m) {
help[i--] = arr[p2--];
}
for (i = 0; i < (r - l + 1); i++) {
arr[l + i] = help[i];
}
free(help);
return ans;
}
int reverPairNumber(vector<int>& arr, int l, int r)
{
if (l == r)
{
return 0;
}
int mid = l + ((r - l) >> 1);
return reverPairNumber(arr, l, mid) + reverPairNumber(arr, mid + 1, r) + Process2(arr, l, mid, r);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/413418.html
標籤：java