算法学习（《算法》学习笔记）

 

一、排序

1.基本排序

选择排序：基本思路，每次找出最小的然后交换。时间复杂度为平方级别。

插入排序：在每次迭代i，a[i]和左边比它大的交换，不用管右边。最好的情况是实现已经排好了，最差的情况是去完全是从大到小排的。

希尔排序：出发点是插入排序，先笼统排再精细排。这个排序方法非常实用。

2.归并排序（分治的思想）

归并排序：基本思路，把数组分为两半，对每一部分进行递归排序，合并两等分。可以用在大量数据上。时间复杂度NlogN。

图1.1 归并示意图

图1.2 归并排序示意图

（归并排序和插入排序更稳定，而选择排序和希尔排序不是这样，因为后者经过长距离的交换）

3.快速排序

快速排序和归并排序是互补的：归并排序将数数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组的排序的方式则是当两个子数组都有序是整个数组也就自然有序了。

切分的方法：一般的策略是先随意地取a[lo]作为切分元素，即那个将会被排定的元素，然后我们从数组的左端开始向右扫描直到找到一个大于等于它的元素，再从数组的右端开始扫描直到找到一个小于等于它的元素。这两个元素显然是没有排定的，因此我们交换他们的位置。如此继续，我们就可以保证左指针i的左侧元素都不大于切分元素，右指针讲得右侧元素都不小于切分元素。当两个指针相遇是，我们只要将切分的元素和a[lo]和左子数组最右测得元素a[j]交换然后返回j就可以了。大致过程：

图1.3 切分示意图

图1.4 快速排序示意图

快速排序算法的改进方法一般基于这两点：1.对于小数组，快速排序比插入排序要慢；2.因为地柜，快速排序的sort（）方法在小数组中也会调用自己。

三向切分的快速排序：

图1.5三向快速切分示意图

图1.6三向切分的轨迹

二、优先队列

优先队列是一种抽象数据类型，它表示了一组值和对这些值得操作，它的抽象层使我们能够方便地将应用程序（用例）和我们将在本节中学习的各种实现隔离开来。优先队列的最重要的操作就是删除最大元素和插入元素。

1.初级实现

可以使用有序数组实现和无序数组实现。

堆的定义：当一颗二叉树的每个结点都大于等于它的两个子结点是，它被称为堆有序。

定义：二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不适用数组的第一个位置）。

图2.1 堆的示意图

图2.2 由下至上的堆有序化（上浮）和由上至下的堆有序化（下沉）示意图

图2.3堆的操作

堆排序

图2.4堆排序示意图

上图所示的是堆排序示意图，堆排序主要包括两个步骤，先进性堆的构造（使得堆有序）然后进行下沉排序（得到排序）。当空间十分紧张的时候这种办法十分流行，因为代码量比较少。

二、查找

1.二分法查找

图 2.1 二分法查找

可以写成递归的代码和迭代的代码。首先讲key和中间键比较，如果相等则返回其索引；如果小于中间键则在左半部分查找；大于则在右半部分查找。

2.二叉查找树(BST)

定义一些术语：所使用的数据结构由结点组成，结点包含的链接可以为空（null）或者指向其他结点。在二叉树中，每个结点只能有一个父结点（只有一个例外，也就是根节点，他没有父节点），而且每个结点都只有左右连个链接，分别指向自己的左子节点和右子节点。

图 2.2 二叉树以及二叉查找树

定义：一颗二叉查找树是一个二叉树，其中每个结点都包含一个comparable的键（以及相关联的值）且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。

图2.3 一棵二叉查找树

查找算法：如果树是空的，则查找未命中；如果查找的键和根结点的键相等，查找命中，否则我们就（递归地）在适当的子树继续查找。如果被查找的键较小就选择左子树，较大则选择右子树。

图2.4 二叉查找树中的查找命中（左）和未命中（右）