算法1：概述与排序算法
1.概述
1.1 简介
1.2 算法效率的衡量
1.2.1 时间复杂度
1.2.2 空间复杂度：
1.3 常见的算法设计方法：
2.排序算法：
2.1 总结：
2.2 冒泡排序
2.2.1冒泡排序
2.2.2鸡尾酒排序
2.3 选择排序
2.4 插入排序：
2.4.1 插入排序:
2.4.2 二分插入排序
2.5 希尔排序
2.6 归并排序
2.7 快速排序
2.8 堆排序
2.9 计数排序
2.10 桶排序
2.11 基数排序
1.概述：
1.1 简介：
算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。对于同一个问题的解决，可能会存在着不同的算法，为了衡量一个算法的优劣，提出了空间复杂度与时间复杂度这两个概念。
1.2 算法效率的衡量
时间复杂度是一个函数，它定性描述了该算法的运算时间。复杂度越低，执行时间越短，程序越高效。
空间复杂度是对一个算法在运算过程中临时占用存储空间大小的量度。占用空间越小，复杂度越低。
两者互为补充，很多情况下以时间换空间、以空间换时间。
1.2.1 时间复杂度：
时间复杂度常大O符号表述，即大O表示法。
算法效率严重依赖于操作(Operation)数量，在判断时首先关注操作数量的最高次项，操作数量的估算可以作为时间复杂度的估算。如下的例子：
O(5) = O(1) //比如说hash算法，不考虑冲突的情况下，不管数据量多大都是查找一次
O(2n + 1) = O(2n) = O(n) //比如说遍历数组
O(n^2 + n + 1) = O(n^2) //比如说冒泡排序，n个数需要扫描n^2
O(3n^3+1) = O(3n^3) = O(n^3)
O( 1 ) < O( log n ) < O( n ) < O( n log n ) < O( n^2 ) < O( n^3 ) < O( 2^n ) < O( n! ) < O( n^n )
1.2.2 空间复杂度：
一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。（计算机的硬件条件越来越好，相对于时间复杂度不是那么重要了）
一个算法所需的存储空间用f(n)表示：S(n)=O(f(n)) n为问题规模，f(n)为在问题规模为n时所占用存储空间的函数
1.3 常见的算法设计方法：
递推法：通常是通过前面的⼀些项来得出序列中的指定项的值（例如找规律，第n个数为多少）
递归法：函数直接，间接调用自身
穷举法：或称为暴力破解法（例如暴力破解密码）
贪心算法：一步一步地进行，每一步都选择最优解。
分治法：把⼀个复杂的问题分成两个或更多的相同或相似的子问题。
动态规划法：类似分治法（例如公司组织架构层层上报）
迭代法：是一种不断用变量的旧值递推新值的过程
分⽀界限法：基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进⾏搜索。
回溯法：按选优条件向前搜索。当探索到某步时，发现原先选择并不优，就退回⼀步重新选择。
2.排序算法：
2.1 总结：
稳定：如果a=b，a原本在b前面，排序之后a仍然在b的前⾯；
不稳定：如果a=b，a原本在b的前面，排序之后a可能会出现在b的后面；
内排序：所有排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进⾏；
2.2 冒泡排序
2.2.1冒泡排序
没什么可说的。
2.2.2鸡尾酒排序
又称为双向冒泡排序，减少了访问次数
最好情况（数组本来是有序的）：时间复杂度为O(n)
最坏情况：时间复杂度为O(n^2)
2.3 选择排序
工作原理：每次从待排序的数据元素中选出最小的元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找最小元素，追加到已排序的序列的末尾。以此类推，直到待排序的数据元素的个数为0
无论什么数据进去都是O(n^2)的时间复杂度，所以用到它的时候，数据规模越小越好。（同插入排序相比，选择排序是不稳定的）
2.4 插入排序：
2.4.1 插入排序:
在已排序序列中从后向前扫描，伺机插入未排序数据。
2.4.2 二分插入排序
寻找插入位置的时候，使用二分法提升性能。
2.5 希尔排序
希尔排序算是对插入排序的一种改进。
插入排序有以下两个特点：
1.当序列的个数比较少时，直接插入排序效率高
2.如果序列本身就是基本有序，那么直接插入排序效率高
插入排序的核心代码
核心思想：将整个序列按照相距某个“增量”进行拆分，然后逐个对子序列进行直接插入排序，使得得到的结果基本有序，最后对基本有序的序列进行一次直接插入排序，使得整个序列有序
