第1部分：算法基本概念

  • 算法的定义：算法是解决特定问题求解步骤的描述，在计算机中为指令的有限序列，并且每条指令表示一个或多个操作
  • 算法的特性：有穷性、确定性、可行性、输入、输出

  • 算法的设计的要求：正确性、可读性、健壮性、高效率和低存储量需求

    第2部分：时间复杂度的推算

  • 推导大O阶：

    1. 用常数1取代运行时间的所有加法常数
    2. 在修改后的运行次数函数中，只保留最高阶次
    3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数

得到的结果就是大O阶

第3部分：背包问题

3.1 0-1背包问题

  • 题目

有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是Ci，得到 的价值是Wi。求解将哪些物品装入背包可使价值总和最大。

  • 基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不 放。 用子问题定义状态：即F[i, v]表示前i件物品恰放入一个容量为v的背包可以 获得的最大价值。则其状态转移方程便是：F[i,v]=max{F[i-1,v],F[i-1,v-Ci]+Wi}。这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生 出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化 为一个只和前i-1件物品相关的问题。如果不放第i件物品，那么问题就转化
为“前i-1件物品放入容量为v的背包中”，价值为F[i-1,v]；如果放第i件物 品，那么问题就转化为“前i - 1件物品放入剩下的容量为v - Ci的背包中”， 此时能获得的最大价值就是F[i - 1; v - Ci]再加上通过放入第i件物品获得的价值Wi。
伪代码如下：

  1. F[0,0...V] = 0
  2. for i=1 to N
  3.     for v=Ci to V
  4.       F[i,v] = max{F[i-1,v],F[i-1,v-Ci]+Wi}
  • 优化空间复杂度

以上方法的时间和空间复杂度均为O(V N)，其中时间复杂度应该已经不能 再优化了，但空间复杂度却可以优化到O(V )。 先考虑上面讲的基本思路如何实现，肯定是有一个主循环i = 1...N，每次 算出来二维数组F[i, 0...V ]的所有值。那么，如果只用一个数组F[0...V ]，能不能保证第i次循环结束后F[v]中表示的就是我们定义的状态F[i, v]呢？F[i, v]是由F[i - 1, v]和F[i - 1, v - Ci]两个子问题递推而来，能否保证在推F[i, v]时（也 即在第i次主循环中推F[v]时）能够取用F[i - 1, v]和F[i - 1, v - Ci]的值呢？事
实上，这要求在每次主循环中我们以v = V...0的递减顺序计算F[v]，这样才能保 证推F[v]时F[v - Ci]保存的是状态F[i - 1, v - Ci]的值。伪代码如下：

  1. F[0...V] = 0
  2. for i = 1 to N
  3.     for v = V to Ci
  4.         F[v] = max{F[v],F[v - Ci] +Wi}

3.2 完全背包问题

  • 题目

有N种物品和一个容量为V的背包，每种物品都有无限件可用。放入第i种 物品的耗费的空间是Ci，得到的价值是Wi。求解：将哪些物品装入背包，可使 这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

  • 基本思路

这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从 每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、 取1件、取2件……直至取[V /Ci]件等很多种。
如果仍然按照解01背包时的思路，令F[i,v]表示前i种物品恰放入一个容量 为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：F[i; v] = max{F[i-1, v-kCi] + kWi | 0<= kCi <= v}，这跟01背包问题一样有O(V N)个状态需要求解，但求解每个状态的时 间已经不是常数了，求解状态F[i, v]的时间是O(v/ Ci )，是比较大的。 将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01 背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是要 试图改进这个复杂度。

  • 一个简单有效的优化

完全背包问题有一个很简单有效的优化，是这样的：若两件物品i、j满 足Ci <= Cj且Wi >= Wj，则将可以将物品j直接去掉，不用考虑。
这个优化的正确性是显然的：任何情况下都可将价值小耗费高的j换成物美 价廉的i，得到的方案至少不会更差。对于随机生成的数据，这个方法往往会大 大减少物品的件数，从而加快速度。然而这个并不能改善最坏情况的复杂度，因为有可能特别设计的数据可以一件物品也去不掉。这个优化可以简单的O(N2)地实现，一般都可以承受。另外，针对背包问题而言，比较不错的一种方法是：首先将费用大于V的物品去掉，然后使用类似计数排序的做法，计算出费用相同的物品中价值最高的是哪个，可以O(V + N)地完成这个优化。这个不太重要的过程就不给出伪代码了，希望你 能独立思考写出伪代码或程序。

  • O(V N)的算法

这个算法使用一维数组，先看伪代码：

  1. F[0..V] = 0
  2. for i = 1 to N
  3.     for v = Ci to V
  4.         F[v] = max(F[v], F[v - Ci] +Wi)

你会发现，这个伪代码与0-1背包问题的伪代码只有v的循环次序不同而已。 为什么这个算法就可行呢？首先想想为什么0-1背包中要按照v递减的次序来 循环。让v递减是为了保证第i次循环中的状态F[i,v]是由状态F[i - 1, v - Ci]递 推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入 第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果F[i - 1, v - Ci]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加 选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结 果F[i , v - Ci]，所以就可以并且必须采用v递增的顺序循环。这就是这个简单的 程序为何成立的道理。
值得一提的是，上面的伪代码中两层for循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。
这个算法也可以由另外的思路得出。例如，将基本思路中求解F[i, v - Ci]的 状态转移方程显式地写出来，代入原方程中，会发现该方程可以等价地变形成 这种形式：F[i, v] = max(F[i - 1, v], F[i, v - Ci] +Wi)。

第4部分：排序算法

4.1 快速排序

快速排序基本思想

  1. 先从数组中找一个基准数
  2. 让其他比它大的元素移动到数列一边，比他小的元素移动到数列另一边，把数组拆解成两个部分
  3. 再对左右区间重复第二步，直到各区间只有一个数

微信图片_20210805105737.jpg
上图则为一次快排示意图，下面我们再利用递归，分别对左半边区间也就是 [3,1,2] 和右半区间 [7,6,5,8] 执行上诉过程，直至区间缩小为 1 也就是第三条，则此时所有的数据都有序。
简单来说就是我们利用基准数通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比基准数小，另一部分记录的关键字均比基准数大，然后分别对这两部分记录继续进行分割，进而达到有序。
归并排序和快速排序两个用到的都是分治思想，那他们两个有什么不同呢？见下图：

注：这里我们以区间的第一个元素作为基准数

微信图片_20210805105826.jpg
对比
虽然归并排序和快速排序都用到了分治思想，但是归并排序是自下而上的，先处理子问题，然后再合并，将小集合合成大集合，最后实现排序。
快速排序是由上到下的，先分区，然后再处理子问题。归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数需要利用辅助数组保存元素。
快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
我们根据思想可知，快速排序算法的核心就是如何利用基准数将记录分区，这里我们主要介绍两种容易理解的方法，一种是挖坑填数，另一种是利用双指针思想进行元素交换。
下面我们先来介绍下挖坑填数的分区方法：
基本思想是我们首先以序列的第一个元素为基准数，然后将该位置挖坑，下面判断 nums[hight] 是否大于基准数，如果大于，则左移 hight 指针，直至找到一个小于基准数的元素，将其填入之前的坑中，则 hight 位置会出现一个新的坑，此时移动 low 指针，找到大于基准数的元素，填入新的坑中。不断迭代直至完成分区。
直接看代码：

  1. class Solution {
  2.     public int[] sortArray(int[] nums) { 
  4.         quickSort(nums,0,nums.length-1);
  5.         return nums;
  7.     }
  8.     public void quickSort (int[] nums, int low, int hight) {
  10.         if (low < hight) {
  11.             int index = partition(nums,low,hight);
  12.             quickSort(nums,low,index-1);
  13.             quickSort(nums,index+1,hight);
  14.         }    
  16.     }
  17.     public int partition (int[] nums, int low, int hight) {
  19.             int pivot = nums[low];
  20.             while (low < hight) {
  21.                 //移动hight指针
  22.                 while (low < hight && nums[hight] >= pivot) {
  23.                     hight--;
  24.                 }
  25.                 //填坑
  26.                 if (low < hight) nums[low] = nums[hight];
  27.                 while (low < hight && nums[low] <= pivot) {
  28.                     low++;
  29.                 }
  30.                 //填坑
  31.                 if (low < hight) nums[hight] = nums[low];
  32.             }
  33.             //基准数放到合适的位置
  34.             nums[low] = pivot;
  35.             return low;
  36.     }   
  37. }

下面我们来看一下第二种交换方法的思路，原理一致，实现也比较简单。见下图：
微信图片_20210805105949.png
其实这种方法，算是对上面方法的挖坑填坑步骤进行合并，low 指针找到大于 pivot 的元素，hight 指针找到小于 pivot 的元素，然后两个元素交换位置，最后再将基准数归位。

  1. class Solution {
  2.     public int[] sortArray (int[] nums) {   
  4.         quickSort(nums,0,nums.length-1);
  5.         return nums;
  7.     }
  9.     public void quickSort (int[] nums, int low, int hight) {
  11.         if (low < hight) {
  12.             int index = partition(nums,low,hight);
  13.             quickSort(nums,low,index-1);
  14.             quickSort(nums,index+1,hight);
  15.         } 
  17.     }
  19.     public int partition (int[] nums, int low, int hight) {
  21.             int pivot = nums[low];
  22.             int start = low;
  24.             while (low < hight) {
  25.                 while (low < hight && nums[hight] >= pivot) hight--;           
  26.                 while (low < hight && nums[low] <= pivot) low++;
  27.                 if (low >= hight) break;
  28.                 swap(nums, low, hight);  
  29.             }
  30.             //基准值归位
  31.             swap(nums,start,low);
  32.             return low;
  33.     }  
  34.     public void swap (int[] nums, int i, int j) {      
  35.         int temp = nums[i];
  36.         nums[i] = nums[j];
  37.         nums[j] = temp;
  38.      } 
  39. }

快速排序的时间复杂度分析

快排也是用递归来实现的。所以快速排序的时间性能取决于快速排序的递归树的深度。
如果每次分区操作，都能正好把数组分成大小接近相等的两个小区间，那么此时的递归树是平衡的，性能也较好，递归树的深度也就和之前归并排序求解方法一致。
我们每一次分区需要对数组扫描一遍，做 n 次比较，所以最优情况下，快排的时间复杂度是 O(nlogn)。
但是大多数情况下我们不能划分的很均匀，比如数组为正序或者逆序时，即 [1,2,3,4] 或 [4,3,2,1] 时，此时为最坏情况，那么此时我们则需要递归调用 n-1 次，此时的时间复杂度则退化到了 O(n^2)。

快速排序的空间复杂度分析

快速排序主要时递归造成的栈空间的使用，最好情况时其空间复杂度为O (logn),对应递归树的深度。最坏情况时则需要 n-1 次递归调用，此时空间复杂度为O(n)。

快速排序的稳定性分析

快速排序是一种不稳定的排序算法，因为其关键字的比较和交换是跳跃进行的，见下图。
微信图片_20210805110040.jpg
稳定性
此时无论使用哪一种方法，第一次排序后，黄色的 1 都会跑到红色 1 的前面，所以快速排序是不稳定的排序算法。
微信图片_20210805110109.jpg
性能分析

快速排序的迭代写法

该方法实现也是比较简单的，借助了栈来实现，很容易实现。主要利用了先进后出的特性，这里需要注意的就是入栈的顺序，这里算是一个小细节，需要注意一下，其中分区函数和上面一致。大家只需看入栈出栈情况即可。

  1. class Solution {
  3.      public int[] sortArray(int[] nums) {
  4.         Stack<Integer> stack = new Stack<>();
  5.         stack.push(nums.length - 1);
  6.         stack.push(0);
  7.         while (!stack.isEmpty()) {
  8.             int low = stack.pop();
  9.             int hight = stack.pop();
  11.             if (low < hight) {
  12.                 int index = partition(nums, low, hight);
  13.                 stack.push(index - 1);
  14.                 stack.push(low);
  15.                 stack.push(hight);
  16.                 stack.push(index + 1);
  17.             }
  18.         }
  19.         return nums;
  20.     }
  22.     public int partition (int[] nums, int low, int hight) {
  24.             int pivot = nums[low];
  25.             int start = low;
  26.             while (low < hight) {
  28.                 while (low < hight && nums[hight] >= pivot) hight--;           
  29.                 while (low < hight && nums[low] <= pivot) low++;
  30.                 if (low >= hight) break;
  31.                 swap(nums, low, hight); 
  32.             }
  33.             swap(nums,start,low);
  34.             return low;
  36.     } 
  37.     public void swap (int[] nums, int i, int j) {    
  38.         int temp = nums[i];
  39.         nums[i] = nums[j];
  40.         nums[j] = temp;
  41.     }  
  42. }

快速排序优化

三数取中法

我们在上面的例子中选取的都是 nums[low] 做为我们的基准值，那么当我们遇到特殊情况时呢？见下图
微信图片_20210805110233.png
特殊举例
我们按上面的方法，选取第一个元素做为基准元素，那么我们执行一轮排序后，发现仅仅是交换了 2 和 7 的位置，这是因为 7 为序列的最大值。
所以我们的 pivot 的选取尤为重要，选取时应尽量避免选取序列的最大或最小值做为基准值。则我们可以利用三数取中法来选取基准值。
也就是选取三个元素中的中间值放到 nums[low] 的位置，做为基准值。这样就避免了使用最大值或最小值做为基准值。
所以我们可以加上这几行代码实现三数取中法。

  1.  int mid = low + ((hight-low) >> 1);
  2.  if (nums[low] > nums[hight]) swap(nums,low,hight);
  3.  if (nums[mid] > nums[hight]) swap(nums,mid,hight);
  4.  if (nums[mid] > nums[low]) swap(nums,mid,low);

其含义就是让我们将中间元素放到 nums[low] 位置做为基准值，最大值放到 nums[hight],最小值放到 nums[mid],即 [4,2,3] 经过上面代码处理后，则变成了 [3,2,4]。
此时我们选取 3 做为基准值，这样也就避免掉了选取最大或最小值做为基准值的情况。

  1. class Solution {
  2.     public int[] sortArray(int[] nums) {       
  3.         quickSort(nums,0,nums.length-1);
  4.         return nums;
  5.     }
  6.     public void quickSort (int[] nums, int low, int hight) {
  7.         if (low < hight) {
  8.             int index = partition(nums,low,hight);
  9.             quickSort(nums,low,index-1);
  10.             quickSort(nums,index+1,hight);
  11.         }       
  12.     }
  14.     public int partition (int[] nums, int low, int hight) {
  15.             //三数取中，大家也可以使用其他方法
  16.             int mid = low + ((hight-low) >> 1);
  17.             if (nums[low] > nums[hight]) swap(nums,low,hight);
  18.             if (nums[mid] > nums[hight]) swap(nums,mid,hight);
  19.             if (nums[mid] > nums[low]) swap(nums,mid,low); 
  20.             //下面和之前一样，仅仅是多了上面几行代码
  21.             int pivot = nums[low];
  22.             int start = low;
  23.             while (low < hight) {
  24.                 while (low < hight && nums[hight] >= pivot) hight--;           
  25.                 while (low < hight && nums[low] <= pivot) low++;
  26.                 if (low >= hight) break;
  27.                 swap(nums, low, hight); 
  28.             }
  29.             swap(nums,start,low);
  30.             return low;
  31.     }  
  32.     public void swap (int[] nums, int i, int j) {     
  33.         int temp = nums[i];
  34.         nums[i] = nums[j];
  35.         nums[j] = temp;
  36.     }  
  37. }

和插入排序搭配使用

我们之前说过，插入排序在元素个数较少时效率是最高的，没有看过的同学可以去看一下之前的文章，所以当元素数量较少时，快速排序反而不如插入排序好用。
所以我们可以设定一个阈值，当元素个数大于阈值时使用快速排序，小于等于该阈值时则使用插入排序。我们设定阈值为 7 。
三数取中+插入排序

  1. class Solution {
  2.     private static final int INSERTION_SORT_MAX_LENGTH = 7;
  4.     public int[] sortArray(int[] nums) {      
  5.         quickSort(nums,0,nums.length-1);
  6.         return nums;
  7.     }
  9.     public void quickSort (int[] nums, int low, int hight) {
  11.             if (hight - low <= INSERTION_SORT_MAX_LENGTH) {
  12.                 insertSort(nums,low,hight);
  13.                 return;
  14.             }               
  15.             int index = partition(nums,low,hight);
  16.             quickSort(nums,low,index-1);
  17.             quickSort(nums,index+1,hight);         
  18.     }
  20.     public int partition (int[] nums, int low, int hight) {
  21.             //三数取中，大家也可以使用其他方法
  22.             int mid = low + ((hight-low) >> 1);
  23.             if (nums[low] > nums[hight]) swap(nums,low,hight);
  24.             if (nums[mid] > nums[hight]) swap(nums,mid,hight);
  25.             if (nums[mid] > nums[low]) swap(nums,mid,low);   
  26.             int pivot = nums[low];
  27.             int start = low;
  28.             while (low < hight) {
  29.                 while (low < hight && nums[hight] >= pivot) hight--;           
  30.                 while (low < hight && nums[low] <= pivot) low++;
  31.                 if (low >= hight) break;
  32.                 swap(nums, low, hight); 
  33.             }
  34.             swap(nums,start,low);
  35.             return low;
  36.     } 
  38.     public void insertSort (int[] nums, int low, int hight) {
  40.         for (int i = low+1; i <= hight; ++i) {
  41.             int temp = nums[i];
  42.             int j;
  43.             for (j = i-1; j >= 0; --j) {
  44.                 if (temp < nums[j]) {
  45.                     nums[j+1] = nums[j];
  46.                     continue;
  47.                 } 
  48.                 break;
  49.             }
  50.             nums[j+1] = temp;
  51.         }
  52.     } 
  53.     public void swap (int[] nums, int i, int j) {
  55.         int temp = nums[i];
  56.         nums[i] = nums[j];
  57.         nums[j] = temp;
  58.     } 
  59. }

我们继续看下面这种情况：
微信图片_20210805110422.jpg
我们对其执行一次排序后，则会变成上面这种情况，然后我们继续对蓝色基准值的左区间和右区间执行相同操作。也就是 [2,3,6,3,1,6] 和 [8,6] 。我们注意观察一次排序的结果数组中是含有很多重复元素的，我们之前的优化方式并不能很好的解决这种情况。
那么我们为什么不能将相同元素放到一起呢？这样就能大大减小递归调用时的区间大小，见下图。
微信图片_20210805110447.jpg
三向切分
这样就减小了我们的左右区间大小，只需对区间 [3,1,2,4] 和 [8] 执行相同操作即可，我们将数组切分成了三部分，小于基准数的左区间，大于基准数的右区间，等于基准数的中间区间。
其实原理很简单，我们利用探路指针也就是 i，遇到比 pivot 大的元素，则和 right 指针进行交换，交换后 right 指向的元素肯定比 pivot 大，则 right—，但是，此时我们的 nums[i] 指向的元素并不知道情况，所以我们的 i 指针先不动，继续判断。
如果此时 nums[i] < pivot 则与 left 指针交换，注意此时我们的 left 指向的值肯定是等于 povit的，所以交换后我们要 left++,i++, nums[i] == pivot 时，仅需要 i++ 即可，继续判断下一个元素。
三数取中+三向切分+插入排序 

  1. class Solution {
  2.     private static final int INSERTION_SORT_MAX_LENGTH = 7;
  3.     public int[] sortArray(int[] nums) {
  4.         quickSort(nums,0,nums.length-1);
  5.         return nums;
  7.     }
  8.     public void quickSort(int nums[], int low, int hight) {
  9.         //插入排序
  10.         if (hight - low <= INSERTION_SORT_MAX_LENGTH) {
  11.             insertSort(nums,low,hight);
  12.             return;
  13.         }
  14.         //三数取中
  15.         int mid = low + ((hight-low) >> 1);
  16.         if (nums[low] > nums[hight]) swap(nums,low,hight);
  17.         if (nums[mid] > nums[hight]) swap(nums,mid,hight);
  18.         if (nums[mid] > nums[low]) swap(nums,mid,low);
  19.         //三向切分
  20.         int left = low,  i = low + 1, right = hight;
  21.         int pvoit = nums[low];
  22.         while (i <= right) {
  23.             if (pvoit < nums[i]) {
  24.                 swap(nums,i,right);
  25.                 right--;
  26.             } else if (pvoit == nums[i]) {
  27.                 i++;
  28.             } else {
  29.                 swap(nums,left,i);
  30.                 left++;
  31.                 i++;
  32.             }
  33.         }
  34.         quickSort(nums,low,left-1);
  35.         quickSort(nums,right+1,hight);
  36.     }
  37.      public void insertSort (int[] nums, int low, int hight) {
  39.         for (int i = low+1; i <= hight; ++i) {
  40.             int temp = nums[i];
  41.             int j;
  42.             for (j = i-1; j >= 0; --j) {
  43.                 if (temp < nums[j]) {
  44.                     nums[j+1] = nums[j];
  45.                     continue;
  46.                 } 
  47.                 break;
  48.             }
  49.             nums[j+1] = temp;
  50.         }
  51.     } 
  52.     public  void swap (int[] nums, int i, int j) {
  53.         int temp = nums[i];
  54.         nums[i] = nums[j];
  55.         nums[j] = temp;
  56.     }
  57. }