1 归并排序（升序或降序只需在左右侧比较时修改即可）
求数组左侧有序和右侧有序，然后合并左侧和右侧完成排序。
对于数组a={1,4,2,5,3}，mid=0+(4-0)/2=2,
第一步：从a的下标i=2处将a分为：左侧{1，4，2}和右侧{5，3}；
第二步：计算左侧的mid，将左侧{1，4，2}分为：左侧{1，4}和右侧{2}；
第三步：计算左侧的mid,将左侧{1，4}分为：左侧{1}右侧{4}；
第四步：当不能进行分割时开始比较当前的左侧和右侧值进行排序，倒着执行到第一步完成数组a左侧的排序{1，2，4}；
第五步：对数组a的右侧进行上述步骤，完成右侧排序{3，5}；
最后：合并左侧{1，2，4}和右侧{3，5}，合并时若左侧a[i]<右侧a[j],先拷贝a[i]，此为升序，若为降序则相反。 7-99999999999999
如图：
2 完整代码如下：
#include<iostream>
using namespace std;
//1.归并排序，利用递归，先将两侧排好序，再进行合并
//比较相邻序列
void merge(int arr[], int temp[], int start,int mid, int end)
{
cout << "(start,mid,end)=" << "(" << start << "," << mid << "," << end << ")" << endl;
int i = start, j = mid + 1, k = start;
//将较小值放入temp
while (i != mid+1 && j != end+1)
{
if (arr[i] <arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
//将多的数放到temp末尾
while (i!= mid + 1)
{
temp[k++] = arr[i++];
}
while (j != end + 1)
{
temp[k++] = arr[j++];
}
//更新序列
for (int i = start; i <= end; i++)
{
arr[i] = temp[i];
cout << arr[i] << " ";
}
cout << endl;
}
//排序
void merge_sort(int arr[], int temp[], int start, int end)
{
int mid = 0;
if (start < end)
{
mid = start + (end - start) / 2;
//递归调用
merge_sort(arr, temp, start, mid);
merge_sort(arr, temp, mid + 1, end);
merge(arr, temp, start, mid, end);
}
}
int main()
{
int a[5] = {1,4,2,5,3};
int t[5];
merge_sort(a, t, 0, 4);
for (int i = 0; i < 5; i++)
{
cout << a[i] << " ";
}
cout << endl;
system("pause");
system("cls");
return 0;
}
3 小和问题
问题描述：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和
以上述中a={1,4,2,5,3}为例：记小和为：res=0
（1)1左边比1小的数为0（1左边没有数字），res=0+0;
（2)4左边比4小的数为1, res=0+1
（3)2左边比2小的数为1, res=0+1+1
（4)5左边比5小的数为1,4,2, res=0+1+1+1+4+2
（5)3左边比3小的数为1,2, res=0+1+1+1+4+2+1+2=12
从上述可以得出比1的右侧比1大的数的个数为4，比4大的个数为1，比2大的数的个数为2，比5大的数的个数为0，比3大的数的个数为0
小和 res=1*4 + 4*1 + 2*2 + 5*0 + 3*0=12
因此小和问题只需在归并排序过程中记录比当前数a[i]大的数的个数 num res+=a[i]*num
注意：当左侧数等于右侧数，即：a[i]==a[j] 时应先拷贝右侧数,即 :temp=a[j]，否则统计不出比当前数字大的数的个数.
4 小和详细代码：
#include<iostream>
using namespace std;
/*
小和问题描述：
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和
*/
//分段排序
int merge(int arr[], int temp[], int start, int mid, int end)
{
cout << "(start,mid,end)=" << "(" << start << "," << mid << "," << end << ")" << endl;
int i = start, j = mid+1, k = start;
int res = 0;
while(i != mid + 1 && j != end + 1)
{
//若左侧等于右侧先拷贝右侧，否则算不出比当前数大的数的个数
if (arr[i] == arr[j])
{
temp[k++] = arr[j++];
}
else if (arr[i] < arr[j]) //注意此处不要写为arr[i++]<arr[j++]
{
res += (end - j + 1) * arr[i]; //num=end-j+1为比当前数a[i]大的数的个数
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
//将多余的数放到temp末尾
while (i != mid + 1)
{
temp[k++] = arr[i++];
}
while (j != end + 1)
{
temp[k++] = arr[j++];
}
//更新a[]
for (int i=start;i<= end;i++)
{
arr[i] = temp[i];
cout << arr[i] << " ";
}
cout << endl;
return res;
}
//递归排序
int merge_sort(int arr[], int temp[], int start, int end)
{
int mid = 0;
if (start == end) //此时不记录小和
{
return 0;
}
mid = start + (end - start) / 2;
//递归调用
return merge_sort(arr,temp,start,mid)
+merge_sort(arr, temp, mid + 1, end)
+merge(arr, temp, start, mid, end);
}
int main()
{
//准备数组{ 2, 3, 4, 1, 2, 3, 8, 9, 0 }；小和=5*2+3*3+2*4+4*1+3*2+2*3+1*8=
int a[5] = { 1,4,2,5,3 };
int t[5];
int Sum = 1 * 4 + 4 * 1 + 2 * 2 + 5 * 0 + 3 * 0;
int sum=merge_sort(a, t, 0, 4);
cout << "a=";
for (int i = 0; i < 5; i++)
{
cout << a[i] << ",";
}
cout << endl;
cout << "验证Sum=" << Sum << endl;
cout << "小和sum=" << sum << endl;
return 0;
}
结果：
这是作者的学习笔记，在此分享，仅供参考。因为作者水平有限，如有疏漏之处，还望批评指正。