排序算法基本概念

对于评述算法优劣术语的说明

1. 稳定：如果a原本在b的前面，若a=b，排序之后a仍然在b前面。
2. 不稳定：如果a原本在b的前面，若a=b，排序之后a可能会在b的后面。
3. 内排序：所有排序操作都在内存中完成。
4. 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
5. 时间复杂度：一个算法执行所消耗的时间。
6. 空间复杂度：运行完一个程序所需内存的大小。

时间复杂度

时间复杂度的定义 T(n)=O(f(n))

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，
若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，
则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的
渐进时间复杂度(O是数量级的符号 )，简称时间复杂度。

时间复杂度的计算步骤

1. 计算出基本操作的执行次数T(n)
   基本操作即算法中的每条语句（以;号作为分割），语句的执行次数也叫做语句的频度。
   在做算法分析时，一般默认为考虑最坏的情况。
2. 计算出T(n)的数量级
   求T(n)的数量级，只要将T(n)进行如下一些操作，忽略常量、低次幂和最高次幂的系数。
   令f(n)=T(n)的数量级。
3. 用大O来表示时间复杂度
   当n趋近于无穷大时，如果lim(T(n)/f(n))的值为不等于0的常数，则称f(n)是T(n)的同数量级函数。
   记作T(n)=O(f(n))。

计算一下时间复杂度

for(i=1;i<=n;i++)   //循环了，当然是O(n^2)
       for(j=1;j<=n;j++)
           s++;

PS：这里的执行次数为 n*n 次 ，所以时间复杂度为O(n^2)。

for(i=1;i<=n;i++)
       for(j=1;j<=i;j++)
           s++;

PS：这里的执行次数为 (1+2+3+…+n)≈(n^2)/2次，所以时间复杂度为O(n^2)。

空间复杂度

空间复杂度定义 S(n)=O(f(n))

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。
比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。
而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。

各种算法的总结

总结：接着我会使用 js 来做各种排序算法的分析。 

参考文档：
js十大排序算法
算法时间复杂度的计算 [整理]
如何计算时间复杂度