AI必备八大算法内功心法秘籍_风闻

一、前言

如果说各种编程语言是程序员的招式，那么数据结构和算法就相当于程序员的内功。

想写出精炼、优秀的代码，不通过不断的锤炼，是很难做到的。

二、八大排序算法

排序算法作为数据结构的重要部分，系统地学习一下是很有必要的。

1、排序的概念

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

排序分为内部排序和外部排序。

若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。

反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

2、排序分类

八大排序算法均属于内部排序。如果按照策略来分类，大致可分为：交换排序、插入排序、选择排序、归并排序和基数排序。如下图所示：

3、算法分析

下表给出各种排序的基本性能，具体分析请参看各排序的详解：

三、算法心法秘籍1.冒泡排序

冒泡排序是一种交换排序。

什么是交换排序呢？

答曰：两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。

算法思想

它重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名冒泡排序。

动态效果示意图：

假设有一个大小为 N 的无序序列。以升序冒泡排序为例，冒泡排序就是要每趟排序过程中通过两两比较相邻元素，将小的数字放到前面，大的数字放在后面。

2.直接插入排序

直接插入排序（Insertion Sort）序是一种最简单的插入排序。为简化问题，我们下面只讨论升序排序。

算法思想

插入排序：每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，知道全部插入完成。 

动态效果示意图：

以上的过程，其实就是典型的直接插入排序，每次将一个新数据插入到有序队列中的合适位置里。

很简单吧，接下来，我们要将这个算法转化为编程语言。

假设有一组无序序列 R0, R1, … , RN-1。

(1) 我们先将这个序列中下标为 0 的元素视为元素个数为 1 的有序序列。

(2) 然后，我们要依次把 R1, R2, … , RN-1 插入到这个有序序列中。所以，我们需要一个外部循环，从下标 1 扫描到 N-1 。

(3) 接下来描述插入过程。假设这是要将 Ri 插入到前面有序的序列中。由前面所述，我们可知，插入Ri时，前 i-1 个数肯定已经是有序了。

所以我们需要将Ri 和R0 ~ Ri-1 进行比较，确定要插入的合适位置。这就需要一个内部循环，我们一般是从后往前比较，即从下标 i-1 开始向 0 进行扫描。

3.希尔排序

希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。

希尔排序，也称递减增量排序算法，以其设计者希尔（Donald Shell）的名字命名，该算法由 1959 年公布。

算法思想

我们举个例子来描述算法流程（以下摘自维基百科）：

假设有这样一组数 {13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10}，如果我们以步长为 5 开始进行排序：

C++

1：13 14 94 33 82

2：25 59 94 65 23

3：45 27 73 25 39

4：10

然后我们对每列进行排序：

C++

1：10 14 73 25 23

2：13 27 94 33 39

3：25 59 94 65 82

4：45

将上述四行数字，依序接在一起时我们得到：{10, 14, 73, 25, 23, 13, 27, 94, 33, 39, 25, 59, 94, 65, 82, 45}，然后再以 3 为步长：

C++

1：10 14 73

2：25 23 13

3：27 94 33

4：39 25 59

5：94 65 82

6：45

排序之后变为：

C++

1：10 14 13

2：25 23 33

3：27 25 59

4：39 65 73

5：45 94 82

6：94

最后以 1 为步长进行排序（此时就是简单的插入排序了）。

可想而知，步长的选择是希尔排序的重要部分。算法最开始以一定的步长进行排序，然后会继续以更小的步长进行排序，最终算法以步长为 1 进行排序。当步长为 1 时，算法变为直接插入排序，这就保证了数据一定会被全部排序。

4.快速排序

快速排序是一种交换排序，它由C. A. R. Hoare在1962年提出。

算法思想

快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。

然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

动态效果示意图：

详细的图解往往比大堆的文字更有说明力，所以直接上图：

上图中，演示了快速排序的处理过程：

初始状态为一组无序的数组：2、4、5、1、3。

经过以上操作步骤后，完成了第一次的排序，得到新的数组：1、2、5、4、3。

新的数组中，以2为分割点，左边都是比2小的数，右边都是比2大的数。

因为2已经在数组中找到了合适的位置，所以不用再动。

2左边的数组只有一个元素1，所以显然不用再排序，位置也被确定。（注：这种情况时，left指针和right指针显然是重合的。因此在代码中，我们可以通过设置判定条件left必须小于right，如果不满足，则不用排序了）。

而对于2右边的数组5、4、3，设置left指向5，right指向3，开始继续重复图中的一、二、三、四步骤，对新的数组进行排序。

5.简单选择排序

简单选择排序是一种选择排序。

选择排序：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。

二、算法思想

简单排序很简单，它的大致处理流程为：

从待排序序列中，找到关键字最小的元素；

如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；

从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

动态效果示意图：

举例说明，处理过程示意图如下所示：

如图所示，每趟排序中，将当前第 i 小的元素放在位置 i 上。

6.堆排序

堆排序是一种选择排序。

选择排序：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。

算法思想

堆排序是利用堆的性质进行的一种选择排序。

动态效果示意图：

堆是一棵顺序存储的完全二叉树。

其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。

其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。

举例来说，对于n个元素的序列{R0, R1, … , Rn}当且仅当满足下列关系之一时，称之为堆：

Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)

Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)

其中i=1,2,…,n/2向下取整；

如上图所示，序列R{3, 8, 15, 31, 25}是一个典型的小根堆。

堆中有两个结点，元素3和元素8。

元素3在数组中以R[0]表示，它的左孩子结点是R[1]，右孩子结点是R[2]。

元素8在数组中以R[1]表示，它的左孩子结点是R[3]，右孩子结点是R[4]，它的父结点是R[0]。可以看出，它们满足以下规律：

设当前元素在数组中以R[i]表示，那么，

(1) 它的左孩子结点是：R[2*i+1];

(2) 它的右孩子结点是：R[2*i+2];

(3) 它的父结点是：R[(i-1)/2];

(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

首先，按堆的定义将数组R[0..n]调整为堆（这个过程称为创建初始堆），交换R[0]和R[n]；

然后，将R[0..n-1]调整为堆，交换R[0]和R[n-1]；

如此反复，直到交换了R[0]和R[1]为止。

以上思想可归纳为两个操作：

（1）根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。

（2）每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。

当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。

先通过详细的实例图来看一下，如何构建初始堆。

设有一个无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。

构造了初始堆后，我们来看一下完整的堆排序处理：

还是针对前面提到的无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 来加以说明。

相信，通过以上两幅图，应该能很直观的演示堆排序的操作处理。 

看完上面所述的流程你至少有一个疑问：

如何确定最后一个非叶子结点？

其实这是有一个公式的，设二叉树结点总数为 n，则最后一个非叶子结点是第⌊n/2⌋个。

7.归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法思想

该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

动态效果示意图：

分而治之：

1、分阶段

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为logn。

2、治阶段

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

、

8.基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

算法思想

基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

算法步骤：

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。

从最低位开始，依次进行一次排序。

这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。

不妨通过一个具体的实例来展示一下基数排序是如何进行的。 设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。

我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以 0~9 来表示的，所以我们不妨把 0~9 视为 10 个桶。

我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是 0，将这个数存入编号为 0 的桶中。

分类后，我们在从各个桶中，将这些数按照从编号 0 到编号 9 的顺序依次将所有数取出来。这时，得到的序列就是个位数上呈递增趋势的序列。

按照个位数排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。

动态效果示意图：

AI本身就是在大量数据中进行处理从而得到更精准的数据值，然而这些基本的八大算法就更应该要掌握好了。我们在人工智能课程学习中我们也会详细讲解到算法思维理解以及代码操作，如果感兴趣的可以下方留言。