计算机程序设计的艺术

第三卷:排序查找

排序

查找:查表:信息的存储与检索

几种排序算法的实现
//
//  //循环形式的二路归并排序
//
#include<vector>
using::vector;
void exchange(int& A,int& B,int C=0)
{
    C = A;
    A = B;
    B = C;
}
void show_numarray(vector<int>& numarray)
{
    cout << endl;
    for each(auto iter in numarray){
        cout << iter << ',';
    }
    cout << endl;
}
/*
    归并排序长度为：2的n次方
*/
#include<queue>
void merge3(vector<int>& numarray, int step, unsigned length)
{
    //建立两个队列 大小为step
    queue<int> s1, s2;
    int start = 0, end = step * 2;
    //cout << "length is " << length << endl;
loop:
    //将numarray中的元素加入两个队列中
    int i = start;
    while (i < end && i <= length ){
        if (i < end - step){
            s1.push(numarray[i]);
        }
        else{
            s2.push(numarray[i]);
        }
        i++;
    }
    //将栈中的元素再放回数组
    i = start;
    while ( i < end ){
        if (s1.empty() ){
            numarray[i] = s2.front();
            s2.pop();
        }
        else if (s2.empty() ){
            numarray[i] = s1.front();
            s1.pop();
        }
        else {   // 都不为空
            if (s1.front() <= s2.front() ){
                numarray[i] = s1.front();
                s1.pop();
            }
            else{
                numarray[i] = s2.front();
                s2.pop();
            }
        }
        i++;
    }
    if (i < length){
        start = i;
        end = i + 2 * step;
        if (end > length){
            end = length;
        }
        //cout << start << "---" << end << endl;
        goto loop;
    }

}
/*
    18-1-2  未完成
    归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。
    归并排序算法依赖归并操作:二路归并
*/
void merge2(vector<int>& numarray, int step, unsigned length)
{
    //逻辑太长导致考虑难以全面
    vector<int> tmp;
    int a = 0, b = step;
    int step0 = step;
    int step1 = 2*step;
    for (int i = 0; i < length; i++)
    {
        if (a <= step0 && b <= step1){
            if (numarray[a] <= numarray[b]){
                tmp.push_back(numarray[a++]);
            }
            else{
                tmp.push_back(numarray[b++]);
            }
        }
        else if (a > step0 && b < step1){
            tmp.push_back(numarray[b++]);
        }
        else if (a < step0 && b > step1){
            tmp.push_back(numarray[a++]);
        }
        else if (a > step0 && b > step1){
            a += step+1;
            if (a > length){
                while (a <= length){
                    tmp.push_back(numarray[a++]);
                }
                break;
            }
            step0 += 2*step+1;
            b += step+1;
            step1 += 2*step+1;
            if (b > length){
                b -= step;
                step1 = length;
            }
            cout << i << endl;
        }
        else{
            cout << a << "_*_" << b << endl;
        }
    }
    //缺少一个赋值函数
    show_numarray(tmp);
}

void merge1(vector<int>& numarray,int step,unsigned length)
{
    //基于交换 ： 方向就错了（一定要搞清楚算法）
    for (int i = 0; (i+2*step) < length;i++){
        for (int j = 0; j < step; j++){
            if (numarray[i + j] > numarray[i+j+step]){
                exchange(numarray[i + j], numarray[i + j + step]);
            }
        }
        i += step * 2;
    }
}
// 18-1-1 元旦 感冒状态
void merge(vector<int>& numarray, int step, unsigned length)
{
    //思路混乱
    vector<int> tmp;
    for (int i = 0; i < length;)
    {
        for (int j = 0,k = 0; (j < step ) || (k < step );)
        {
            if (i+step >=length){
                if (i + j < length){
                    tmp.push_back(numarray[i + j]);
                    j++;
                }
                else{
                    break;
                }
            }
            else if ((i + k + step)<length && (j < step) && numarray[i + j] <= numarray[i + k + step]){
                tmp.push_back(numarray[i + j]);
                j++;
            }
            else if ((i + k + step)<length && (k < step) && numarray[i + j] > numarray[i + k + step]){
                tmp.push_back(numarray[i + k + step]);
                k++;
            }
            else if ((i + k + step) == length || (k == step) ){
                tmp.push_back(numarray[i + j]);
                j++;
            }
            else if (j==step) {
                tmp.push_back(numarray[i + k + step]);
                k++;
            }
            else {
                cout << "异常情况！" << i << '-' << j << '-' << k << endl;
                break;
            }
        }
        i += step * 2;
    }
    cout << tmp.size() <<"---"<< length << endl;

    for (int i = 0;i < tmp.size() ; i++){
        numarray[i] = tmp[i];
    }

}

void bi_merge_sort(vector<int>& numarray)
{
    unsigned length = numarray.size();
    for (int i = 1; i <= length/2;)
    {
        cout <<"step is :"<< i << endl;
        merge3(numarray,i,length);
        i *= 2;
        show_numarray(numarray);
        //break;
    }

}
void test()
{
    vector<int> numarray;
    int scale = 64;
    for (int i = 0; i < scale;i++){
        numarray.push_back(scale-i);
    }
    show_numarray(numarray);
    bi_merge_sort(numarray);
}

//*************快排**************
//  -2018-3-10
#include<vector>
/*-----------------功能函数--------------------------*/

void show_data(vector<int> data){
    cout << endl;
    for each (auto iter in data){
        cout << iter << " ";
    }
    /*linux下更改为
    for (auto iter : data){
        cout<<iter<<" ";
    }
    */
}
template<typename T>
void bi_swap(T& A,T& B){
    static T C = 0;
    C = A;
    A = B;
    B = C;
}
/*检查数据的大小排列
        默认为由小到大
        返回值：不和趋势的元素数
    大约：25s：50万int数的排序
*/
int check_data(vector<int> data,bool small2big=true){
    long count=0;
    long end=data.size();
    assert(end>=2);
    if(small2big){
        for(long i=1;i<end;i++){
            count+=(data[i-1] <= data[i] ? 0 : 1 );
        }
    }
    else{
        for(long i=1;i<end;i++){
            count+=(data[i-1] >= data[i] ? 0 : 1 );
        }
    }
    cout<<"不和大小趋势的元素有："<<count<<endl;

    return count;
}
/**********百科官方版1**************************/
template<typename T>
void quick_sort_recursive(vector<T>& arr, int start, int end) {
    if (start >= end)
        return;
    T mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right)
            left++;
        while (arr[right] >= mid && left < right)
            right--;
        std::swap(arr[left], arr[right]);
    }
    if (arr[left] >= arr[end])
        std::swap(arr[left], arr[end]);
    else
        left++;
    quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}
template<typename T> 
void quick_sort(vector<T>& arr,int len) {
    quick_sort_recursive(arr, 0, len);
}
/****************开发过程版**************************/

//每一步都要搞清楚，想不出来就写流程
//分析出所有的递归过程中的情况，并用代码覆盖
//
int flat(vector<int>& data, int start, int end){
    //[1]get a number: 1\first data.    2\random data
    int wait2compare = start;
    //cout << endl << wait2compare;
    start += 1;
    while (end > start ){
        //[2]compare start,end;
        if ((data[start]>data[wait2compare]) && (data[end]<data[wait2compare])){
            bi_swap<int>(data[start], data[end]);
            start++;
            end--;
        }
        if (data[start] <= data[wait2compare]){
            start += 1;
        }
        if (data[end] >= data[wait2compare]){
            end -= 1;
        }
    }
    //[3]change the two value
    data[wait2compare]>data[end] ? bi_swap<int>(data[wait2compare], data[end]):0;
    return end;
}
void quick_sort1(vector<int>& data,int start,int end){
    //递归操作首先调试完成非递归部分
    if(end>start){ 
        //cout << endl << "参数：" << start << "-" << end;
        int middle = flat(data, start, end);
        //show_data(data);
        cout << "middle" << middle;
        quick_sort1(data, start, middle-1);
        quick_sort1(data, middle, end);   //为什么不减1?
    }
}

/****************无注释·泛型版**********************/
template<typename T>
int flat1(vector<T>& data, int start, int end){
    int tmp = start++;
    while (end > start){
        if ((data[start]>data[tmp]) && (data[end]<data[tmp]))   bi_swap<T>(data[start++], data[end--]);
        if (data[start] <= data[tmp])   start++;
        if (data[end] >= data[tmp])     end--;
    }
    data[tmp]>data[end] ? bi_swap<int>(data[tmp], data[end]) : void(0);  //更为严格的类型检查
    return end;
}
template<typename T>
void quick_sort2(vector<T>& data, int start, int end){
    if (end>start){
        int middle = flat1(data, start, end);
        quick_sort2(data, start, middle - 1);
        quick_sort2(data, middle, end);  
    }
}
/***************************************************/
void test1(){
    vector<int> data;
    int end = 200;
    for (int i = 0; i < end; i++){
        data.push_back(rand()%100);
    }
    show_data(data);
    quick_sort2<int>(data,0,data.size()-1);
    show_data(data);
}

#需要从keras中导入相关的库
from random import randint
import numpy as np
import keras
from keras.layers import Dense,Activation
from keras.layers import Dropout
from keras.layers import Flatten
from keras.layers import Input
from keras.models import Model

def gene_data(length=1000):
    #生成未排序的隨機數列
    assert(type(length) is int)
    data_in=[]
    data_out=[]
    for _ in range(10000):
        tmp=[randint(1,10000) for _ in range(length)]
        data_in.append([tmp])
        data_out.append(sorted(tmp))
    return np.array(data_in)/10000,np.array(data_out)/10000

def nn_sort():
    data_in,data_out=gene_data()
    print(data_in.shape)
    act='relu'

    start=Input(shape=(1,1000))
    x=Dense(1000,activation=act)(start)  #第一层初始化很重要
    #x=Dense(300,activation=act )(x)
    x=Dense(1200,activation=act )(x)
    #x=Dense(500,activation=act )(x)
    x=Flatten()(x)
    end=Dense(1000,activation='relu')(x)
    model_D=Model(inputs=start,outputs=end)
    model_D.summary()
    model_D.compile(loss='mse',optimizer='adam', metrics=['accuracy'])
    model_D.fit(data_in,data_out, epochs=36, batch_size=32,verbose=2,validation_split=0.2
                 )
    #方案1：[已實現] 将输入和真实分布 统一转化为浮点表示。进行回归表示
    #方案2：在神经网络的第一层作归一化。最后一层反归一化[*最大值，int()]。

nn_sort()

其他内容

分析与综合:分析的方法贯彻的是由整体到个体,由共同性到特异性.一个分析树是由上到下(由树根到树叶)的过程(这个工程中更多的看到的是忽略共通性后的不同点).综合的方法则是运用概括的方法,由个体到整体,由差异性到共同点,一颗分析树是由下到上(由树叶到树根)的过程,(这个工程中看到的更多的是忽略差异后的共通性)

随机:即使你才中了开头,你也才不中他的结尾.我们常理解的随机是不可预测性,而计算机的随机讲求的是等可能性(1-10中的随机数),侧重不同,前一种随机往往就有局部的可能性不"随机".如色子连出三个6

对新技术完全保密的人 < 将新技术申请专利的人(专利时间有限) < free开源的人.

不要操作原始数据,要把原始数据打包成压缩包,所有的操作都基于原始数据的备份数据之上.

1、将链表和向量合并既方便插入、删除操作，又方便查找（数据结构复合） 类似：在向量上建立查找tree和索引表 【都是利用空间换时间】 复杂的数据结构不容易构建，而且容易出错。

2、为什么不在数据结构初始化的时候就考虑到问题的规模（即对相应的数据规模进行估计） 1、数据结构的通用性（即无法做估计） 2、前后端分离的限制 3、尽量不做黑箱便于算法优化。

3、人脑能记住的场景元素非常有限【而且必须有主线】 所以函数即是功能 功能要简单 函数要小

七、AdaBoost Adaboost是一种迭代算法， 其核心思想是针对同一个训练集训练不同的分类器(弱分类器)， 然后把这些弱分类器集合起来，构成一个更强的最终分类器 (强分类器)。 其算法本身是通过改变数据分布来实现的， 它根据每次训练集之中每个样本的分类是否正确， 以及上次的总体分类的准确率，来确定每个样本的权值。 将修改过权值的新数据集送给下层分类器进行训练， 最后将每次训练得到的分类器融合起来，作为最后的决策分类器。

博弈论game

声明:本部分内容大部分来自互联网

概念

例子

囚徒困境:人与人间的不信任

情况 囚徒A 囚徒B A结果 B结果
情景1 招供 招供 4年 4年
情景2 招供 不招供 1年 5年
情景3 不招供 招供 5年 1年
情景4 不招供 不招供 0年 0年
有意思的地方:
现实案例

智猪博弈(boxed pigs)

踏板与食槽分离:按动踏板食槽投入饲料.只有大猪才按的动踏板.

启发式算法

一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计

香农