一. 什么是数据结构：

对到底什么是数据结构这个概念,一直有很多不同的解释,也有许多不同的争论,这里只代表了我个人的认识.

数据结构:我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器(内存)中,以及在此基础上为实现某 个功能(比如查找某个元素,删除某个元素等)而执行的相应操作,这个相应的操作也叫做算法.

1.算法的实现是依据不同的数据结构的。

2.算法：是对特定问题求解步骤的一种描述，以下特征：有穷性，确定性，可行性，输入和输出；

二.插入排序：每次将一个待排的记录插入到前面的已经排好的队列中的适当位置。
①.直接插入排序

直接排序法在最好情况下（待排序列已按关键码有序），每趟排序只需作1次比较而不需要移动元素。所以n个元素比较次数为n-1，移动次数0。
最差的情况下（逆序），其中第i个元素必须和前面的元素进行比较i次，移动个数i+1，所以总共的比较次数 比较多，就不写出来了
总结：是一种稳定的排序方法，时间复杂度O(n^2)，排序过程中只要一个辅助空间，所以空间复杂度O(1)
②.希尔排序

缩小增量排序，对直接插入排序的一种改进
分组插入方法。
总结：是一种不稳定的排序方法，时间复杂度O(n^1.25)，空间复杂度O(1)
三.交换排序
①.冒泡排序

最好的情况下，就是正序，所以只要比较一次就行了，复杂度O(n)
最坏的情况下，就是逆序，要比较n^{2次才行，复杂度O(n}2)
总结：稳定的排序方法，时间复杂度O(n^2)，空间复杂度O(1)，当待排序列有序时，效果比较好。
②.快速排序

通过一趟排序将待排的记录分割成独立的两部分，其中一部分记录的关键字均比另一个部分的关键字小，然后再分别对这两个部分记录继续进行排序，以达到整个序列有效。
总结：在所有同数量级O(nlogn)的排序方法中，快速排序是性能最好的一种方法，在待排序列无序时最好。算法的时间复杂度是O(nlogn)，最坏的时间复杂度O(n^2)，空间复杂度O(nlogn)
四.选择排序
①.直接选择排序

和序列的初始状态无关
总结：时间复杂度O(n^2)，无论最好还是最坏
②.堆排序

直接选择排序的改进
总结：时间复杂度O(nlogn)，无论在最好还是最坏情况下都是O(nlogn)
五.归并排序

总结：时间复杂度O(nlogn)，空间复杂度O(n)
六.基数排序

按组成关键字的各个数位的值进行排序，是分配排序的一种。不需要进行排码值间的比较就能够进行排序。
总结：时间复杂度O(d(n+rd))
七.总结：

n比较小的时候，适合 插入排序和选择排序
基本有序的时候，适合 直接插入排序和冒泡排序
n很大但是关键字的位数较少时，适合 链式基数排序
n很大的时候，适合 快速排序 堆排序 归并排序
无序的时候，适合 快速排序
稳定的排序：冒泡排序 插入排序 归并排序 基数排序
复杂度是O(nlogn)：快速排序 堆排序 归并排序
辅助空间（大 次大）：归并排序 快速排序
好坏情况一样：简单选择（n^2），堆排序（nlogn），归并排序（nlogn）
最好是O(n)的：插入排序 冒泡排序

八. 时间复杂度和空间复杂度：

（1）时间频度 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时 间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的 语句执行次数称为语句频度或时间频度。记为T(n)。
（2）时间复杂度 在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间 复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大 时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另 外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为 O(n2)。 按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),…， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 2、空间复杂度 与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。
（3）渐进时间复杂度评价算法时间性能 　　主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。

（4)空 间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储 空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定 的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必 须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们 称这种算法是“就地"进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着 n的增大而增大，当n较大时，将占用较多的存储单元，快速排序和归并排序算法就属于这种情况。

（5） 如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当 一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n).若形 参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间， 用它来存储对应实参变量的地址，以便由系统自动引用实参变量。

(6) 下面如图是常见的算法的时间复杂度和空间复杂度: