内容检索

数据结构和算法概述
算法分析
排序算法
线性表(#)
符号表(#)
树(#)
堆(#)
优先队列(#)
并查集(#)
图(#)

章节	小节	知识点	具体内容和应用实例
0 数据结构和算法的介绍	数据结构的介绍	逻辑结构	线性结构
		逻辑结构	非线性结构
		物理结构	顺序存储结构
		物理结构	链式存储结构
	算法的介绍
1 数据结构	数组	数组的介绍	数组相关的算法题
	队列	队列的介绍
		使用数组模拟队列
		使用数组模拟循环队列
	链表	链表的介绍
		单链表	单链表的介绍
			单链表的增删改查，顺序插入
			单链表的算法题
		双向链表	双向链表的介绍
		双向链表	双向链表的增删改查，顺序插入
		单项环形链表	单项环形链表的应用实例
		Josephu 问题	使用单项环形链表解决约瑟夫问题
	栈	栈的介绍
		栈的应用场景
		关于栈的算法题
		基于栈实现前缀、中缀及后缀表达式（逆波兰表达式）	前缀表达式（波兰表达式）
			中缀表达式
			后缀表达式（逆波兰表达式）
			中缀表达式转后缀表达式的实现
	哈希表	哈希表的基本原理	使用数组+链表实现一个哈希表
	树	二叉树	（1）二叉树的概念
			（2）二叉树遍历的说明
			（3）二叉树遍历的前序、中序及后续遍历的实现
			（4）二叉树中查找指定节点
			（5）二叉树中删除指定节点
		顺序存储二叉树	（1）顺序存储二叉树的概念
		顺序存储二叉树	（2）顺序存储二叉树的遍历
		线索化二叉树	（1）线索化二叉树的概念
			（2）线索化二叉树的分析
			（3）线索化二叉树的实现
			（4）线索化二叉树的遍历
		二叉排序树	（1）二叉排序树的介绍及概念
			（2）二叉排序树的实现及遍历
			（3）二叉排序树的删除
		霍夫曼树	（1）霍夫曼树的介绍及概念
			（2）霍夫曼树的实现
			（3）霍夫曼编码的实例
		平衡二叉树（AVL 树）	（1）平衡二叉树的介绍及概念
			（2）平衡二叉树的左旋实现
			（3）平衡二叉树的右旋实现
			（4）平衡二叉树的双旋转实现
		B-Tree（B树）、 B+ Tree（B+树）、 B* Tree（B*树）	（1）B-Tree 的介绍及概念
			（2）B-Tree 的原理及实现
			（3）B+ Tree 的介绍及概念
			（4）B* Tree 的介绍及概念
	图	图的基本介绍
		图的常用概念
		图的实现
		图的深度优先算法介绍及实现
		图的广度优先算法介绍及实现
2 算法设计	数组	数组的介绍	数组相关的算法题

0 数据结构与算法设计

数据结构是一门研究非数值计算的程序设计问题的操作对象，以及它们之间的关系和操作问题的学科。即数据结构就是把数据元素按照一定的关系组织起来的集合，用来组织和存储数据。

0.1 数据结构分类

传统上，我们可以把数据结构分为逻辑结构和物理结构两大类。

逻辑结构分类

逻辑结构是从具体问题中抽象出来的模型，是抽象意义上的结构，按照对象中数据元素之间的相互关系分类，也是我们后面课题中需要关注和讨论的问题。

(a) 【集合结构】：

集合结构中数据元素除了属于同一个集合外，他们之间没有任何其他的关系。

(b)【线性结构】：

线性结构中的数据元素之间存在一对一的关系

©【树形结构】：

树形结构中的数据元素之间存在一对多的层次关系

(d)【图形结构】：

图形结构的数据元素是多对多的关系

物理结构分类

逻辑结构在计算机中真正的表示方式(又称为映像)称为物理结构，也可以叫做存储结构。常见的物理结构有顺序存储结构、链式存储结构。

(a)【顺序存储结构】：

把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的，比如我们常用的数组就是顺序存储结构。

优点：得益于它的数据元素放到地址连续的存储单元里，所以查找和更新速度快
缺点：如果向这种结构中间插入或删除某个元素，需要移动该元素后面的所有元素。

(b)【链式存储结构】：

把数据元素存放在任意的存储单元里面，这组存储单元可以是连续的也可以是不连续的。此时，数据元素之间并不能反映元素间的逻辑关系，因此在链式存储结构中引进了一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。

0.2 算法

算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

在程序中，我们也可以用不同的算法解决相同的问题，而不同的算法的成本也是不相同的。

总体上，一个优秀的算法追求以下两个目标:

花最少的时间完成需求;

占用最少的内存空间完成需求;

【例1】计算 1 到 100 的和。

第一种解法:

public static void main(String[] args) { 
  int sum = 0;
  int n=100;
  for (int i = 1; i <= n; i++) {
    sum += i;
  }
  System.out.println("sum=" + sum);
}

第二种解法:

public static void main(String[] args) {
  int sum = 0;
  int n=100;
  sum = (n+1)*n/2;
  System.out.println("sum="+sum);
}

很明显，第二种算法完成需求，花费的时间更少一些。

【例2】计算 10 的阶乘

第一种解法：

public class Test {
  public static void main(String[] args) {
    //测试，计算10的阶乘
    long result = fun1(10);
    System.out.println(result);
  }
  //计算n的阶乘
  public static long fun1(long n){
    if (n==1){
      return 1;
    }
    return n*fun1(n-1);
  }
}

第二种解法：

public class Test {
  public static void main(String[] args) {
    //测试，计算10的阶乘
    long result = fun2(10);
    System.out.println(result);
  }
  
  //计算n的阶乘
  public static long fun2(long n){
    int result=1;
    for (long i = 1; i <= n; i++) {
      result*=i;
    }
    return result;
  }
}

第一种解法，使用递归完成需求，fun1方法会执行 10 次，并且第一次执行未完毕，调用第二次执行，第二次执行未完毕，调用第三次执行… 最终，最多的时候，需要在栈内存同时开辟 10 块内存分别执行 10 个 fun1 方法。

第二种解法，使用 for 循环完成需求，fun2 方法只会执行一次，最终，只需要在栈内存开辟一块内存执行 fun2 方法即可。

很明显，第二种算法完成需求，占用的内存空间更小。

数据结构

数组、队列、链表、栈、树（二叉树，堆排序，霍夫曼树，平衡树，B树，B+树，）、哈希表（实现：数组+单链表）、图（）

数组

算法设计

递归算法、排序算法（八大排序）、查找算法（线性｜二分｜插值｜黄金分割）、分治算法、动态规划、kmp算法、贪心算法、普里姆（图相关，最小生成树等）、kruskal算法（图相关，加权最小生成树等）、Djikstra算法、Floyd算法、

算法的时、空间复杂度

前面我们已经介绍了，研究算法的最终目的就是如何花更少的时间，如何占用更少的内存去完成相同的需求，并且也通过案例演示了不同算法之间时间耗费和空间耗费上的差异，但我们并不能将时间占用和空间占用量化，因此，接下来我们要学习有关算法时间耗费和算法空间耗费的描述和分析。

有关算法时间耗费分析，我们称之为算法的时间复杂度分析，有关算法的空间耗费分析，我们称之为算法的空间复杂度分析。

时间复杂度分析

我们要计算算法时间耗费情况，首先我们得度量算法的执行时间，那么如何度量呢?

事后分析估算方法

比较容易想到的方法就是我们把算法执行若干次，然后用计时器计时。

public static void test() {
  long strat = System.currentTomeMillis();
  // TODO 待测试程序
  long end = System.currentTomeMillis();
  long excuteTime = end - start;
}

这种统计方法主要是通过设计好的测试程序和测试数据，利用计算机计时器对不同的算法编制的程序的运行时间进行比较，从而确定算法效率的高低。

但是这种方法有很大的缺陷：必须依据算法实现编制好的测试程序，通常要花费大量时间和精力，测试完了如果发现测试的是非常糟糕的算法，那么之前所做的事情就全部白费了，并且不同的测试环境（硬件环境）的差别导致测试的结果差异也很大。

事前分析估算方法

在计算机程序编写前，依据统计方法对算法进行估算，经过总结，我们发现一个高级语言编写的程序程序在计算机上运行所消耗的时间取决于下列因素:

算法采用的策略和方案；
编译产生的代码质量；
问题的输入规模(所谓的问题输入规模就是输入量的多少)；
机器执行指令的速度。

由此可见，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模。如果算法固定，那么该算法的执行时间就只和问题的输入规模有关系了。

我么再次以之前的求和案例为例，进行分析。

第一种解法:

public static void main(String[] args) { 
  int sum = 0; // 执行1次
  int n = 100; // 执行1次
  for (int i = 1; i <= n; i++) {  // 执行 n+1 次
    sum += i; // 执行n次
  }
  System.out.println("sum=" + sum);
}

第二种解法:

public static void main(String[] args) {
  int sum = 0; // 执行1次
  int n = 100; // 执行1次
  sum = (n+1)*n/2; // 执行1次
  System.out.println("sum="+sum);
}

因此，当输入规模为 n 时，

第一种算法执行了 $1+1+(n+1)+n=2n+3$ 次；
第二种算法执行了 $1+1+1=3$ 次

如果我们把第一种算法的循环体看做是一个整体，忽略结束条件的判断，那么其实这两个算法运行时间的差距就是 $n$ 和 $1$ 的差距。

为什么循环判断在【算法1】里执行了 n+1 次，看起来是个不小的数量，但是却可以忽略呢？

我们研究算法复杂度，侧重的是当输入规模不断增大时，算法的增长量的一个抽象（规律），而不是精确地知道需要执行多少次，最重要的就是把核心操作的次数和输入规模关联起来。

关于输入规模 $n$ 的多项式中，随着算法输入规模的增长，常数项和最高次幂的常数系数可以被忽略，我们只关心最高次幂。

算法函数中最高次幂越小，算法效率越高。

时间复杂度

大 O 记法

在进行算法分析时，语句总的执行次数 $T(n)$ 是关于问题规模 $n$ 的函数，进而分析 $T(n)$ 随着 $n$ 的变化情况并确定 $T(n)$ 的量级。算法的时间复杂度，就是算法的时间量度，记作：

$T(n)=O(f(n))$

它表示随着问题规模 $n$ 的增大，算法执行时间的增长率和 $f(n)$ 的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度，其中 $f(n)$ 是问题规模 $n$ 的某个函数。

在这里，我们需要明确一个事情： $执行次数=执行时间$ 用大写 $O()$ 来体现算法时间复杂度的记法，我们称之为大O记法。

一般情况下，随着输入规模 $n$ 的增大， $T(n)$ 增长最慢的算法为最优算法。

有一个存储了n个随机数字的数组，请从中查找出指定的数字。

【最好情况】查找的第一个数字就是期望的数字，那么算法的时间复杂度为 $O(1)$

【最坏情况】查找的最后一个数字，才是期望的数字，那么算法的时间复杂度为 $O(n)$

【平均情况】任何数字查找的平均成本是 $O(n/2)$

最坏情况是一种保证，在应用中，这是一种最基本的保障，即使在最坏情况下，也能够正常提供服务，所以，除非特别指定，我们提到的运行时间都指的是最坏情况下的运行时间。

【常数阶 $O(1)$ 】

一般不涉及循环操作的都是常数阶，因为它不会随着 n 的增长而增加操作次数。例如:

public static void main(String[] args) {
  int n = 100;
  int i = n + 2;
  System.out.println(i);
}

上述代码，不管输入规模 n 是多少，都执行 2 次，根据大O推导法则，常数用 1 来替换，所以上述代码的时间复杂度为 $O(1)$

【线性阶 $O(n)$ 】

一般含有非嵌套循环涉及线性阶（单层 for 循环），线性阶就是随着输入规模的扩大，对应计算次数呈直线增长，例如：

public static void main(String[] args) { 
 for (int i = 1; i <= n; i++) {
   System.out.println(i); 
 }
}

上面这段代码，它的循环的时间复杂度为 $O(n)$ ，因为循环体中的代码需要执行 n 次。

【平方阶 $O(n^2)$ 】

一般嵌套循环（双层 for 循环）属于这种时间复杂度

public static void main(String[] args) {
  
 for (int i = 1; i <=n ; i++) {
   for (int j = 1; j <=n ; j++) {
     System.out.println(i + "\t" + j);
   }
 }
}

上面这段代码， $n=100$ ，也就是说，外层循环每执行一次，内层循环就执行 100 次，那总共程序想要从这两个循环中出来，就需要执行 $100 \times100$ 次，也就是 n 的平方次，所以这段代码的时间复杂度是 $O(n^2)$ .

【立方阶 $O(n^3)$ 】

一般三层嵌套循环属于这种时间复杂度

public static void main(String[] args) {
  for (int i = 1; i <=n ; i++) {
    for (int j = i; j <=n ; j++) {
      for (int m = i; m <=n ; j++) {
        System.out.println(i,j,m);
      }
    }
  }
}

上面这段代码， $n=100$ ，也就是说，外层循环每执行一次，中间循环循环就执行 100 次，中间循环每执行一次，最内层循环需要执行 100 次，那总共程序想要从这三个循环中出来，就需要执行 $100\times 100\times 100$ 次，也就是 $n^3$ ，所以这段代码的时间复杂度是 $O(n^3)$

【对数阶 $O(log \;n)$ 】

如下列程序所示

public static void main(String[] args) {
  int i=1,
  n=100; 
  while(i<n){
    i = i*2;
  }

由于每次 $i\times 2$ 之后，就距离 n 更近一步，假设有 x 个 2 相乘后大于 n，则会退出循环。由于是 $2^x=n$ ，得到 $x=log(2)n$ ，而我们在分析算法时间复杂时只关注增长率，从而可以忽略底数，所以这个循环的时间复杂度为 $O(log \;n)$ 。

【总结】

描述	增长的数量级	说明	举例
常数级别	$O(1)$	普通语句	将两个数相加
对数级别	$O(log \; n)$	二分策略	二分查找
线性级别	$O(n)$	单层循环	找出最大元素
线性对数级别	$O(nlog\;n)$	分治思想	归并排序
平方级别	$O(n^2)$	双层循环	检查所有元素对
立方级别	$O(n^3)$	三层循环	检查所有三元组
指数级别	$O(2^n)$	穷举查找	检查所有子集

他们的复杂程度从低到高依次为：

$O(1)<O(log\;n)<O(n)<O(nlog\;n)<O(n^2)<O(n^3)$

我们的算法，尽可能的追求的是 $O(1)$ ， $O(log \; n)$ ， $O(n)$ ， $O(nlog\;n)$ 这几种时间复杂度，而如果发现算法的时间复杂度为平方阶、立方阶或者更复杂的，那我们可以分为这种算法是不可取的，需要优化。

函数调用的时间复杂度分析

之前，我们分析的都是单个函数内，算法代码的时间复杂度，接下来我们分析函数调用过程中时间复杂度。

【案例一】

public static void main(String[] args) {
  int n=100;
  for (int i = 0; i < n; i++) {
    show(i);
  }
}

private static void show(int i) {
  System.out.println(i);
}

在 main 方法中，有一个 for 循环，循环体调用了 show 方法，由于 show 方法内部只执行了一行代码，所以 show 方法的时间复杂度为 $O(1)$ ，那 main 方法的时间复杂度就是 $O(n)$

【案例二】

public static void main(String[] args) {
  int n=100;
  for (int i = 0; i < n; i++) {
    show(i);
  }
}

private static void show(int i) {
  for (int j = 0; j < n; j++) {
    System.out.println(i);
  }
}

在 main 方法中，有一个 for 循环，循环体调用了 show 方法，由于 show 方法内部也有一个 for 循环，所以 show 方法的时间复杂度为 $O(n)$ ，那 main 方法的时间复杂度就是 $O(n^2)$

【案例三】

public static void main(String[] args) { // O(2n^2)
  int n=100;
  show(n); // O(n)
  for (int i = 0; i < n; i++) { // O(n)
    show(i); // O(n^2)
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      System.out.println(j); // O(n^2)
    }
  }
}

private static void show(int i) { // O(n)
  for (int j = 0; j < i; i++) {
    System.out.println(i); 
  }
}

在 show方法中，有一个 for 循环，所以show方法的时间复杂度为 $O(n)$
在 main方法中，show(n) 这行代码内部执行的次数为 n，第一个 for 循环内调用了 show 方法，所以其执行次数为 $n^2$ $n^{2}$
- 第二个嵌套 for 循环内只执行了一行代码，所以其执行次数为 $n^2$
- 那么 main 方法总执行次数为 $n+n^2+n^2=2n^2+n$ 。
根据大 O 推导规则，去掉 n 保留最高阶项，并去掉最高阶项的常数因子2，所以最终 main 方法的时间复杂度为 $O(n^2)$

空间复杂度分析

Java 中常见内存占用

基本数据类型内存占用情况

数据类型	内存占用字节数
`byte`	1
`short`	2
`int`	4
`long`	8
`float`	4
`double`	8
`boolean`	1
`char`	2

计算机访问内存的方式都是一次一个字节

一个引用（机器地址）需要 8 个字节表示：

例如: Date date = new Date()，则 date 这个变量需要占用 8个字节来表示
创建一个对象，比如 new Date()，除了 Date对象内部存储的数据（例如年月日等信息）占用的内存，该对象本身也有内存开销，每个对象的自身开销是 16 个字节，用来保存对象的头信息。
一般内存的使用，如果不够 8 个字节，都会被**自动填充为 8 字节**
Java 中数组被限定为对象，他们一般都会因为记录长度而需要额外的内存，一个原始数据类型的数组一般需要 24字节的头信息(16个自己的对象开销，4字节用于保存长度以及4个填充字节)再加上保存值所需的内存。

空间复杂度

了解了 Java 的内存最基本的机制，就能够有效帮助我们估计大量程序的内存使用情况。

算法的空间复杂度计算公式记作

$S(n)=O(f(n))$

其中 $n$ 为输入规模， $f(n)$ 为语句关于 $n$ 所占存储空间的函数。

【案例一】：对指定的数组元素进行反转，并返回反转的内容。

算法一：

public static int[] reverseList1(int[] arr){
  int n=arr.length; // 申请4个字节
  int temp; // 申请4个字节
  
  for(int start=0,end=n-1; start<=end; start++,end--){
    temp=arr[start];
    arr[start]=arr[end];
    arr[end]=temp;
  }
  return arr;
}

不管传入的数组大小为多少，始终额外申请 $4+4=8$ 个字节;

算法二：

public static int[] reverse2(int[] arr){
  int n = arr.length; // 申请4个字节
  int[] temp = new int[n]; // 申请n*4个字节+数组自身头信息开销24个字节
  for (int i = n-1; i >=0; i--) {
    temp[n-1-i]=arr[i];
  }
  return temp;
}

$4+4n+24=4n+28$

根据大 O 推导法则，

算法一的空间复杂度为 $O(1)$ ；
算法二的空间复杂度为 $O(n)$

所以从空间占用的角度讲，算法一要优于算法二。

排序算法

冒泡排序 Bubble Sort

冒泡排序(Bubble Sort)，是一种计算机科学领域的较简单的排序算法。

排序前：{3,43,38,5,47,15,36,26,27,2,44,4,50,19,38}

排序后：{2,3,4,5,15,19,26,27,36,38,44,46,47,48,50}

【排序原理】

比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。

【动画演示】

【代码示例】

private static int[] bubbleSort(int[] arr) {
  for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length-i-1; j++) {   // 因为操作 arr[j] 与 arr[j+1] 比较，这里的边界是 arr.length-i-1
      if (arr[j] > arr[j + 1]) { // 比较 与 交换数值
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

【复杂度分析】

冒泡排序使用了双层 for 循环，其中内层循环的循环体是真正完成排序的代码。所以，我们分析冒泡排序的时间复杂度，主要分析一下内层循环体的执行次数即可。

在最坏情况下，也就是假如要排序的元素为 {50,48,47,46,44,38,36,27,26,19,15,5,4,3,2} 逆序，那么：

元素比较的次数为： $(n-1)+(n-2)+(n-3)+...+2+1=((n-1)+1)*(n-1)/2=n^2/2-n/2$

元素交换的次数为： $(n-1)+(n-2)+(n-3)+...+2+1=((n-1)+1)*(n-1)/2=n^2/2-n/2$

总执行次数为： $(n^2/2-n/2)+(n^2/2-n/2)=n^2-n$

按照大 O 推导法则，保留函数中的最高阶项。那么最终冒泡排序的时间复杂度为：

$O(n^2)$

选择排序 Selection Sort

选择排序是一种更加简单直观的排序方法。

排序前：{3,43,38,5,47,15,36,26,27,2,44,4,50,19,38}

排序后：{2,3,4,5,15,19,26,27,36,38,44,46,47,48,50}

【排序原理】

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始（末尾）位置；
然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾（起始）；
以此类推，直到所有元素均排序完毕。（拿出最大或最小，然后在剩余中再拿最大或最小）

【动画演示】

【代码示例】

private static int[] selectionSort(int[] arr) {
    int length = arr.length;
    int minIndex, temp;
    for (iny i = 0; i < length - 1; i++) {
        minIndex = i;	// 假设本轮循环的初始索引是最小数的索引
        for (int j = i + 1; j < length; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
      	// 将【最小数的索引】与【本轮循环的初始索引】交换
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

【复杂度分析】

选择排序使用了双层 for 循环，其中外层循环完成了数据交换，内层循环完成了数据比较。所以我们分别统计数据交换次数和数据比较次数：

元素比较的次数为： $(n-1)+(n-2)+(n-3)+...+2+1=((n-1)+1)*(n-1)/2=n^2/2-n/2$

元素交换的次数为： $n-1$

总执行次数为： $(n^2/2-n/2)+(n-1)=n^2/2+n/2-1$

按照大 O 推导法则，保留函数中的最高阶项。那么最终选择排序的时间复杂度为：

$O(n^2)$

插入排序 Insertion sort

插入排序(Insertion sort)是一种简单直观且稳定的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

排序前：{3,43,38,5,47,15,36,26,27,2,44,4,50,19,38}

排序后：{2,3,4,5,15,19,26,27,36,38,44,46,47,48,50}

【排序原理】

插入排序把所有的元素分为两组，【已经排序】的和【未排序】的

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。

【动画演示】

【代码示例】

private static void insertionSort(int[] arr) {
    int length = arr.length;
    int preIndex, current;
    for (int i = 1; i < length; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

【复杂度分析】

插入排序使用了双层循环，其中内层循环的循环体是真正完成排序的代码。所以，我们分析插入排序的时间复杂度，主要分析一下内层循环体的执行次数即可。

在最坏情况下，也就是假如要排序的元素为 {50,48,47,46,44,38,36,27,26,19,15,5,4,3,2} 逆序，那么：

元素比较的次数为： $(n-1)+(n-2)+(n-3)+...+2+1=((n-1)+1)*(n-1)/2=n^2/2-n/2$

元素交换的次数为： $(n-1)+(n-2)+(n-3)+...+2+1=((n-1)+1)*(n-1)/2=n^2/2-n/2$

总执行次数为： $(n^2/2-n/2)+(n^2/2-n/2)=n^2-n$

按照大 O 推导法则，保留函数中的最高阶项。那么最终插入排序的时间复杂度为：

$O(n^2)$

希尔排序 Shell Sort

之前我们学习的冒泡排序，选择排序还有插入排序，他们在最坏情况下的时间复杂度都是 $O(n^2)$ ，而平方阶通过我们之前学习算法分析我们知道，随着输入规模的增大，时间成本将急剧上升。所以这些基本排序方法不能处理更大规模的问题，接下来我们学习一些高级的排序算法，争取降低算法的时间复杂度最高阶幂。

希尔排序 (Shell Sort) 是插入排序的一种，又称“缩小增量排序”，是插入排序的更高效的改进版本。

排序前：{9,1,2,5,7,4,8,6,3,5}

排序后：{1,2,3,4,5,5,6,7,8,9}

【排序原理】

选定一个增长量 gap，按照增长量 gap 作为数据分组的依据，对数据进行分组；
对分好组的每一组数据完成插入排序；
减小增长量，最小减为 1，重复第 2 步操作。

【增长量 gap】的值采用以下规则：

// 初始gap等于数组长度的一半
// 每次迭代后gap的大小都是原来的1/2
// 直到gap=1
for(int gap=array.length; gap>0 ; gap=gap/2) {
  // TODO: 内层的插入排序
}

【算法图解】

【代码示例】

private static int[] shellSort(int[] arr) {
    int length = arr.length;
    for(int gap = length/2; gap > 0; gap = gap/2) {
        // 注意：这里和图片展示的不一样，实际操作是多个分组交替执行
        for(int i = gap; i < length; i++) {
            int j = i; // j与有序数组的末尾索引有关
            int current = arr[i];
            while(j - gap >= 0 && current < arr[j - gap]) {
                 arr[j] = arr[j - gap];
                 j = j - gap;
            }
            arr[j] = current;
        }
    }
    return arr;
}

【复杂度分析】

希尔排序是在插入排序的基础上进行的一中改进的算法。

希尔排序是将一个原序列分成几个子序列，对于每个子序列来所都进行一次插入排序，而依据不同的子序列划分大小，最后子序列为1时，此时插入排序跟原来的插入排序就是一模一样的了，只不过现在的队列比原来的要有序的多。

所以希尔排序就是将原序列进行了一些整理，将其变得有序一些，而我们都知道，对于插入排序这个 $O(n^2)$ 级别的算法来说，越是有序的序列，它所需要的时间越少，甚至在某些情况下可以逼近 $O(n)$ ，这就是希尔排序对于插入排序的改良。所以希尔排序的时间复杂度为：

$O(n) < O(f(n)) < O(n^2), \text{平均为 }O(n^{1.25})$

归并排序 Merge Sort

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

排序前：{8,4,5,7,1,3,6,2}

排序后：{1,2,3,4,5,6,7,8}

【排序原理】

「分」尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是 1为止；
「治」将相邻的两个子组进行排序并合并成一个有序的大组；
不断的重复步骤 2，直到最终只有一个组为止。

【算法图解】

【代码示例】

public static void mergeSort(int[] array) {
	if (array == null || array.length <= 1) {
		return;
	}
  sort(array, 0, array.length - 1);
}

private static void sort(int[] array, int left, int right) {
	if (left >= right) {
		return;
	}
	int mid = left + ((right - left)/2);
	sort(array, left, mid);	// 对左侧子序列进行递归排序
	sort(array, mid + 1, right);	// 对右侧子序列进行递归排序
	merge(array, left, mid, right);	// 合并
}

private static void merge(int[] array, int left, int mid, int right) {
	int[] temp = new int[right - left + 1];
  // 【归并的关键】就在于以下三个指针的操作
	int i = 0;	// 指针：指向temp[]第一个元素
	int p1 = left; // 指针：指向左子组第一个元素
	int p2 = mid + 1;	// 指针：指向右子组第一个元素
  
	// 1.比较左右两部分的元素，哪个小，把那个元素填入temp[]中
	while (p1 <= mid && p2 <= right) {
		temp[i++] = (array[p1] < array[p2]) ? array[p1++] : array[p2++];
	}
  
	// 2.上面的循环退出后，把剩余的元素依次填入到temp中。以下两个while只有一个会执行
	while (p1 <= mid) {
		temp[i++] = array[p1++]; // 如果p1的指针没有到mid，将剩余的元素放入temp[]
	}
	while (p2 <= right) {
		temp[i++] = array[p2++]; // 如果p2的指针没有到rigth，将剩余的元素放入temp[]
	}
  
	// 3.把最终的排序的结果复制给原数组
	for (i = 0; i < temp.length; i++) {
		array[left + i] = temp[i];
	}
}

【复杂度分析】

归并排序是分治思想的最典型的例子。

树状图来描述归并，如果一个数组有 8 个元素，那么它将每次除以 2 找最小的子数组，共拆分 $log(8)$ 次，值为 3，所以树共有 3 层。那么自顶向下第 $k$ 层有 $2^k$ 个子数组，每个数组的长度为 $2^{(3-k)}$ ，归并最多需要 $2^{(3-k)}$ 次比较。因此每层的比较次数为 $2^k \times 2^{(3-k)}=2^3$ ，那么 3 层总共为 $3\times 2^3$ 。

假设元素的个数为 $n$ ，那么使用归并排序拆分的次数为 $log_2(n)$ ，所以共 $log_2(n)$ 层，那么使用 $log_2(n)$ 替换上面 $3\times 2^3$ 中的 3 这个层数，最终得出的归并排序的时间复杂度为： $log_2(n)* 2^{log_2(n)}=log_2(n)*n$ 。根据大 O 推导法则，忽略底数，最终归并排序的时间复杂度为

$O(nlog\;n);$

【归并排序的缺点】

需要申请额外的数组空间 temp[]，导致空间复杂度提升，是典型的以空间换时间的操作。

希尔排序和归并排序在处理大批量数据时差别不是很大。

快速排序 Quick Sort

快速排序是对冒泡排序的一种改进。

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

排序前：{8,4,5,7,1,3,6,2}

排序后：{1,2,3,4,5,6,7,8}

【排序原理】

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

首先设定一个分界值，通过该分界值将数组分成左右两部分；
将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；
然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理；
重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

【算法图解】

【代码示例】

private static void initQuickSort(int arr[]) {
  int left = 0;
  int right = arr.length - 1;
  int[] result = quickSort(arr, left, right);
}

private static int[] quickSort(int[] arr, int left, int right) {
  int partitionIndex;

  if (left < right) {
    partitionIndex = partition(arr, left, right);
    quickSort(arr, left, partitionIndex-1);
    quickSort(arr, partitionIndex+1, right);
  }
  return arr;
}
 
private static int partition(int[] arr, int left, int right) {	// 分区操作
  int pivot = left;	// 设定基准值（pivot）
  int index = pivot + 1;
  for (int i = index; i <= right; i++) {
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index);
      index++;
    }
  }
  swap(arr, pivot, index - 1);
  return index-1;
}
 
private static void swap(int[] arr, int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

【快速排序和归并排序的区别】
快速排序是另外一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立的排序。快速排序和归并排序是互补的：

归并排序将数组分成两个子数组分别排序，并将有序的子数组归并从而将整个数组排序，而快速排序的方式则是当两个数组都有序时，整个数组自然就有序了。
在归并排序中，一个数组被等分为两半，归并调用发生在处理整个数组之前，在快速排序中，切分数组的位置取决于数组的内容，递归调用发生在处理整个数组之后。

【时间复杂度分析】

快速排序的一次切分从两头开始交替搜索，直到 left 和 right 重合（仅扫描一遍）。因此，一次切分算法的时间复杂度为 $O(n)$ ，但整个快速排序的时间复杂度和切分的次数相关。

最优情况：每一次切分选择的基准数字刚好将当前序列等分（在序列中间）。如果我们把数组的切分看做是一个树，那么上图就是它的最优情况的图示，共切分了 $log\;n$ 次，所以，最优情况下快速排序的时间复杂度为 $O(nlog\;n)$ ；

每一次切分选择的基准数字是当前序列中最大数或者最小数，这使得每次切分都会有一个子组，那么总共就得切分 n 次。所以，最坏情况下，快速排序的时间复杂度为 $O(n^2)$ ；

平均情况：每一次切分选择的基准数字不是最大值和最小值，也不是中值，这种情况我们也可以用数学归纳法证明，快速排序的时间复杂度为 $O(nlog\;n)$

$O(nlog\;n) < O(f(n)) < O(n^2), \text{平均为 }O(nlog\;n)$

计数排序 Counting Sort

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

【排序原理】

找出待排序的数组中最大和最小的元素；
统计数组中每个值为 i 的元素出现的次数，存入数组 int[] C 的第 i 项；
对所有的计数累加（从 C[] 中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1。

【动画演示】

【代码示例】

public static void countingSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        int length = array.length;

        int max = array[0];
        int min = array[0];
        for (int i = 0; i < length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
            if (min > array[i]) {
                min = array[i];
            }
        }
        // 最大最小元素之间范围[min, max]的长度
        int offset = max - min + 1;
        // 1. 计算频率，在需要的数组长度上额外加1
        int[] count = new int[offset + 1];
        for (int i = 0; i < length; i++) {
            // 使用加1后的索引，有重复的该位置就自增
            count[array[i] - min + 1]++;
        }
        // 2. 频率 -> 元素的开始索引
        for (int i = 0; i < offset; i++) {
            count[i + 1] += count[i];
        }

        // 3. 元素按照开始索引分类，用到一个和待排数组一样大临时数组存放数据
        int[] aux = new int[length];
        for (int i = 0; i < length; i++) {
            // 填充一个数据后，自增，以便相同的数据可以填到下一个空位
            aux[count[array[i] - min]++] = array[i];
        }
        // 4. 数据回写
        for (int i = 0; i < length; i++) {
            array[i] = aux[i];
        }
    }

【算法分析】

当输入的元素是 n 个 0～k 之间的整数时，它的运行时间是 $O(n + k)$ 。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组 C[] 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上 1 ），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

根据大 O 推导法则，最终计数排序的时间复杂度为

$O(n)$