杂记1

链表和数组的区别

从逻辑结构来看

• 数组必须事先定义固定的长度，不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取。
• 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项，非常繁琐）链表必须根据next指针找到下一个元素

从内存存储来看

• (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小
• 链表从堆中分配空间, 自由度大但是申请管理比较麻烦
  从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反， 如果需要经常插入和删除元素就需要用链表数据结构了。

排序基本

• 作为排序依据的数据项称为排序码，也即数据元素的关键码。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可能不唯一。

• 若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。

排序分为两大类：内排序和外排序。

• 内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。
• 外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。

插入排序

• 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

• 插入排序都采用in-place在数组上实现，其运作如下：

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

冒泡排序

• 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
  运作如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

快速排序

• 通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序。
  是冒泡排序的一种升级;
  基本原理：

设定一个基准值（也就是轴）
将比轴小的值，移到轴的左边，形成左子数列
将比轴大的值，移到轴的右边，形成右子数列
分别对左子数列和右子数列做上述三个步骤(递归)，直到左子数列或右子数列只剩一个值或没有数值

选择排序

• 比如在一个长度为N的无序数组中，在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。

希尔排序

• 主要就是选定一个h的有序数组来进行预排序。这样最后进行插入排序的时候，能使数据局部有序。就算交换的话，交换的次数也不会很多。这样h序列称为递增序列。希尔的性能很大部分取决于递增序列 。一般来说我们使用这个序列3x + 1.

堆排序

• 它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。

二叉树

• 在二叉树的第i层上至多有2i-1个结点(i≥1)。
• 深度为k的二叉树至多有2k-1个结点(k≥1)。
• 遍历二叉树
• 先序遍历(DLR)

⑴访问根结点；
⑵先序遍历根结点的左子树；
⑶先序遍历根结点的右子树。

• 中序遍历(LDR)

⑴中序遍历根结点的左子树；
⑵访问根结点；
⑶中序遍历根结点的右子树。

• 后序遍历(LRD)

⑴后序遍历根结点的左子树；
⑵后序遍历根结点的右子树。
⑶访问根结点；

• 层次遍历（队列实现）

构建一个队列专门用来储存二叉树节点指针，先把根节点入队，假设是A，对A元素进行访问，然后对A的左右孩子依次入队，假设B,C。A出队列，再是对B进行访问，同样将B的左右孩子入队列，B出对列······重复以上，知道队列为空。

哈希

• Hashing查找，也称为散列查找或杂凑查找。它既是一种查找方法，又是一种存贮方法，称为散列存贮。散列存贮的内存存放形式也称为散列表
• 哈希函数

在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。
哈希函数是从关键字空间到存储地址空间的一种映象
哈希函数可写成：addr(ai)=H(keyi)
ai是表中的一个元素
addr(ai)是ai的存储地址
keyi是ai的关键字

• 哈希表

应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。

• 哈希查找

又叫散列查找，利用哈希函数进行查找的过程叫哈希查找。

• 冲突：key1key2，但H(key1)=H(key2)的现象叫冲突