目录
一、绪论
1.数据结构
数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。
介于数学、计算机硬件、软件三者之间。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
数据结构包括逻辑结构、存储结构两个层次。
逻辑结构：集合、线性、树、图
存储结构：顺序、链式（不连续）
2.算法
定义：为了解决某类问题而规定的一个有限长的操作序列。
时间复杂度
定理1.1：忽略所有低次幂项和最高次幂的系数
常量阶：O(1),与问题规模n无关的常数。
线性阶：O(n)
平方阶：O(n2)
立方阶：O(n3)
对数阶：O(log2N)
空间复杂度
对于一个算法，其时间复杂度和空间复杂度往往是相互影响的， 当追求一个较好的时间复杂度时， 可能会导致占用较多的存储空间 ， 即可能会使空间复杂度的性能变差， 反之亦然。
不过， 通常情况下， 鉴于运算空间较为充足， 人们都以算法的时间复杂度作为算法优劣的衡
址指标。
排序
内部排序
内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中， 可以将排序记录区分为两个区域：有序序列区和无序序列区。
根据逐步扩大记录有序序列长度的原则不同， 可以将内部排序分为以下几类。
插入、交换、选择、归并、分配。
外部排序
待排序记录的存储方式
顺序表、链表
算法效率的评价指标
对于排序操作，时间主要消耗在关键字之间的比较和记录的移动上（这里， 只考虑以顺序表方式存储待排序记录），排序算法的时间复杂度由这两个指标决定。因此可以认为，高效的排序算法的比较次数和移动次数都应该尽可能的少。
1.插入排序
插入排序的基本思想是：每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。
1-1.直接插入排序
直接插入排序 (Straight Insertion Sort) 是一种最简单的排序方法，其基本操作是将一条记录插入到已排好序的有序表中， 从而得到一个新的、 记录数量增1的有序表。
1-2.折半插人排序
1-3.希尔排序
分组插入,时间复杂度突破平方阶。
2.交换排序
交换排序的基本思想是：两两比较待排序记录的关键字，一旦发现两个记录不满足次序要求时则进行交换，直到整个序列全部满足要求为止。
2-1.冒泡排序
2-2.快速排序
3.选择排序
选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，按顺序放在已排序的记录序列的最后，直到全部排完为止。
0 条评论