vlambda博客
学习文章列表

 算法具有的重要特征 

1.有穷性：算法有穷性是指算法必须能在执行有限个步骤之后终止；

2.确切性：算法每一步骤必须有确切定义；

3.输入项：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

4.输出项：一个算法有一个或多个输出，以反映对输入数据加工后的结果，没有输出的算法毫无意义；

5.可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成也称之为有效性。

 Python基础算法 

1.冒泡排序

冒泡排序也是一种简单直观的排序算法。重复地走访过要排序的数列，一次比较两个元素，如果顺序错误就交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2.插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但原理是最容易理解，插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据在已排序序列中从后向前扫描，找到相应位置并插入。插入排序和冒泡排序一样也有一种优化算法叫做拆半插入。

3.希尔排序

希尔排序也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的：插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

4.归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法Divide and 的一个非常典型的应用。作为一种典型的分而治之思想的算法应用，归并排序的实现有两种方法：自上而下的递归；自下而上的迭代；

5.快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他算法更快，因为它的内部循环可以在大部分的架构上很有效率地被实现出来。快速排序使用分治法策略来把一个串行分为两个子串行。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上快速排序应该算是在冒泡排序基础上的递归分治法。

6.堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

7.计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

8.桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：在额外空间充足的情况下，尽量增大桶的数量，使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中，同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

9.基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串和特定格式的浮点数，所以基数排序也不是只能使用于整数。