数据结构算法全解析之算法性能衡量的好坏

排序问题一直是计算机还有面试中常见到的知识点，排序算法的好坏能影响到系统的性能，本文将循序渐进、图文并茂的方式讲解常见的排序算法，然后分析各算法的时间复杂度、空间复杂度等情况，之后结合实际应用讲解面试中常问的点。章节主要细分如下：

尺有所短,寸有所长 ——算法性能衡量的好坏
柿子先挑软的捏——基础排序算法
直挂云帆济沧海——排序算法进阶
纸上得来终觉浅，绝知此事要躬行——排序算法性能比较与实际应用
什么是算法？我经常问自己，如何用一句最简短的话来讲解算法是什么？先 po 一段官方的解读：

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

白话来说，算法就是能解决问题，处理数据的的指令，在你给予输入，然后给出正确的结果，处理这过程的方法就是我们所理解的算法；而解决问题的算法有好有坏，我们需要使用一个公认的标准去衡量这个算法的优劣，也就是我们所知道的时间与空间复杂度。

1. 时间复杂度

时间复杂度，顾名思义就是衡量算法所消耗的工作量，我们假设计算机运行一行代码需要执行一次计算。那下面代码则需要执行 2 次运算。

    public int TCool() {
      int i = 1+2; // 需要执行 1 次
      return i; // 需要执行 1 次
    }

下面这段代码则需要执行（n+1 + n+1） = 2n+2 次运算

public int TCool() {
  for (int i = 0; i < n ;i++) { // 需要执行（n+1）次
    System.out.printf("hello t-cool\n"); // 需要执行 n 次
  }
  return 0; // 需要执行 1 次
}

所以我们把算法需要执行的次数用函数 T(n)来表示，此时为了估算算法需要的运行时间，我们需要引入时间复杂度的概念。

算法的时间复杂度，用来度量算法的运行时间，记作: T(n) = O(f(n))。它表示随着 输入大小 n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述。如果不好理解很抽象，那笔者用函数进行直观的描述，函数 f(n) = n^2，和 T(n) = n+2,从图中可以看出，当 n > 2 的时候，函数 f(n) 的增长速度永远大于 T(n)，f(n)则是函数 T(n)的上界，哪我们就可以记着 T(n)的时间复杂度为 O(f(n))，读作 BIG O；那肯定有同学会问，那 n4 都是属于 T(n)的上界，他们也算是他的时间复杂度吗？答案是对的，他们同样可以作为函数 f(n)的时间复杂度，但是相对而言 n^2 是最接近我们的，所以时间复杂度使用 O(f(n))来表示；

那么到这里，肯定小伙伴会问？如何得到函数 T(n)的时间复杂度函数 f(n)呢？

学过数学的都知道，常数项 C 对一个函数的增长速度影响不是很大，当 T(n) = 等于常数 c 的时候，我们认为这个函数的时间复杂度是 O(1)，如果

比如： T(n) = 1 ---> 对应的时间复杂度是 O(1)
T(n) = n + c --- > 对应的时间复杂度是 O(n)
当指数是高次项的时候，函数会受到较大的影响，我们以前数学考试经常会让我们作比较 n3 次方进行比较，n2 对函数的影响：

比如：
T(n) = n^3 + n^2 + c -----> 时间复杂度是 O(n ^ 3)，
综合起来，我们对于一个函数的时间复杂度的处理原则是：不要低阶项，只要高阶项，且忽略高阶项的系数，官方说法叫大 O 推导法。

说到这里，其实，由执行次数得到时间复杂度对于我们来说已经没有难度，真正难的在于我们怎么通过算法分析与数学归纳运算得到 T(n)。下面将总结规则，简单的分成四类，加深读者的记忆：

对于嵌套循环，循环体的时间复杂度是 O(n)，循环次数为 m，则时间复杂度是 O(n_m)。如：下面代码的时间复杂度是 O(n _ 1) = O(n)

public void TCool(int n) {
  for (int i = 0; i < n ;i++) {  // 循环次数 n
    System.out.printf("hello T-Cool"); // 循环体时间复杂度是 O(1)
  }
}

对于多层嵌套，外层循环的时间复杂度是 O(n)，内层分别是 O(a),O(b)……，那么总的时间复杂度是 O(n * a * b* ……)；如下，总的时间复杂度是 O(n * n *1)。

public void TCool() {
  for(int j = 0; j < n;j++) { //循环次数 n
    for (int i =0 ;i < n ;i++){ // 循环次数 n
          System.out.printf("hello T-Cool"); // 循环体时间复杂度是 O(1)
    }
  }
}

对于条件判断语句，总的时间复杂度是其中时间复杂度最大的路径的实际复杂度

对于顺序执行语句，总的时间复杂度是其中最大的时间复杂度的时间复杂度

时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，要深入函数进行分析。

2. 空间复杂度

前面对于时间复杂度有所了解之后，空间复杂度就相对更容易理解了，空间复杂度是我们对于算法在运行时对于空间临时占用大小的一个度量，它同时间复杂度一样，只是对于趋势的度量。下面讲解具体的例子。

空间复杂度为 O(1)，即算法执行所需要的临时空间不随着每个变量 n 的大小变化而变化，那么我们认为空间复杂度为 O(1)。

举例如下：

int tCoolOne = 1;
int tCoolOne = 2;
int cCoolSum = tCoolOne + tCoolTwo;

代码中的变量所分配的大小空间都是不会因为数据量的增多而增大，因此我们认为他的空间复杂度是 O(1)。

空间复杂度为 O(N)，类比可知，当我们所分配的空间大小随着变量增大就增大，如下举例：

int[] tCoolNum = new int[n]; // n 是变量

3. 排序算法的稳定性

为了不让读者陷于一些常见的术语的理解中，笔者会尽量简短的介绍一些基本的概念。下面介绍的是关于排序算法中会涉及到的术语——算法的稳定性。

那什么是算法的稳定性呢，简短的理解，就是一种序列排序之后，序列中数的相对位置保持不变，那么我们把这个算法认为为是稳定的，相反亦然。