版权声明:本文为博主原创文章,转载请注明博客地址: https://cloud.tencent.com/developer/article/1433359
分治法不仅仅是应用于计算机学科,还涉及到了各行各业。分治意为分而治之。即就是将原问题分解为规模更小的,但是形式上与原问题相同的子问题来解决。对于较小的问题求解起来也是比较容易的,在有必要的时候,可以将子问题的解进行合并以得到原问题的解。
归并排序就是分治思想的一种体现,归并排序的操作如下,假设给定一个数组num,需要对它排序,首先将数组分成两半部分,对这两半部分分别进行归并排序。最后将两个排好序的子序列进行合并,就可以得到排序以后的结果。使用伪代码描述如下:
//伪代码描述
type temp[n]; //这可能是该算法唯一不足的地方,就是它的空间复杂度是O(N)
MergeSort(type num[n],int start,int end)//排序算法
{
int mid = (start + end) / 2; //中间位置
MergeSort(num[n],start,mid); //对前半部分子序列进行归并排序
MergeSort(num[n],mid+1,end); //对后半部分子序列进行归并排序
Merge(num,start,mid,end,temp); //这一步进行合并操作
}
Merge(num,start,mid,end,temp)//合并操作
{
i = start,j = mid + 1, k = start;
//这里使用的办法可以称之为“双指针法”。在这里分别是i和j。它们分别指向了待合并的两个子序列的
//第一个元素,然后比较这两个元素的大小(我在这里排序的结果是从小到大的),将小的那个元素放到
//备用数组中。然后被复制的那个数组的指针后移,继续比较,直到某一子序列全部比较完毕。
while(i < mid && j < end)
{
if (num[i] <= num[j]) temp[k++] = num[i++];
else temp[k++] = num[j++];
}
//将未处理的剩余元素,直接复制到备用数组temp中。
if(i < mid) copy temp[k++] = num[i++];
else copy temp[k++] = num[j++];
}
以上就是算法的描述,我们来看一张图解分析。
这张图描述了对一个数组使用归并排序的具体过程。归并排序的C/C++实现代码如下:
#include <iostream>
int num[10] = { 2,3,1,5,7,6,8,0,9,4 }; //待排序数组
int temp[10]; //备用数组
using std::cout;
void MergeSort(int *num, int start, int end);
void Merge(int * num, int start, int mid, int end);
int main()
{
MergeSort(num, 0, 9);
for (int i = 0; i < 10; i++)
{
cout << num[i] << std::endl;
}
system("pause");
}
void MergeSort(int * num, int start, int end)
{
int mid = (start + end) / 2;
if (start < end)
{
MergeSort(num, start, mid);
MergeSort(num, mid + 1, end);
Merge(num, start, mid, end);
}
}
void Merge(int * num, int start, int mid, int end)
{
int i, j, k;
i = start;
j = mid + 1;
for (k = start; i <= mid && j <= end ; k++)
{
if (num[i] <= num[j])
{
temp[k] = num[i++];
}
else
{
temp[k] = num[j++];
}
}
while (i <= mid)
{
temp[k++] = num[i++];
}
while (j <= end)
{
temp[k++] = num[j++];
}
for (int i = start; i <= end; i++) //将temp中的数据拷贝回num中
{
num[i] = temp[i];
}
}
快速排序也是分治法的一个典型代表。快速排序是使得下标s之前的元素都比nums小,在s之后元素都比nums大。这样我们把nums的位置就确定下来了,然后对nums之前的元素进行快速排序,也对nums之后的元素快速进行排序。这样就把一个序列的顺序排好了。在这里我们的初始s = 0.代码如下:
#include <iostream>
void QuickSort(int *num,int start,int end);
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
int main()
{
int num[10] = { 2, 4, 1, 3, 5, 9, 0, 6, 7, 8 };
QuickSort(num, 0, 9);
for (int i = 0; i < 10; i++)
{
std::cout << num[i] << std::endl;
}
system("pause");
}
void QuickSort(int * num, int start, int end)
{
if (start >= end)
{
return;
}
int k = num[start]; //代码这里实际是用k表示的
int i = start;
int j = end;
while (i != j)
{
while (j > i && k <= num[j]) //偶数次的时候移动j.
{
j--;
}
swap(num[i], num[j]);
while (i < j && k >= num[i]) //奇数次的时候移动i.
{
i++;
}
swap(num[i], num[j]);
}
QuickSort(num, start, i - 1);
QuickSort(num, i + 1, end);
}
在快速排序中,s的选择是非常重要的,选择的好,则快速排序的时间复杂度将会是O(nlogn);选择的不好,将会是O(n²)。在上面选择初始s = 0的情况下,如果将要排序的序列是有序的,那么时间复杂度就会是O(n²)。关于s的选择策略有很多,其中较为简单的一种是选择第一个元素,中间元素,最后一个元素这三者的中值作为nums。
例:给定一个序列,输出它的前m的大的数,要求从大到小输出。
简单点的解法就是先给序列排序,然后输出。这样做的时间复杂度是O(nlongn);我们把这个问题分而治之,只给前m大的数排序,然后输出。我们在找前m大的数的时候,必须在O(n)内找到。这样时间复杂度就是O(n+mlogm)。当m不是非常接近n的时候,该时间复杂度接近O(n)。
#include <iostream>
using std::cout;
using std::cin;
void Mfun(int *num, int m, int start, int end);
void QuickSort(int * num, int start, int end);
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
int count = 0;
int main()
{
int num[10] = { 3,4,2,1,5,6,0,8,7,9 };
int m;
cout << "请输入m:";
cin >> m;
Mfun(num, m, 0, 9);
QuickSort(num, 10 - m, 9);
for (int i = 9; i > 9 - m ; i--)
{
cout << num[i] << std::endl;
}
system("pause");
}
void Mfun(int *num, int m, int start, int end)
{
if (m < end - start + 1)
{
int i = start;
int j = end;
int k = num[start];
while (i != j)
{
while (j > i && num[j] >= k)
{
j--;
}
swap(num[i], num[j]);
while (i < j && num[i] <= k)
{
i++;
}
swap(num[i], num[j]);
}
Mfun(num, m, i + 1, end);
}
if (m > end - start + 1)
{
m = m -(end - start + 1);
Mfun(num, m, start - m, start - 1);
}
}
void QuickSort(int * num, int start, int end)
{
if (start >= end)
{
return;
}
int k = num[start]; //代码这里实际是用k表示的
int i = start;
int j = end;
while (i != j)
{
while (j > i && k <= num[j]) //偶数次的时候移动j.
{
j--;
}
swap(num[i], num[j]);
while (i < j && k >= num[i]) //奇数次的时候移动i.
{
i++;
}
swap(num[i], num[j]);
}
QuickSort(num, start, i - 1);
QuickSort(num, i + 1, end);
}
在求前m大的数,使用的思想就是快速排序的思想。使得下表为end - m之后的数都比numend - m大,这样就找到了前m大的数字,然后对这m个数字进行排序输出即可。代码的复杂度变高了,但是时间复杂度确实降低了,这就是体现了分治法的威力。