数据结构-列表

Overview

所有数据结构的操作大体可以分为两种类型

数据结构的操作类型

• 静态操作：不改变元素的集合和结构，可能改变元素的值
• 动态操作：元素结构（顺序）可能调整，元素可能增减

Link to original

对比列表和向量，

列表 vs 向量

• 向量擅长静态操作
• 列表擅长动态操作

Link to original

结构

列表有如下结构：

无序 & 有序

• 无序列表：不维护数据间的有序性
• 有序列表：维护数据间的有序性

列表的排序

• 选择排序：类似冒泡排序，但交换时只取前缀中的最大值交换
• 插入排序：打牌时用的排序:)，可以在线进行

逆序对

一个好的排序算法，应该使序列逆序对越少时，排序交换次数也越少。