每天一道算法题||DAY3

今天的算法题：用分治法解决DAY1的排序题，设计更高效的算法。

输入：n个数的一个序列<a1,a2,……,an>
输出：输入序列的一个排列< a1',a2',……,an '>,满足 a1'≤a2 '≤ …… ≤ an'

许多有用的算法在结构上是递归的：为了解决一个给定的问题，算法一次或多次递归地调用其自身以解决紧密相关的若干子问题。这些算法典型地遵循分治法的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时有三个步骤：

1. 分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。
2. 解决这些子问题，递归的求解各子问题。然而，若子问题的规模足够小，则直接求解。
3. 合并解决这些子问题的解成原问题的解。

归并排序算法完全遵循分治模式。直观上其操作如下：

1. 分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。
2. 解决：使用归并排序递归的排序两个子序列。
3. 合并：合并两个已排序的子序列以产生已排序的答案。
   当待排序的序列长度为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]http://www.jianshu.com/p/5a8e26e42ddb