今天的算法题：用分治法解决DAY1的排序题，设计更高效的算法。
输入：n个数的一个序列<a1,a2,……,an>
输出：输入序列的一个排列< a1',a2',……,an '>,满足 a1'≤a2 '≤ …… ≤ an'
许多有用的算法在结构上是递归的：为了解决一个给定的问题，算法一次或多次递归地调用其自身以解决紧密相关的若干子问题。这些算法典型地遵循分治法的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。
分治模式在每层递归时有三个步骤：
- 分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。
- 解决这些子问题，递归的求解各子问题。然而，若子问题的规模足够小，则直接求解。
- 合并解决这些子问题的解成原问题的解。
归并排序算法完全遵循分治模式。直观上其操作如下：
- 分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。
- 解决：使用归并排序递归的排序两个子序列。
-
合并：合并两个已排序的子序列以产生已排序的答案。
当待排序的序列长度为1时，递归“开始回升”，在这种情况下不要做任何工作，因为长度为1的每个序列都已经排好序。
过程分析：
分解过程
排序过程
贴代码：
#include <iostream>
using namespace std;
void merge(int *data,int start,int end,int *result)
{
int left_length = (end - start + 1) / 2 + 1;//左部分区间的数据元素的个数
int left_index = start;
int right_index = start + left_length;
int result_index = start;
while(left_index < start + left_length && right_index < end+1)
{
//对分别已经排好序的左区间和右区间进行合并
if(data[left_index] <= data[right_index])
result[result_index++] = data[left_index++];
else
result[result_index++] = data[right_index++];
}
while(left_index < start + left_length)
result[result_index++] = data[left_index++];
while(right_index < end+1)
result[result_index++] = data[right_index++];
}
void merge_sort(int *data, int start, int end, int *result)
{
if(1 == end - start)//如果区间中只有两个元素，则对这两个元素进行排序
{
if(data[start] > data[end])
{
int temp = data[start];
data[start] = data[end];
data[end] = temp;
}
return;
}
else if(0 == end - start)//如果只有一个元素，则不用排序
return;
else
{
//继续划分子区间，分别对左右子区间进行排序
merge_sort(data,start,(end-start+1)/2+start,result);
merge_sort(data,(end-start+1)/2+start+1,end,result);
//开始归并已经排好序的start到end之间的数据
merge(data,start,end,result);
//把排序后的区间数据复制到原始数据中去
for(int i = start;i <= end;++i)
data[i] = result[i];
}
}
int main()
{
int data[] = {9,6,7,22,20,33,16,20};
const int length = 8;
int result[length];
cout << "Before sorted:" << endl;
for(int i = 0;i < length;++i)
cout << data[i] << " ";
cout << endl;
cout << "After sorted:" << endl;
merge_sort(data,0,length-1,result);
for(int i = 0;i < length;++i)
cout << data[i] << " ";
cout << endl;
return 0;
}
运行结果：
归并排序运行结果
明日算法题：冒泡排序
输入：n个数的一个序列<a1,a2,……,an>
输出：输入序列的一个排列< a1',a2',……,an '>,满足 a1'≤a2 '≤ …… ≤ an'
回顾：[DAY2]//www.greatytc.com/p/5a8e26e42ddb
