算法详解

近日，笔者对算法进行了一些总结(参考了很多大牛的博客)

众所周知，在开发的过程中，大家约遇到很多的逻辑处理问题，从而写一些算法来提高程序的运行效率。，那么评价一个算法的优劣是从那几个方面来进行的呢？下面，笔者从以下几个方面来阐述：

1、时间复杂度：

 所谓的时间复杂度，也就是执行一个算法所需要的时间，一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做

　　公式：T(n)=Ο(f(n))

2、空间复杂度：

指的是执行一个算法，在计算机中所需要的内存空间的大小。计算方式和时间复杂度类似。

以上两点，在程序运行中，值越小越好(做测试时，我们可以打印一个算法执行所需要的时间)

3、稳定性：

列举，如存在一个算法，对集合中的数进行排序，有且存在(a=b)，在排序之前(a在b之前)，排序之后a仍然在b之前

4、不稳定性：

与算法的稳定性相反，排序之后，改变了a与b的位置。

5、内排序：

所有的排序操作，是在内存中进行。

6、外排序：

由于数据量比较大，因此把数据存放在磁盘当中，通过磁盘和数据传输才能进行。

 

1、直接插入排序法：

原理：从待排序的数中选出一个来，插入到前面的合适位置

        思路：从待排序的数组中找出一个，插入到前面的位置，插入方面比较耗时，当数组中的数字是第一个的时候，那么使用中间变量来记录，为第二个数字的时候，对比前一个数，如果小，那么互换，继续比较直到找到正确的位置。

 

二、选择排序（O(n2)、不稳定）
与直接插入排序正好相反，选择排序是从待排序的数中选出最小的放在已经排好的后面，算法耗时主要在选择上。

。

通过循环，找到数组中最小数的下标(k值记录)，与当前位置i互换数据即可。

3、快速排序（O(nlogn)、不稳定）

快速排序简称快排，是一种比较快的排序，适合基本无序的数据，为什么这么说呢？下面我说下快排的思路：

设置两个指针：i和j，分别指向第一个和最后一个，i像后移动，j向前移动，选第一个数为标准（一般这样做，当然快排的关键就是这个“标准”的选取），从后面开始，找到第一个比标准小的数，互换位置，然后再从前面，找到第一个比标准大的数，互换位置，第一趟的结果就是标准左边的都小于标准，右边的都大于标准（但不一定有序），分成两拨后，继续递归的使用上述方法，最终有序！代码如下：