quoniammm / happy-algorithm

算法导论笔记以及算法实现

Hi. It's quoniammm

happy-algorithm's Issues

渐进符号介绍以及如何求解递归式

完美的文章并不存在，就像完美的绝望并不存在一样。 ——村上春树

渐进符号介绍

1.
定义（注：两种定义适用于下面的所有渐进符号，为了方便，以后的所有渐进符号都只给出第一种定义方式）：
<1>.存在常量，，使得 ，对于所有成立，即上界，；
<2>. 是使得 满足：存在常量，，使得 ，对于所有成立的函数集。

定义一（常用）	定义二（不常用）

2.
定义：存在常量，，使得 ，对于所有成立，即下界，如：；

二分查找

我们自以为知之甚多的的事情背后，无不潜伏着等量的未知因素 ——村上春树

Array.prototype.binary_search = function(low, high, key) {
    var mid = parseInt((high + low) / 2),
          low = low,
          high = high;
    if(low > high)
        return -1;
    else {
        if(key == this[mid])
            return mid;
        else if(key > this[mid])
            return this.binary_search(mid+1, high, key);
        else
            return this.binary_search(low, mid-1, key);
    }
}

时间复杂度：

选择排序（算法实现）

/*
 * chosenSort.cpp
 *
 *  Created on: 2016年1月8日
 *      Author: quoniam
 */
#include<iostream>
using namespace std;
int main()
{
    int n,a[1000];
    cin >> n;
    for(int i = 0;i < n;i ++) {
        cin >> a[i];
    }
    for(int i = 0;i < n;i ++) {
        for(int j = i+1;j < n;j ++) {
            if(a[i] < a[j]) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    for(int i = 0;i < n;i ++) {
        cout << a[i] << " ";
    }
}

冒泡排序（算法实现）

/*
 * bubbleSort.cpp
 *
 *  Created on: 2016年1月6日
 *      Author: quoniam
 */
#include<iostream>
using namespace std;
int main()
{
    int n, a[1000];
    cin >> n;
    for(int i =0;i < n;i ++) {
        cin >> a[i];
    }
    for(int i = 0;i < n;i ++) {
        for(int j = 1;j < n - i;j ++) {
            if(a[j-1] > a[j]) {
                int temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;
            }
        }
    }
        for(int i = 0;i < n;i ++) {
        cout << a[i] << endl;
    }
    return 0;
}

奇偶排序<1>（算法实现）

/*
 * oddEvenSort.cpp
 *
 *  Created on: 2016年1月7日
 *      Author: quoniam
 */
#include<iostream>
using namespace std;
int main()
{
    int a[10];
    int l = 0, r = 9;
    for(int i = 0;i < 10;i ++) {
        cin >> a[i];
    }
    while(l <= r) {
        bool leftisOdd = (a[l] % 2 == 1);
        bool rightisEven = (a[r] % 2 == 0);
        if(leftisOdd) {
            l++;
        } else if(rightisEven) {
            r--;
        } else if(!leftisOdd && !rightisEven) {
            int temp = a[l];
            a[l] = a[r];
            a[r] = temp;
        }
    }
    int start = 0, end = l;
    for(int i = start;i < end -1;i ++) {
        for(int j = start + 1;j <start +  end - i;j ++) {
            if(a[j-1] > a[j]) {
                int temp = a[j-1];
                a[j-1] = a[j];
                a[j] = temp;
            }
        }
    }
    start = l;
    end = 10;
    for(int i = start;i < end-1;i ++) {
        for(int j = start + 1;j < start + end - i;j ++) {
            if(a[j-1] > a[j]) {
                int temp = a[j-1];
                a[j-1] = a[j];
                a[j] = temp;
            }
        }
    }
    for(int i =0;i < 10;i ++) {
        cout << a[i] << " ";
    }
    return 0;
}

奇偶排序<2>（算法实现）

/*
 * oddevenSort.cpp
 *
 *  Created on: 2016年1月7日
 *      Author: quoniam
 */
#include<iostream>
using namespace std;
int main() {
    int a[10];
    for(int i = 0;i < 10;i ++) {
        cin >> a[i];
    }
    for(int i = 0;i < 10; i ++) {
        for(int j = 1;j < 10 - i;j ++) {
            bool leftisEven = (a[j-1] % 2 == 0);
            bool rightisEven = (a[j] % 2 == 0);
            if((leftisEven && !rightisEven) || (leftisEven == rightisEven && a[j-1] > a[j])){
                int temp = a[j-1];
                a[j-1] = a[j];
                a[j] = temp;
            }
        }
    }
    for(int i = 0;i < 10;i ++) {
        cout << a[i] << " ";
    }
    return 0;
}

归并排序

刚刚好，看到你幸福的样子，于是幸福着你的幸福。 ——村上春树

//归并排序数组 A[1...n]
Array.prototype.merge_sort = function() {
   //归并函数，归并函数的结果使得子数组是从小到大排列的
    var merge = function(left, right) {
        var final = [];
        //每次循环弹出两个数组中较小的那个值（因为数组是从小到大排列的），
        //并压入要返回的那个数组中
        while (left.length && right.length)
            final.push(left[0] <= right[0] ? left.shift() : right.shift());
        return final.concat(left.concat(right));
    };
    var len = this.length;
   //如果n=1，排序完成
    if (len < 2) return this;
    var mid = len / 2;
   //递归的合并排列好的子数组
    return merge(this.slice(0, parseInt(mid)).merge_sort(), this.slice(parseInt(mid)).merge_sort());
};

时间复杂度：O(nlgn)