1.线性结构
线性结构和非线性结构主要看元素之间的关系，如果是一对一的关系则是线性表，不是一对一关系则是非线性表
线性表分为顺序存储结构和链式存储结构，例如栈和队列
2.选择排序的特殊性
- 元素的比较次数与初始序列无关
- 算法的时间复杂度与初始序列无关
无论初始序列如何，都会将每一个元素与其他元素比较找出最大或最小
3.快速排序
找到一个支点，将该序列位置整个调整一遍，左边的元素都比支点小，右边的元素都比支点大，支点不一定是左边第一个数，可以任意选择
- 初始数据有序时，花费的时间反而更多
因为如果选取支点值为第一个数时,相当于每次分块只减少了一个值，总时间为O(n2)，排序有序数据，花费的时间反而更多
4.堆排序
堆排序的时间复杂度不会因为待排序序列的有序程度而改变，都需要构造一个最大堆，并不断进行调整
5.希尔排序
希尔排序是插入排序的一种，是直接插入排序算法的一种更高效改进版本
6.归并排序
需要额外的内存
7.稳定排序和非稳定排序
- 稳定排序：
基数排序，冒泡排序，插入排序，归并排序 - 不稳定排序
堆排序，快速排序，希尔排序，选择排序
网友评论