数据存储在内存中的顺序和位置关系 就叫数据结构
常见的几种数据结构 1、数组和链表 数组内存连续 易读难增删数组空间连续 访问直接索引访问 而增删则需要移除数据后将该元素后面所有的元素往前移保持内存连续 因此增删难
后者内存不连续 分散存储 易增删难读链表读取必须从表头读起(双向链表也可以从队尾) 一直找到自己想要读取的数据为止 因此读取难 而一旦找到了自己想要的数据 增删只需要更改前后两个数据的next指针即可 因此增删易
链表拓展有双向 循环 双向循环 只是指针的增加意味着内存空间的更多需求和更多指针的更改
因此我们访问数据和修改数据是很简单的
4、堆和二叉树 堆是一种图的树形结构 被用于实现“priority queues” (取值必须从最小值按顺序取出)堆有一个性质：子节点的大小 必须 大于父节点 所以无论数据量有多少 我们取出最小值的时间复杂度都是最小的 o(1) 但是由于性质的存在 取出最小值之后 需要将最后的数据移到最顶端 并重新比较整理 因此时间复杂度是logn
二叉树 二叉查找树 也是一种图的数据结构二叉树有两个性质:
第一个是每个结点的值都大于其左子树上任意一个结点的值；
第二个是每个结点的值都小于其右子树上任意一个结点的值；
如果理解了这两个性质 我们就能得出结论最小值肯定是从顶端开始往左边一直找找到左边的末端，而最大值要从顶端往右边一直找找到右边的末端
增加删除和查找结点的时候 只要考虑到值和结点的大小比较 大于就往右边放 小于就往左边放
而时间复杂度则是需要考虑到二叉树的高度的 如果树朝单侧发展 那么查找到的肯定就是o(n) 如果是比较均衡的树形结构 那么肯定是o(logn)
关于排序有两个概念
第一个叫稳定排序和不稳定排序 意思是两个相同的元素在排序前后两个元素的顺序并没有因为排序而发生变动 就叫稳定排序 反之不稳定
第二个叫时间复杂度 也是时间复杂性 是衡量一个排序算法的最直观的指标
从左到右慢慢挨个比较
时间复杂度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;
}
}
}
选择最小的 交换左边第一个 然后第二轮从第二个开始选出最小的 交换第二个 依次进行
时间复杂度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;
}
从右侧未排序区域取一个元素出来 和左侧已排序区域比较 插入到合适的位置 就叫插入排序
时间复杂度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;
}
堆排序的特点 其实就是利用了堆的数据结构特点 首先取出根结点 然后重构堆，再取出根结点放在后面，再重构，直到取完该堆数据则排序完成。
时间复杂度 nlogn 不稳定排序图解堆排序
5、归并排序把一个有序的序列分成长度相同的两个子序列 然后递归将子序列分成两个相同长度的更小子序列 直到子序列无法继续往下分(也就是只有一个元素的时候) 然后就开始对子序列开始进行归并，而归并指的就是两个排好序的子序列合成一个有序序列，每次依次比较每个子序列的的第一位元素的大小 然后依次取出归并成一个父序列 直到所有的子序列归并为一个序列为止
时间复杂度 nlogn 稳定排序