期末考试快到了，总结算法，以备后续学习。

看之前可以先关注目录，这样可以明确本文的结构，快速找到所需的知识

1. 输入
2. 输出
3. 有穷
4. 可行
5. 确定

• 自然语言
• 流程图
• 伪代码
• 语言的编程设计

概念：

• O(n):用来描述增长率的上限
• Ω(n):用来描述增长率的下限

最优算法：大Ω符号通常与大O符号合作，以证明问题的具体算法是问题的最佳算法，或者是问题中算法类的最佳算法。一般来说，如果能证明问题的时间下限是Ω(g(n))任何解决问题的算法都被认为是解决问题的最佳算法

主定理：

习题：

分治法：将难以直接解决的大问题分为一些小子问题，分别解决每个子问题，然后合并每个子问题。分为三个步骤：划分、解决问题和合并。

减治法：将难以直接解决的大问题分为几个子问题，但这些子问题不需要单独解决，只需要解决其中一个子问题，因此不需要合并子问题的解决方案。

同样：都需要划分子问题，都需要解子问题；两者的编程理念都是递归

不同:减治法不需要合并子问题，只需要找出子问题与原问题之间的对应关系，或者直接解决原问题。

子问题的规模最好大致相同(子问题的平衡)

分治法：

1. 归并排序
2. 快速排序

减治法：

1. 折半查找
2. 二叉查找树
3. 堆排序

没有最好的排序和搜索算法，只有最合适的。

核心思想：

不断将序列一分为二(如果是奇数，则向上取整，如7/2=3.5向上取整则为4，所以左四个数，右三个数)直到只有一个数，然后开始合并排序 。

详细解读：

一是分，二是治，先不断分为二，再不断合二为一。

我们需要将两个有序的子序列合并成一个有序的序列，如上图中的最后一个合并，将[4、5、7、8]和[1、2、3、6]两个有序的子序列合并成最后一个序列[1、2、3、4、5、6、7、8]。

以下是两个应用，一个是偶序列，一个是奇序列

代码：

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];
    }
}

merge的过程为：

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++];
}

现在对程序进行测试：

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;
}

运行结果：

总结：

归并排序的性能不受输入数据的影响，始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

核心思想

快速排序算法的思想非常简单，在待排序的数列中，我们首先要找一个数字作为基准数（这只是个专用名词）。为了方便，我们一般选择第 1 个数字作为基准数（其实选择第几个并没有关系）。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。

因此可以总结为三点：

• 1．先从数列中取出一个数作为基准数。
• 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
• 3．再对左右区间重复第二步，直到各区间只有一个数。

那么移动元素，该怎么移动呢？

快速排序的操作是这样的：首先从数列的最右边（也就是最后一个数字）开始往左边找，我们设这个下标为 j，也就是进行减减操作（j–），找到第 1 个比基准数小的值，让它与基准值交换；接着从左边开始往右边找，设这个下标为 i，然后执行加加操作（i++），找到第 1 个比基准数大的值，让它与基准值交换；然后继续寻找，直到 i 与 j 相遇时结束，最后基准值所在的位置即 k 的位置，也就是说 k 左边的值均比 k 上的值小，而 k 右边的值都比 k 上的值大。

详细解读：

代码：（Java版）

public class QuickSort { 
        
    private int[] array;
    public QuickSort(int[] array) { 
        
        this.array = array;
    }
    public void sort() { 
        
        quickSort(array, 0, array.length - 1);
    }
    public void print() { 
        
        for (int i = 0; i < array.l	ength; i++) { 
        
            System.out.println(array[i]);
        }
    }
   
    /** * 递归排序 * @param src * @param begin * @param end */
    private void quickSort(int[] src, int begin, int end) { 
        
        if (begin < end) { 
        
            int key = src[begin];
            int i = begin;
            int j = end;
            while (i < j) { 
        
                while (i < j && src[j] > key) { 
        
                    j--;
                }
                if (i < j) { 
        
                    src[i] = src[j];
                    i++;
                }
                while (i < j && src[i] < key) { 
        
                    i++;
                }
                if (i < j) { 
        
                    src[j] = src[i];
                    j--;
                }
            }
            src[i] = key;
            quickSort(src, begin, i - 1);
            quickSort(src, i + 1, end);
        }
    }
}

核心思想：

​ 堆排序中的“堆”的含义是完全二叉树。算法的具体操作步骤分为4步：

1. 先将无序序列画成一个完全二叉树的形式
2. 再自底向上，自右向左对完全二叉树中的元素进行比较得到大根堆或小根堆
3. 然后将完全二叉树的根节点与堆中最右下角的元素互换，互换之后根节点脱落，从此此根节点不再参与比较，而是等待之后的根节点相继脱落一起形成有序区。
4. 之后一种重复2,3步便可得到有序区（有序序列）。

这里说一下什么是完全二叉树，同时也区分一下完全二叉树与满二叉树的区别

先看图：

完全二叉树：设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，
第 h 层所有的结点都连续集中在最左边（例如如果在上图的完全二叉树的g结点接一个k结点，则这个数便不再是完全二叉树）

满二叉树：深度为k且有2^k-1个结点的二叉树称为满二叉树

详细解读：

代码：（C++）

#include 
#include 
using namespace std;
void max_heapify(int arr[], int start, int end) {
    //建立父节点指标和子节点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { //若子节点指标在范围内才做比较
        if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的
            son++;
        if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完毕，直接跳出函数
            return;
        else { //否则交换父子内容再继续子节点和孙节点比较
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
void heap_sort(int arr[], int len) {
    //初始化，i从最后一个父节点开始调整
    for (int i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    //先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}
int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++)
        cout << arr[i] << ' ';
    cout << endl;
    return 0;
}

总结：

​ 堆是一种很好做调整的结构，在算法题里面使用频度很高。常用于想知道最大值或最小值的情况，比如优先级队列，作业调度等场景。堆排序的时间性能是O(logn)

核心思想：

​ 在一个有序表中，每次取目标值与序列中间的值进行比较。若目标值等于值，则查找成功，返回此值的位置；若目标值大于此值，则说明目标值在该查找表的右半区，此时我们往右半区进行查找；若目标值小于此值，则说明目标值在该查找表的右左半区此时我们往左半区进行查找。如此往复，直至查找成功；若无和目标值相等的记录数，则查无此值。

详细解读：

代码：

#include 
#include 

//折半查找,又称为二分查找 ,条件保证要好排序的，不适合应用在频繁的插入操作，因为会打乱顺序
int Binary_Search(int *a,int n,int key)
{ 
        
    int low,high,mid;
    low = 0;    //定义最低下标为记录首位
    high = n;   //记录最高下标为记录末位

    while ( low <= high )
    { 
        
        mid = (low + high) / 2;
        if (key < a[mid]) { 
        
            high = mid - 1;//最高位下标调小 一位
        }
        else if(key > a[mid]){ 
        
            low = mid + 1; //最低下标调整到中位下标大一位
        } 
        else{ 
        
            return mid; //代表就是次位置
        }
    }
    return -1; //没有找到返回-1
}

void main()
{ 
        
    int a[] = { 
        1,2,3,4,5,6,7,8,9,10};

    //需求要查找8, 如果用传统的方式 要查找8次才能得出
    int index;//下标
    index = Binary_Search(a, sizeof(a) / sizeof(int),8);

    if (index == -1)
        printf("没有找到");
    else
        printf("找到了,index为:%d",index);
}

总结：

	二分查找有个很重要的特点，就是不会查找数列的全部元素，而查找的数据量其实正好符合元素的对数，正常情况下每次查找的元素都在一半一半地减少。所以二分查找的[时间复杂度](http://data.biancheng.net/view/2.html)为 `O(log2n)` 是毫无疑问的。当然，最好的情况是只查找一次就能找到，但是在最坏和一般情况下的确要比顺序查找好了很多。 

核心思想：

​ 左右子树与根节点的关系（左子树比根节点都小，右子树比根节点都大）

详细解读：

在BST中搜索一个值是非常简单和高效的。

看上面的树，假设要搜索7这个节点。首先从Root节点出发，我们知道7大于3，所以会走到右子树6，然后因为7也大于6，所以会继续往右子树走，到了9，因为7小于9，所以会向左子树走，走到7，发现7等于7，所以找到要搜索的节点。

代码：

// 这里先定义出节点的结构
class Node
{ 
        
    public int data;
    public Node parent;
    public Node left;
    public Node right;

    public Node(int _data)
    { 
        
        this.data = _data;
    }
}

// 定义二叉搜索树结构
class BST
{ 
        
    private Node root;

    // 这个函数是 private 的，递归调用，插入节点
    private Node RecursionInsert(Node node, int data)
    { 
        
        if (node == null)
        { 
        
            return new Node(data);
        }

        if (data < node.data)
        { 
        
            node.left = RecursionInsert(node.left, data);
            node.left.parent = node;
        }
        else if (data > node.data)
        { 
        
            node.right = RecursionInsert(node.right, data);
            node.right.parent = node;
        }

        return node;
    }

    // 对外开放的 插入 接口
    public void Insert(int data)
    { 
        
        if (root == null)
        { 
        
            root = RecursionInsert(root, data);
        }
        else
        { 
        
            RecursionInsert(root, data);
        }
    }

    // 按层序打印二叉树
    public void LevelOrderTraversal()
    { 
        
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);

        while (q.Count > 0)
        { 
        
            Node currNode = q.Dequeue();

            if (currNode.left != null)
            { 
        
                q.Enqueue(currNode.left);
            }

            if (currNode.right != null)
            { 
        
                q.Enqueue(currNode.right);
            }
            // 括号里面是父节点的值
            string msg = string.Format("{0}({1})", currNode.data, currNode.parent != null ? currNode.parent.data.ToString() : "null");
            Debug.Log(msg);
        }
    }
}

// 创建一个二叉搜索树
class Program
{ 
        
    /* Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 */

    static void Main(string[] args)
    { 
        
        BST bst = new BST();
        bst.Insert(50);
        bst.Insert(30);
        bst.Insert(20);
        bst.Insert(40);
        bst.Insert(70);
        bst.Insert(60);
        bst.Insert(80);

        bst.LevelOrderTraversal();
    }
}

总结

二叉查找树查找成功的平均查找长度为: ASL = [ (n+1)/n] * log2 (n+1) - 1 [公式1] 其时间复杂度是: O (log2 (n))

核心思想：

打扑克＋遍历，打过扑克的朋友对于理解这个排序应该是手到擒来的，我们在摸牌阶段要不断调整牌的顺序，每次摸一张牌查到原来序列当中，其操作流程就是与每一张牌比大小然后放在比它大的牌前面。

详细解读：

代码:

void insertion_sort(int arr[],int len){
        for(int i=1;i=0) && (key