《我的第一本算法书》笔记一

2020 年 11 月 14 日
筆記
算法

一、数据结构

数据存储在内存中的顺序和位置关系就叫数据结构

常见的几种数据结构

1、数组和链表

数组内存连续易读难增删

数组空间连续访问直接索引访问而增删则需要移除数据后将该元素后面所有的元素往前移保持内存连续因此增删难

后者内存不连续分散存储易增删难读

链表读取必须从表头读起(双向链表也可以从队尾) 一直找到自己想要读取的数据为止因此读取难而一旦找到了自己想要的数据增删只需要更改前后两个数据的next指针即可因此增删易
链表拓展有双向循环双向循环只是指针的增加意味着内存空间的更多需求和更多指针的更改

2、栈和队列均无法访问中间数据

栈先进后出访问中间数据必须将数据出栈移至栈顶访问只限栈顶

队列先进先出访问中间数据必须将数据出队移至对头访问时可以访问队头和队尾

3、哈希表

内存是不连续的

对于我们想要修改的数据我们访问需要通过哈希函数(常见取模)访问到数据

发生键冲突也就是哈希冲突的时候我们会通过相对应的方法将哈希值存储(链地址是同键存为一个链表，开放地址法是候补哈希函数，等)

因此我们访问数据和修改数据是很简单的

4、堆和二叉树

堆是一种图的树形结构被用于实现“priority queues” (取值必须从最小值按顺序取出)

堆有一个性质：子节点的大小必须大于父节点所以无论数据量有多少我们取出最小值的时间复杂度都是最小的 o(1) 但是由于性质的存在取出最小值之后需要将最后的数据移到最顶端并重新比较整理因此时间复杂度是logn

二叉树

二叉查找树也是一种图的数据结构

二叉树有两个性质:
第一个是每个结点的值都大于其左子树上任意一个结点的值；
第二个是每个结点的值都小于其右子树上任意一个结点的值；
如果理解了这两个性质我们就能得出结论最小值肯定是从顶端开始往左边一直找找到左边的末端，而最大值要从顶端往右边一直找找到右边的末端
增加删除和查找结点的时候只要考虑到值和结点的大小比较大于就往右边放小于就往左边放
而时间复杂度则是需要考虑到二叉树的高度的如果树朝单侧发展那么查找到的肯定就是o(n) 如果是比较均衡的树形结构那么肯定是o(logn)

二、排序

关于排序有两个概念
第一个叫稳定排序和不稳定排序意思是两个相同的元素在排序前后两个元素的顺序并没有因为排序而发生变动就叫稳定排序反之不稳定
第二个叫时间复杂度也是时间复杂性是衡量一个排序算法的最直观的指标

1、冒泡排序

从左到右慢慢挨个比较

时间复杂度n2 稳定排序

伪代码：
for (i = 0;i<length-1;i++)
{
for (j = 0;j<length-1-i;j++)
{
if array[j] > array[j+1]
{
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}

2、选择排序

选择最小的交换左边第一个然后第二轮从第二个开始选出最小的交换第二个依次进行

时间复杂度n2 不稳定排序

这边重点提一句因为关于选择排序是不是稳定排序我觉得是需要考虑排序的算法规则的首先我们在未排序部分选择一个最小元素，如果我们将它直接移动到未排序部分之前那么这个算法是稳定的，而如果我们将该元素和未排序部分的第一位进行交换那么肯定是不稳定的排序，至于为什么大家都考虑为不稳定排序的原因很大一部分原因是交换的代价远远小于移动的代价！

伪代码：
for i=0;i<length-1;i++
{
int minIndex = i;
for j=i+1;j<length;j++
{
if array[j] < array[minIndex]
minIndex = j;
}
temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}

3、插入排序

从右侧未排序区域取一个元素出来和左侧已排序区域比较插入到合适的位置就叫插入排序

时间复杂度n2 稳定排序

关于插入排序有两种极端情况如果刚好是排好序的且是和要求的一样正序的话那么时间复杂度是n，如果是排好序且是反序的话则是n2 所以平均是n2
伪代码：
int i, j;
for (i = 1; i < length; i++)
{
cur = num[i];
for (j = i – 1; j >= 0 && num[j] > cur; j–)
{
num[j + 1] = num[j];
}
num[j + 1] = cur;
}

4、堆排序

堆排序的特点其实就是利用了堆的数据结构特点首先取出根结点然后重构堆，再取出根结点放在后面，再重构，直到取完该堆数据则排序完成。

时间复杂度 nlogn 不稳定排序

图解堆排序

5、归并排序

把一个有序的序列分成长度相同的两个子序列然后递归将子序列分成两个相同长度的更小子序列直到子序列无法继续往下分(也就是只有一个元素的时候) 然后就开始对子序列开始进行归并，而归并指的就是两个排好序的子序列合成一个有序序列，每次依次比较每个子序列的的第一位元素的大小然后依次取出归并成一个父序列直到所有的子序列归并为一个序列为止

时间复杂度 nlogn 稳定排序

伪代码：主要是递归遍历排序
public static void Sort(int[] a, int f, int e)
{
if (f < e)
{
int mid = (f + e) / 2;
Sort(a, f, mid);
Sort(a, mid + 1, e);
MergeMethid(a, f, mid, e);
}
}
private static void MergeMethid(int[] a, int f, int mid, int e)
{
int[] t = new int[e – f + 1];
int m = f, n = mid + 1, k = 0;
while(n <= e && m <= mid)
{
if (a[m] > a[n]) t[k++] = a[n++];
else t[k++] = a[m++];
}
while (n < e + 1) t[k++] = a[n++];
while (m < mid + 1) t[k++] = a[m++];
for (k = 0, m = f; m < e + 1; k++, m++) a[m] = t[k];
}

6、快速排序

快排运用了二分的思想，首先选择一个基准，定义左右两端指针，先从左到右进行扫描直到，R[hi] < temp,将R[hi]移动至lo所在位置 [公式] 从右往左进行扫描，直到R[lo] > temp,将R[lo]移动到hi所在位置上，左右端指针在排序过程中从数组的两端往中间进行靠近，直到hi == lo。而快速排序则要进行多次快排过程，直到划分的区间最后长度仅为1.
快速排序的优异之处在于它本身会对所有的值和基准值进行比较而这个比较将会在整个排序周期中只有1次如果a<b 那么a和b将永远不会再进行比较如果a<b<c 同样的那么a将永远不会和c进行比较就不会有任何的冗余操作

时间复杂度 nlogn 不稳定排序

伪代码：
void QuickSort(int R[], int lo, int hi){
int i = lo, j = hi;
int temp;
if(i < j){
temp = R[i];
while (i != j)
{
while(j > i && R[j] >= temp)– j;
R[i] = R[j];
while(i < j && R[i] <= temp)++ i;
R[j] = R[i];
}
R[i] = temp;
QuickSort(R, lo, i – 1);
QuickSort(R, i + 1, hi);
}
}