排序总结(1):排序的相关概念+插入排序
文章目录
相关概念
排序方法的稳定性

排序方法的分类
- 根据数据对象的存储位置分类:内排序和外排序

2.根据排序原则分类
3.根据时间复杂度分类
排序过程的基本操作

由排序的基本操作,引入排序的时间开销

待排序序列的存储方式

以顺序表为待排记录序列的存储结构的几种排序方式
顺序表数据类型的定义
直接插入排序:插入排序的简单排序方法
基本思想

例子

性质

折半插入排序:插入排序的先进排序方法
基本思想

例子

性质

2-路插入排序:使用静态链表保存生成数据的方法
基本思想

例子

性质

希尔排序:直接插入排序的改进方法
基本思想

例子

性质
希尔排序是插入排序中唯一一种不稳定的排序方法
以静态链表为待排记录序列的存储结构的排序方法
静态链表数据类型的定义
相较顺序表存储结构的优势
通过改变存储结构,即以静态链表作为待排记录序列的存储结构,避免在排序过程中记录的移动
表插入排序
基本思想

性质

缺陷
表插入排序的结果是以链表形式存在,不能做折半查找等随机查找。因此我们若要对排序后的结果做随机查找,就需要在排序后对记录做重排,使其在数组中顺序存储
重排记录的方法


评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论