方法的实现方法，功能的实现方法。

方法的实现方法，功能的实现方法。使用算法。

1.什么是算法：方法的实现方法，问题的程序式解决方法。

算法的5个特征：

输入性：0个或多个输入。

输出性：1个或多个输出。

有穷性：方法必须在有穷的时间内执行完。

确定性：方法的每个语句都有确切的含义，不能有二义性。必须是相同的输入，有相同的输出。

可行性：方法的每一句都可以用计算机来执行。

 --

 

2.算法模式：

递归：自身调用自身。实现时要有结束条件。

归纳：尾递归。

例如：选择排序
对数组a1...an排序。
定i位的值
fun(0)
fun(i){
    if(i<n){
	    k=i;//k保存最小值的下标。
		for(j=i;j<n;j++){
			if(a[k]>a[j]){
				k=j;
			}
		}
		a[i]与a[j]交换位置;
		fun(i+1);
	}
}

 

分治：大规模划分成小规模分别解决，然后在组合起来。

二分法查找
在数组a1。。。an从小到大已排序中找k。
fun(low,high,k,a){
	mid=(low+high)/2; //向下取整。
	if(k==a[mid]) {
	    return mid;
	}else if(k<a[mid]){
		return fun(low,mid-1,k);
	}else{
	    return fun(mid+1,high,k);
	}
}

 

动态规划：解本问题解过程中会缓存和使用中间过程值。

求字符串A和B的最长公共子串的长度。
L[i,j]
A或B有一个串长度为0：L[i,j]=0;
ai是A最后一个，bj是B的最后一个，ai=bj：L[i,j]=L[i-1,j-1]+1;
ai!=bj:L[i,j]=min{L[i-1,j],L[i,j-1]};

//n为A的长度，m为B的长度。
fun(A,B){
	for(i=0;i<n:i++){
		L[i,0]=0;
	}
	for(j=0;j<m;j++){
		L[0,j]=0;
	}
	
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			if(ai=bj){
			    return L[i-1,j-1]+1;//return fun(A.sub(i),B.sub(j));
			}else{
			    return min{L[i-1,j],L[i,j-1]}
			}
		}
	}
	
	return L[n,m];
}

 --

 

3.方法性能估算方法：

性能就是资源的使用情况：时间方面（时间复杂度），内存方面（空间复杂度），其他资源方面。

高性能就是：少时间，少内存，少其他资源。

时间方面的估算方法：

常见时间复杂度比较：

Ο(n!)>Ο(2的n次方)>Ο(n2)>Ο(nlog2n)>Ο(n)>Ο(log2n)>Ο(1)

1.基本步奏的执行次数。（有时是几个基本步骤的和）(一般次数是规模n的函数，在式子中找出使次数增长最快的项就是此算法的时间复杂度)

以下分析都是求最坏情况下的时间复杂度。 

 

归纳法的：选择排序的：时间复杂度：

基本步骤是：a[k]>a[j]

n=1:a[k]>a[j]执行1次

n=n:a[k]>a[j]执行比较次数是c(n)=c(n-1)+(n-1)次

式子展开得出：

c(n)=n(n-1)/2=1/2n的平方-1/2n;

所以时间复杂度是O(n的平法)，读作O n的平方。

 

分治法的：二分法查找的：时间复杂度：

基本步骤是：三次比较中每次都会比较其中一个。

n=1:1

n>=2:c(n)=1+c(n/2向下取整)

式子展开：

c(n)<logn(向下取整)+1

所以时间复杂度是O(logn)

 

动态规划的：求字符串A和B的最长公共子串的长度的：时间复杂度：

基本步骤是：每次return L[i-1,j-1]+1或return min{L[i-1,j],L[i,j-1]}会执行一个。

n,m时：执行次数是c(n,m)=n*m

所以时间复杂度是O(nm)

 

2.具体执行时间测量。例如：可以在函数开始时打个时间戳，结束时打个时间戳，求执行时间。

 

内存方面的估算方法：

1.基本步奏需要的辅助内存。

--

 

4.方法的可读性：

1.程序书写要规范，注意缩进、空行。

2.需要必要的合理的注释。函数功能注释，关键步奏注释。

3.起有自身功能描述的函数名，或变量名。

4.方法功能单一，低耦合，高内聚。

5.其他面向对象设计原则。

---------------------------------------------------------------------------------------------------------------

1.排序

1.选择排序：每次选出最小值放到最首位，然后规模减1再次选出最小值，直到规模为0。

 

    void fun(int[] a, int len) {
        for (int i = 0; i < len; i++) {
            int minIndex = i;
            for (int j = i; j < len; j++) {
                if (a[minIndex] > a[j]) {
                    minIndex = j;
                }
            }

            if (minIndex != i) {
                int temp = a[i];
                a[i] = a[minIndex];
                a[minIndex] = temp;
            }
        }
    }
    //时间复杂度是：O(n的平方)

 

 

--

2.交换排序

1.冒泡排序：相邻两项比较，值大的放后位，然后位置+1再重复前面的步骤，一直到位置为length结束（这样达到了最大值在最后面）。规模-1再次前面的步骤，直到规模为0.

 

    void fun(int[] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length-i-1; j++) {
                if (a[j] > a[j+1]) {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
    }

//时间复杂度是：O(n的平方)

 2.快速排序：选择一个轴心值，小的放轴心值左边，大的放轴心值右边。以轴心位置为分界分成两部分，递归此过程。

void quicksort(int[] v, int left, int right) {
    if (left < right) {

        int pivotValue = v[left];
        int low = left;
        int high = right;
        while (low < high) {
            
            //从high开始一直找到比轴心值小的值放到low的位置
            // low位置的值不需要保存，值已经给pivotValue，（或high的位置，非循环第一次时））
            while (low < high && v[high] > pivotValue) {
                high--;
            }
            v[low] = v[high];
            
            //反转从low开始一直找到比轴心值大的的放到high的位置
            // （high位置的值不需要保存，值已经给low的位置）
            while (low < high && v[low] < pivotValue) {
                low++;
            }
            v[high] = v[low];
        }
        //现在low为轴心位置。
        v[low] = pivotValue;
        
        //以轴心位置分割两部分递归此过程。
        quicksort(v, left, low - 1);
        quicksort(v, low + 1, right);
    }
}
    
//时间复杂度是O(nlogn)

--

3.插入排序：i前的是有序的，把第i位的值插入到i前面的数组中。然后移动i的值,重复前面过程，直到i为数组长度。

 

public void insertSort(int a[]) {
    for (int i = 1; i < a.length; i++) {
        int insertIndex = i;
        int key = a[i];//当前要进行插入的值

        for (int j = i - 1; j >= 0; j--) {
            if (key < a[j]) {
                //后移元素
                a[j + 1] = a[j];
                insertIndex = j;
            } else {
                //大时在insertIndex的位置插入key
                break;
            }
        }
        a[insertIndex] = key;
    }
}

//时间复杂度是：O(n的平方)

 

 

--------------------------------------

2.查找

1.二分查找

 

int binary_search(int* a, int len, int goal)
{
    int low = 0;
    int high = len -1;
    while (low <= high)
    {
        int middle = (high - low) / 2 ;
        if (a[middle] == goal){
            return middle;
		}else if (a[middle] > goal){
            high = middle - 1;
		}else{
            low = middle + 1;
		}
    }
    return -1;
}
时间复杂度是：o(logn)

-------------------------------------

3.链表的逆序，插入，删除。

1.逆序：从头开始每个都提到最前面，q指向heap，p指向head的下一位。循环内先用q指向p的下一位，把p往前翻到head前，head再指向p。p向前移位。重复前面的步骤

Node reverse_Link(Node head) {
    Node p;
    Node q;
    q = head;
    p = head.next;
    while (p != null) {
        q.next = p.next;
        p.next = head;
        head = p;
        p = q.next;
    }
    return head;
}

 

 

2.插入：找到要插入的位置p，e.next=p.next,p.next=e;

//i位置前插入值e
insert_Link(Node head, int i, Node e) {
    Node p;
    p = head;

    for (int j = 1; j < i-1; j++) {
        if (p == null) {
            return;
        }
        p = p.next;
    }

    e.next = p.next;
    p.next = e;
}

 

 

3.删除:找到要删除的位置p，要删除的前一个位置p。q.next=p.next;

//删除位置i
delete_Link(Node head, int i){
    Node p;
    q = head;
    p = head;
    for (int j = 1; j < i; j++) {
        if (p == null) {
            return;
        }
        q = p;
        p = p.next;
    }

    if (p == null) {
        return;
    }

    if (p == q) {
        head = null;
    }

    q.next = p.next;
}

 

 

-------------------------------------

4.二叉树遍历与二叉树深度

二叉树遍历：

 

二叉树遍历：
前序遍历 根左右
void preOrder(BinaryTree bt) {
    if (pRoot != NULL) {
        visit(bt);//visit只是代表处理，关键的是结构
        preOrder(bt.leftChild);
        preOrder(bt.rightChild);
    }
}

中序遍历 左根右
void inOrder(BinaryTree bt) {
    if (pRoot != NULL) {
        inOrder(bt.leftChild);
        visit(bt); //visit只是代表处理，关键的是结构
        inOrder(bt.rightChild);
    }
}

后序遍历，左右根
void postOrder(BinaryTree bt) {
    if (bt != null) {
        postOrder(bt.leftChild);
        postOrder(bt.rightChild);
        visit(bt);//visit只是代表处理，关键的是结构
    }
}

 

二叉树深度

 

int treeDeep(BinaryTree bt) {
    int deep = 0;
    if (bt == null) {
        return 0;
    } else {
        int lChilddeep = treeDeep(bt.lChild);
        int rChilddeep = treeDeep(bt.rChild);
        deep = lChilddeep >= rChilddeep ? lChilddeep + 1 : rChilddeep + 1;
    }
    return deep;
}