CLRS 2.3设计算法 - Go语言中文社区

CLRS 2.3设计算法

2.3-1
这里写图片描述

2.3-2

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

void merge(int *array,int p,int q,int r)
{
    int n1 = q - p + 1;                 //计算前半部分数组大小
    int n2 = r - q;                     //计算后半部分数组大小
    int *L = new int[n1];
    int *R = new int[n2];
    int i = 0,j = 0;;
    for(int k = p; k <= q; ++k)         //将数组前半部分复制给左边子数组
        *(L + i++) = *(array + k);
    for(int k = q + 1; k <= r; ++k)     //将数组后半部分复制给右边子数组
        *(R + j++) = *(array + k);
    i = j = 0;
    for(int k = p; k <= r; ++k)
    {
        if(i == n1)                     //前半部分子数组已经复制完，直接复制后半部分到数组中
            *(array + k) = *(R + j++);
        else if(j == n2)                //后半部分子数组已经复制完，直接复制前半部分到数组中
            *(array + k) = *(L + i++);
        else if(*(L + i) <= *(R + j))   //将较小元素复制到数组中
            *(array + k) = *(L + i++);
        else *(array + k) = *(R + j++);
    }
    delete []L;
    delete []R;
}

void merge_sort(int *array,int p,int r)
{
    if(p < r)
    {
        int q = (p + r) / 2;
        merge_sort(array,p,q);
        merge_sort(array,q+1,r);
        merge(array,p,q,r);
    }
}

int main()
{
    int *array;
    int len,key;
    cout << "input the length of array" << endl;
    cin >> len;
    array = new int[len];
    cout << "input " << len << " integers" << endl;
    for(int i = 0; i < len; ++i)
        cin >> *(array + i);
    merge_sort(array,0,len-1);
    cout << "after sort" << endl;
    for(int i = 0; i < len; ++i)
        cout << *(array + i) << ' ';
    cout << endl;
    delete []array;
    return 0;
}

2.3-3
证明：
当 n = 2 时，显然成立；
设当 n = 2k−1 时成立，此时 T(n) = nlgn = (k−1)⋅2k−1；
则当 n = 2k 时，由递归式有 T(n) = 2T(n/2)+n = 2⋅(k−1)⋅2k−1+2k = k⋅2k = nlgn 也成立。

2.3-4
递归式：

T(n)={Θ(1)T(n−1)+C(n−1)if n = 1otherwise

其中 C(n) 是向有 n 个元素数组里面插入一个元素所需时间。
最坏运行时间 Θ(n2)。 
#include <iostream>
using std::cin;
using std::cout;
using std::endl;

void insertion_sort_recursively(int *array,int length)
{
    if(length == 1)                                 //只有一个元素则此元素已排序，返回
        return;
    insertion_sort_recursively(array,length-1);     //递归排序
    /***将当前元素插入到数组中***/
    int i = length - 1;
    int key = *(array + i);
    int j = i - 1;
    while(j >= 0 && *(array + j) > key)
    {
        *(array + j + 1) = *(array + j);
        --j;
    }
    *(array + j + 1) = key;
}

int main()
{
    int *array;
    int len,key;
    cout << "input the length of array" << endl;
    cin >> len;
    array = new int[len];
    cout << "input " << len << " integers" << endl;
    for(int i = 0; i < len; ++i)
        cin >> *(array + i);
    insertion_sort_recursively(array,len);
    cout << "after sort" << endl;
    for(int i = 0; i < len; ++i)
        cout << *(array + i) << ' ';
    cout << endl;
    delete []array;
    return 0;
}

2.3-5
二分查找的迭代和递归如下：

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

int binary_search(int *array,int length, int key)
{
    int low = 0, high = length - 1;
    while(low <= high)
    {
        int mid = (low + high) / 2;
        if(key == *(array + mid))
            return mid;                 //返回下标以0开始
        else if(key < *(array + mid))   //前半段中寻找
            high = mid - 1;
        else low = mid + 1;             //后半段中寻找
    }
    return -1;                          //未找到则返回-1
}

int binary_search(int *array,int low,int high,int key)
{
    while(low <= high)
    {
        int mid = (low + high) / 2;
        if(key == *(array + mid))
            return mid;
        else if(key < *(array + mid))
            return binary_search(array,low,mid-1,key);
        else return binary_search(array,mid+1,high,key);
    }
    return -1;
}


int main()
{
    int array[] = {-5,1,2,3,4,5,6,7,45};
    cout << binary_search(array,9,2) << endl;
    cout << binary_search(array,0,8,2) << endl;
    return 0;
}

递归式：T(n)=T(n/2)+c，所以最坏情况是Θ(lgn)。

2.3-6
不可以，虽然可以在 lgn 时间内找到插入的位置，但是还是需要线性时间来移动元素。最坏时间复杂度依然是 Θ(n2)。
附上二分查找插入排序的代码

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

int binary_search(int *array,int length,int key)
{
    int low = 0,high = length - 1;
    while(low <= high)
    {
        int mid = (low + high) / 2;
        if(key == *(array + mid))
            return mid;                         //返回找到的坐标
        else if(key < *(array + mid))
            high = mid - 1;
        else low = mid + 1;
    }
    return high;                                //返回第一个小于key的元素下标
}

void insertion_sort_with_binary_search(int *array,int length)
{
    for(int i = 1; i < length; ++i)
    {
        int key = *(array + i);
        int j = i - 1;
        int pos = binary_search(array,j,key);
        while(j > pos && *(array + j) > key)    //找到插入的位置
        {
            *(array + j + 1) = *(array + j);
            --j;
        }
        *(array + j + 1) = key;
    }
}


int main()
{
    int *array;
    int len,key;
    cout << "input the length of array" << endl;
    cin >> len;
    array = new int[len];
    cout << "input " << len << " integers" << endl;
    for(int i = 0; i < len; ++i)
        cin >> *(array + i);
    insertion_sort_with_binary_search(array,len);
    cout << "after sort" << endl;
    for(int i = 0; i < len; ++i)
        cout << *(array + i) << ' ';
    cout << endl;
    delete []array;
    return 0;
}

2.3-7
首先用一个时间复杂度为 Θ(nlgn) 的排序算法对数组进行排序，然后从头到尾进行扫描，利用二分法查找 x–S[i]，若找到即说明存在两个数之和为 x，当扫描到尾部还没找到则说明不存在，这时算法时间复杂度是 Θ(nlgn)。

#include <iostream>
#include <limits>
using std::cin;
using std::cout;
using std::endl;

void merge(int *array,int p,int q,int r)
{
    int n1= q - p + 1;
    int n2 = r- q;
    int *L = new int[n1+1];
    int *R = new int[n2+1];
    int i = 0,j = 0;
    for(int k = p; k <= q; ++k)
        *(L + i++) = *(array + k);
    *(L + i) = INT_MAX;
    for(int k = q + 1; k <= r; ++k)
        *(R + j++) = *(array + k);
    *(R + j) = INT_MAX;
    i = j = 0;
    for(int k = p; k <= r; ++k)
    {
        if(*(L + i) <= *(R + j))
            *(array + k) = *(L + i++);
        else *(array + k) = *(R + j++);
    }
    delete []L;
    delete []R;
}

void merge_sort(int *array,int p,int r)
{
    if(p < r)
    {
        int q = (p + r) / 2;
        merge_sort(array,p,q);
        merge_sort(array,q+1,r);
        merge(array,p,q,r);
    }
}

int binary_search(int *array, int low,int high, int key)
{
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (key == *(array + mid))
            return mid;
        else if (key < *(array + mid))
            high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

bool sum_equal_x(int *array, int length, int val)
{
    for (int i = 0; i < length - 1; i++)
    {
        int key = val - *(array + i);
        if (-1 != binary_search(array, i + 1, length - 1, key))
            return true;
    }
    return false;
}

int main()
{
    int *array;
    int len,key;
    cout << "input the length of array" << endl;
    cin >> len;
    array = new int[len];
    cout << "input " << len << " integers" << endl;
    for(int i = 0; i < len; ++i)
        cin >> *(array + i);
    cout << "input integer x: ";
    int x;
    cin >> x;
    if(sum_equal_x(array,len,x))
        cout << "there exists two elements" << endl;
    else cout << "not exists two elements" << endl;
    delete []array;
    return 0;
}
版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/u012593447/article/details/46970491
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。
  • 发表于 2020-03-01 22:31:43
  • 阅读 ( 603 )
  • 分类：算法

你可能感兴趣的文章

精选的优质文章

0 条评论

请先 登录 后评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看

来源51CTO

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！